Quick Sort Algorithm

Look at the following array

90 100 20 60 80 110 120 40 10 30 50 70

0 = left

nElemn-1 =right

First we take a value from array and stored in a temp variable. Normally it is the rightmost element. We called it pivot value.

pivot = array[right]

1.We take 70 out from the array as pivot value.

90 100 20 60 80 110 120 40 10 30 50

2.Assign two pointer variables ptrLeft and ptrRight and assign initial values.

ptrLeft = left-1

ptrRight = right

*                                

90 100 20 60 80 110 120 40 10 30 50

3.Increase prtLeft by 1 and check whether array[ptrLeft] < pivot. If it is, Increase ptrLeft by 1. This will continue until array[ptrLeft] >= pivot.

4. When array[ptrLeft] >= pivot stop increasing ptrLeft. Decrease ptrRight by 1 and check whether 

array[ptrRight] > pivot. If it is, decrease the ptrRight by 1. Continue reducing ptrRight untill  

array[ptrRight] <=  pivot.

*                                *

90 100 20 60 80 110 120 40 10 30 50

If prtRight > ptrLeft , swap array[ptrLeft] and array[ptrRight]. Else
If  ptrRight <= ptrLeft, swap pivot and ptrLeft.

Finally breakdown the array to two parts (from 0 to ptrLeft-1) and (from ptrLeft+1 to right).

Apply the same rules to both sub arrays  until the array divide into single elements. 

The complete procedure

90 100 20 60 80 110 120 40 10 30 50 70

Takeout 70 as pivot value. Increase ptrLeft by 1. array[ptrLeft]=90 now(ptrLeft=0 now). 90 > 70. Stop increase ptrLeft.

*                                

90 100 20 60 80 110 120 40 10 30 50

Reduce ptrRight by 1. array[ptrRight]=50 now(ptrRight=10 now). 50 < 70.Stop reduce ptrRight.

*                                *

90 100 20 60 80 110 120 40 10 30 50

Swap array[ptrLeft] and array[ptrRight].  (swap 90 and 50). Increase ptrLeft by 1. 100 > 70. Stop increase
ptrLeft.

    *                            *

50 100 20 60 80 110 120 40 10 30 90

Reduce ptrRight by 1. 30 < 70. Stop reduce ptrRight. 

    *                         *  

50 100 20 60 80 110 120 40 10 30 90

Swap array[prtLeft] and array[ptrRight] .(because ptrRight > ptrLeft) and again increase ptrLeft by 1. 

      *                       *

50 30 20 60 80 110 120 40 10 100 90  ->

20 < 70. Continue increasing ptrLeft.

         *                    *

50 30 20 60 80 110 120 40 10 100 90  ->

60 < 70. Continue increasing ptrLeft. 80 > 70. Stop increasing ptrLeft. Reduce ptrRight by 1.

            *                 *

50 30 20 60 80 110 120 40 10 100 90

100 > 70. Continue reducing ptrRight. 10 < 70. Stop reducing ptrRight.

            *             *

50 30 20 60 80 110 120 40 10 100 90

Swap array[ptrLeft] and array[ptrRight]. So swap 80 and 10.(because ptrLeft < ptrRight) and again increase ptrLeft by 1. 110 > 70. Stop increase ptrLeft and Reduce ptrRight by 1. 

                *         *

50 30 20 60 10 110 120 40 80 100 90

80 > 70. Continue reducing ptrRight. 40 < 70. Stop reducing ptrRight. 

                *      *

50 30 20 60 10 110 120 40 80 100 90

Swap array[ptrLeft] and array[ptrRight]. So swap 110 and 40. (because ptrRight > ptrLeft). Again increase
ptrLeft by 1. 120 > 70. Stop increase ptrLeft  and  reduce ptrRight by 1.  

                   *   *

50 30 20 60 10 40 120 110 80 100 90

ptrRight is 120 now. 120 > 70. Continue reducing ptrRight. 

                   **

50 30 20 60 10 40 120 110 80 100 90  <-

ptrRight is 40 now. 40 < 70. Stop reduce ptrRight. 

               *   *

50 30 20 60 10 40 120 110 80 100 90

Swap array[ptrLeft] and pivot. (because ptrRight < ptrLeft)

50 30 20 60 10 40 70 110 80 100 90 120

Divide array into two parts. (0 to ptrLeft-1) and (ptrRight+1 to nElemns-1)

50 30 20 60 10 40                               110 80 100 90 120

Do the same procedure to two sub arrays................

*

50 30 20 60 10

*           *

50 30 20 60 10

   *        *

10 30 20 60 50  ->

      *     *

10 30 20 60 50  ->

         *  *

10 30 20 60 50

         **

10 30 20 60 50  <-

      *  *

10 30 20 60 50

10 30 20 40 50 60

10 30 20            50 60

*

10 30 ->

   *

10 30

   **

10 30  <-

*  *

10 30

10 20 30

50 60

*

50            ->

    *

50   

50  60

110 80 100 90 120

*

110 80 100 90

*          *

110 80 100 90

   *       *

90 80 100 110   ->

       *   *

90 80 100 110   ->

           **

90 80 100 110   ->

           *   *

90 80 100 110

90 80 100 110 120

90 80 100 110

*

90 80 100       ->

   *

90 80 100       ->

       *

90 80 100       ->

            *

90 80 100

90 80 100 110

Java code for Quick Sort

public class QuickArray {

double quickArr[];

int nElemns;

public QuickArray(int size){

        quickArr=new double[size];

        nElemns=0;

}

public void insert(double value){

        quickArr[nElemns++]=value;

}

public void dsply(){

        for(int i=0;i<nElemns;i++)

               System.out.print(quickArr[i]+" ");

        System.out.println();

}

public void QuickSort(){

        recQuickSort(0,nElemns-1);

}

private void recQuickSort(int left, int right) {

       

        if(right-left<=0)

               return;

        else{

               int margine=doBreak(left,right);

               recQuickSort(left,margine-1);

               recQuickSort(margine+1,right);

        }

       

}

private int doBreak(int left, int right) {

        double pivot=quickArr[right];

        int leftPtr=left-1;

        int rightPtr=right;

       

       

        while(true){

              

               while(quickArr[++leftPtr]<pivot){

                       System.out.println("->");

                       }

               while(rightPtr>0 && quickArr[--rightPtr]>pivot){

                       System.out.println("<-");

               }

              

               if(rightPtr-leftPtr<=0)

                       break;

               else{

                       swap(rightPtr,leftPtr);

               }

        }

       

        swap(leftPtr,right);

       

        return leftPtr;

}

private void swap(int rightPtr, int leftPtr) {

        double temp=quickArr[rightPtr];

        quickArr[rightPtr]=quickArr[leftPtr];

        quickArr[leftPtr]=temp;

       

}

}

The Runner Class

public class Runner {

        /**

         * @param args

         */

        public static void main(String[] args) {

               QuickArray qarr=new QuickArray(12);

               qarr.insert(90);

               qarr.insert(100);

               qarr.insert(20);

               qarr.insert(60);

               qarr.insert(80);

               qarr.insert(110);

               qarr.insert(120);

               qarr.insert(40);

               qarr.insert(10);

               qarr.insert(30);

               qarr.insert(50);

               qarr.insert(70);

              

               qarr.dsply();

               qarr.QuickSort();

               qarr.dsply();

        }

}

The Output should like this

I put " -> " and " <- " to identify occasions that the conditions are true. I put same marks in the above procedure. 

Please comment if you need any clarifications :)