We will discuss three comparison-based sorting algorithms in the next few slides:
Bubble Sort,
Selection Sort,
Insertion Sort.
They are called comparison-based, as they compare pairs of elements of the array and decide
whether to swap them or not.
These three sorting algorithms are the easiest to implement but also not the most efficient, as
they run in O(N²).
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent
elements if they are in the wrong order. This algorithm is not efficient for large data sets, as its
average and worst-case time complexity are quite high.
Program for Bubble Sort
#include <stdio.h>
int main() {
int i,temp;
int ptr,n;
int arr[5]={8,3,60,45,10};
for(i=1;i<=4;i++)
{
ptr=0;
while(ptr<=4)
{
if (arr[ptr]>arr[ptr+1])
{
temp=arr[ptr];
arr[ptr]=arr[ptr+1];
arr[ptr+1]=temp;
}
ptr++;
}
}
for(i=0;i<=4;i++)
printf(“%d\t",arr[i]);
return 0;
}
Complexity Analysis of Bubble Sort:
Time Complexity: O(n2)
Auxiliary Space: O(1)
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts by repeatedly selecting the
smallest element from the unsorted portion and swapping it with the first unsorted element.
Find the smallest element and swap it with the first element. This way we get the smallest
element at its correct position.
Then find the smallest among remaining elements (or second smallest) and swap it with
the second element.
We keep doing this until we get all elements moved to correct position.
Program
#include<stdio.h>
void main()
{
int array[5]={100,500,800,330,20}, i, j, temp,min;
for(i = 0 ; i< 4; i++)
min=i;
for( j = i+1; j<=4 ; j++ )
if(array[j] < array[min] )
min=j;
temp= array[min];
array[min] = array[i];
array[i] = temp;
}
printf("Sorted list in ascending order:\n");
for(i= 0 ; i <=4 ; i++ )
printf("%d\n", array[i]);
Insertion Sort
The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-
list (in the same array). This algorithm is not suitable for large data sets as its average and worst
case complexity are of (n2), where n is the number of items.
For example,
Consider an array: [12, 11, 13, 5, 6]
• Iteration 1 (i = 1, key = 11):
Compare 11 with 12. Since 11 < 12, shift 12 one position to the right and insert 11 at the
beginning.
Array becomes: [11, 12, 13, 5, 6].
• Iteration 2 (i = 2, key = 13):
Compare 13 with 12. Since 13 > 12, leave it in its place.
Array remains: [11, 12, 13, 5, 6].
• Iteration 3 (i = 3, key = 5):
Compare 5 with 13, 12, and 11. Since 5 < 13, 5 < 12, and 5 < 11, shift all three elements one
position to the right and insert 5 at the beginning.
Array becomes: [5, 11, 12, 13, 6].
• Iteration 4 (i = 4, key = 6)
Compare 6 with 13, 12, and 11. Since 6 < 13, 6 < 12, and 6 < 11, shift the elements 13, 12, and
11 to the right, and insert 6 in the correct position.
Array becomes: [5, 6, 11, 12, 13].