Quick Sort example in core-java

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.

1. Partitioning the array or sub-array into left(smaller keys) and right(larger keys) groups.
2. Call ourselves to sort the left group
3. 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)