Sorting Algorithms 1

Bubble Sort

In bubble sorting we compare the two adjacent elements, and swap them if they are not in order.

Code in C

void bubsort(int v[], int n)
{
 int i,j,temp;
 for(i = n-2; i >= 0; i--)
 for(j = 0; j <= i; j++)
 if(v[j] > v[j+1]){
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
}

Time Analysis

Worst case : O(n²)

Best case : O(n)

Average case: O(n²)

Best case is when the input is a sorted one, and worst case is when the input is reverse sorted.

Insertion Sort

In insertion sort we check each element and put it in the right place in a sorted list.

It is efficient for small data sets. More efficient than bubble and selection sort of same time complexity.

Code in C

void insertsort(int v[], int n)
{
 int i, j, key;

for(i = 1; i < n-1; i++) {
 j = i;
 key = v[i];

while(v[j-1] > key && j>0){
 v[j] = v[j-1];
 j = j-1;
 }
 v[j] = key;
 }
}

Time Analysis

Worst case : O(n²)

Best case : O(n)

Average case : O(n²)

Best case is when the input is a sorted one, and worst case is when the input is reverse sorted.

Selection Sort

Algorithm is as follows

1. Find the minimum value in the list.
2. Swap it with the value in the first position.
3. Repeat the steps above for the remainder of the list. (starting at the second position and advancing each time)

Code In C

void selectsort(int v[], int n)
{
 int i, min, pos, temp;
 for(pos= 0; pos<n; pos++) {
 min = pos;
 for(i = pos+1; i<n; i++){
 if(v[i] < v[min])
 min = i;
 }
 if(min != pos){
 temp = v[min];
 v[min] = v[pos];
 v[pos] = temp;
 }
 }
}

Time Analysis

Worst case : O(n²)

Best case : O(n²)

Average case : O(n²)

In selection sort, every time, the time complexity is of O(n²).