Quick Sort: Quick Sort is the most popular sorting algorithm.In the majority of situations ,it is fastest,operating in O(N*logN) time . This is only true for internal or int-memory sorting;for sorting data in disk files.to understanding you should be familiar with the partitioning algorithm.Basically the quick-sort algorithm operates by partitioning an array in two two sub-arrays and then calling itself recursively to quick-sort each of these sub-arrays Quick Algorithm: There are 3 basic steps. Partitioning the array or sub-array into left(smaller keys) and right(larger keys) groups.
Call ourselves to sort the left group
Call ourselves again to sort the right groups.
Choosing a Pivot Value:
The pivot value should be the key value of an actual data items;this item is called the pivot.
you can pick a data item to be the pivot more or less at random.for simplicity,lets say we always pick the item on the right end of the sub-array being partitioned.
After the partition,if the pivot is inserted at the boundary between the left and right sub arrays ,it will be in its final sorted position.
Code Example:
/**
*
*/
/**
* @author Abhinaw.Tripathi
*
*/
class ArraysIns
{
private long[] theArray;
private int nElems;
public ArraysIns(int max)
{
theArray =new long[max];
nElems=0;
}
public void insert(long values)
{
theArray[nElems] =values;
nElems++;
}
public void display()
{
System.out.println("A=");
for(int j=0;j<nElems; j++)
System.out.println(theArray[j]+ " ");
System.out.println(" ");
}
public void swap(int dex1,int dex2)
{
long temp;
temp=theArray[dex1];
theArray[dex1]=theArray[dex2];
theArray[dex2]=temp;
}
public int partitionIt(int left,int right,long pivot)
{
int leftptr=left-1;
int rightPtr=right+1;
while(true)
{
while(leftptr <right && theArray[++leftptr] <pivot);
while(rightPtr>left && theArray[--rightPtr] > pivot);
if(leftptr >=rightPtr)
break;
else
swap(leftptr, rightPtr);
}
return leftptr;
}
public void recursiveSort(int left,int right)
{
if(right-left <=0)
return;
else
{
long pivoit=theArray[right];
int partition=partitionIt(left, right, pivoit);
recursiveSort(left, partition-1);
recursiveSort(partition+1, right);
}
}
public void quickSort()
{
recursiveSort(0, nElems-1);
}
}
public class QuickSortApp {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ArraysIns arr =new ArraysIns(16);
for(int j=0;j<10;j++)
{
long n=(int)(java.lang.Math.random()*99);
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
Efficiency of Quick Sort: O(N*logN)