Neeraj's Blog

There is always an open source solution..

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²).

Single Post Navigation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: