Partitioning: Partitioning is the underlying mechanism of quick sort.It is also useful operation on its own.To partitioning data is to divide it into two groups so that the items with a key value higher than a specified amount are in one group and all the items with a lower key value are in another. Code Example: /** * @author Abhinaw.Tripathi * */ class ArrayPar { private long[] theArray; private int nElems; public ArrayPar(int max) { theArray =new long[max]; nElems=0; } public void insert(long values) { theArray[nElems] =values; nElems++; } public int size() { return 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 class PartitionApp { public static void main(String[] args) { ArrayPar arr=new ArrayPar(16); for(int j=0;j<10;j++) { long n=(int)(java.lang.Math.random()*99); arr.insert(n); } arr.display(); long pivot=71; System.out.println("Pivot is :"+pivot); int size=arr.size(); int partDex=arr.partitionIt(0, size-1, pivot); System.out.println("partition is at the index"+partDex); arr.display(); } }
Efficiency of the Partition Algorithm:
It runs in O(N) time