Quick Sort Algorithm

Lets see yet another algorithm of sorting items.This time the quick sort which is one of the faster(though not the fastest) but the most popular sorting technique.This is used my most of the programmers.This is because although the worst case time of quicksort is theta(n^2) the average case complexity is remarkable ..theta(n lg n).where lg is of base 2.So lets see how it works.
Quick sort like merge sort works on the divide and conquer approach.Let an array A[p..r] be available for sorting:
divide-partion the array A into two(possibly empty) subarrays A[p..q-1] and A[q+1..r] such that all items in subarray A[p..q-1] are less than A[q] and all elements in A[q+1..r] are greater than A[q].So we have to compute the index q in this procedure as well.
Conquer-Here we sort the two sub-arrays by recursive method.
Conquer- Since the two sub-arrays are already sorted nothing's to be done here.

I think the more important part is the division part.So lets take that first:
Let the method Partition(A,p,r) take array A and the starting and ending indices p and r as arguments.What we do is that we make the last element of the array (i.e. a[r]) as a pivot and we compare each of the previous elements,thus finding the correct position of element a[r].The procedure looks like this-

Partition(A,p,r)
x=a[r]                      //make the last element a pivot
i=p-1                       //start from 1 step behind    
for j=p to r-1
     if a[j]<=x
          i=i+1             //counting the positions which are less than the pivot element 
          swap a[i] and a[j]
 exchange a[i+1] and a[r]  //put a[r] into postion q(its correct position.
return i+1                         // the position q.

The partioning procedure...All light shaded elements are less than the pivot and all deep shaded are greater than it.

Now we just have to make a recursive function that sorts the array with the help of the Partition method.

QuickSort(A,p,r)
if p<r
    q=Partition(A,p,r)
    QuickSort(A,p,q-1)
    QuickSort(A,q+1,r)

To sort the entire array the initial call should be QuickSort(A,1,A.length).The average case time complexity is theta(n lg n).How we get this ,I am going to discuss later in the  Complexity section.For now you can see the JAVA code in the respective section.