Neeraj's Blog

There is always an open source solution..

Sorting Algorithms 2

Quick Sort

This algorithm was developed by Tony Hoare in 1960. It is a divide and conquer algorithm.

Algorithm is as follows

  1. Select an element ‘pivot’ from the list.
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
  3. Recursively sort the sub-lists of lesser elements and greater elements.
Code In C

void qsort(int v[], int left, int right)
{
 int i, last;
 void swap(int v[], int i, int j);
 if(left >= right)
 return;
 swap(v, left, (left+right)/2);
 last = left;
 for(i = left+1; i <= right; i++){
 if(v[i] < v[left])
 swap(v, ++last, i);
 }
 swap(v, left, last);
 qsort(v, left, last-1);
 qsort(v, last+1, right);
}

Time Analysis

Worst case : O(n²)

Best case : O(n log n)

Average case: O(n log n)

In the best case, each time the list is divided into two equal half. So there will be log n nested calls. And this operation is done n times.

Recurrence relation is T(n) = O(n) + 2T(n/2).

And also selecting the pivot plays a good role in time complexity. For already sorted list selecting the middle element or random element is better than selecting first or last element.

Merge Sort

Merge sort was developed by  John Von Neumann in 1945. It is also a divide and conquer algorithm. It always does  a fewer comparison as compared to quick sort.

Algorithm is as follows

  1. Divide the element into n sub-lists of single elements. Now each sub-list is sorted since there is only one element.
  2. Repeatedly merge sub-lists to to produce a larger sub-list which should be in a sorted list. Until a n element single list is obtained.
Code in C

void msort(int a[], int low, int high)
{
 void merge(int a[], int, int, int);
 int mid;
 if(low < high){
 mid = (low + high)/2;
 msort(a, low, mid);
 msort(a, mid+1, high);
 merge(a,low,high,mid);
 }
}

void merge(int a[], int low, int high, int mid)
{
 int i,j,k, c[50];
 i = low;
 j = mid + 1;
 k = low;
 while((i <= mid) && (j <= high)){
 if(a[i] < a[j])
 c[k++] = a[i++];
 else
 c[k++] = a[j++];
 }
 while(i <= mid)
 c[k++] = a[i++];
 while(j <= high)
 c[k++] = a[j++];
 for(i = low; i < k; i++)
 a[i] = c[i];
}

Time Analysis

Worst case : O(n log n)

Best case : O(n log n)

Average case : O(n log 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: