quick sort - as the name goes

Quick sort is one of the fastest sorting algorithms and easy to implement.The idea goes like this

First divide the array into 2 parts where the elements of the second part are all more than that of the first part.Now we have to sort the 2 parts to make the array sorted.Apply the same algo to the 2 parts so as to sort them.Done the array is sorted.

To divide into 2 such parts first choose an alement popularly called as the pivot element.For instance choose the middle element as pivot element

Have 2 pointers (i and j)pointing to the first and the last element of the array

Search for the element in the first part greater than the pivot element.Similarly search for an element in the second part less than the pivot(These could be even the first or last)
if i <= j swap(a[i],a[j])
Then continue after the same stuff incrementing i and decrementing j

Thus at the end we have two parts one which is totally less than the pivot element and one which is more than the pivot element.

The pseudo code is as below


void quicksort (int[] a, int low, int hi)
{

int i=low, j=hi, h;
int x=a[(low+hi)/2];

// partition
do
{
while (a[i] while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);

if (low < j) quicksort(a, low, j);
if (i < hi) quicksort(a, i, hi);
}

as one can see the complexity totally depends on the pivot element chosen for that array.Suppose the first half of the array is more than the pivot and the second half is less and as fate has it we have chosen the middle element to be the pivot.Then we have to exchange all the elements of both the halfs.So complexity increases here.

Analysis:
The best case happens when the 2 parts have equal number of elements.This does not really depend upon whether the pivot is the middle element.For eg in the sequence
9 8 7 5 2 3 6 8 4 7.If we choose the pivot to be 2 then the first half will have 1 element that is the pivot and the othet half will have the other elements.So choosing pivot is either luck factor or we shud have an idea about the occurence of the order.

If we know that the array will always be more or less in an ascending order then we can choose the pivot in the middle.

Now if tge 2 prts have equal number of elements then the complexity is log(n) times n
Since we go thru the array once to divide it and we have log(n) such divisions

Thus the complexity is nlog(n) - best case

If as said one part has one element and the other has remaining then the complexity is n*n = n2 since there will be nearly n parts and n time complexity for each part
so worst case is n2

Thanks,
Prasanna

Merge - sort The divide and conquer way

Merge sort is one of the qucik sorting alogorithms that uses the Divide and conquer strategy and programmatically recursion

This is how it goes

The array that has to be sorted is divided into 2 halfs.each of these 2 halfs are sorted independently.Now these 2 halfs are merged to give the full sorted array.As one can easily claim the two independent halfs are again sorted using the same mergesort algorithm wherein they are divided into 2 more halfs and so on.....the recursion ends when the divided half contains only one element....
Now the most important part is to merge the 2 sorted halfs into a sorted array of elements.

This is the pseudo code for the recursive mersort function

void mergesort(int low, int hi)
{
   if (low < hi)
   {
       int middle=(low+hi)/2;
       mergesort(low, m);
       mergesort(middle+1, hi);
       merge(lo, middle, hi);
   }
}

We find the middle elemsnt and divide the array into 2 halfs.Then recursively aply the same algorithm for the 2 halfs.
As stated above the recursion stops when low = hi or there is only one element in the array i.e low and hi coincide to be same.

Now the more important part is the merge function.Lets see how it goes
The efficient way of implementing this goes here

We have to use an other auxiliary array B which is atleast as big as the first half

Now copy the elements of the first half of the array a to b.Now compare the elements of first half in b and the second half in a one by one
Whichever is smaller is copied on to the next position in a.End the loop when we reach the end of either of the half

Analysis:
As we can see we have to implement the function merge log(n) times.
Now the function merge requires at the max copying it to the auxiliary array once and copy it back to the original array,Thus 2n times
Thus the total time complexity is 2nlog(n) i.e of the order nlog(n).This is very  scalable
That is why mergesort is one of the earlier winners in the sorting contest

Thanks,
Prasanna


}