Quick Sorting Algorithm -

This is the one of the most in use sorting algorithm. This sorting algorithm provides a way to each element to arrange themselves. Every element finds their own place in the list.

Each list will be partitioned into smaller lists, left list holds less elements and right part hold greater elements. This algorithm is based on divide and conquer method.

Quick sort is the faster sorting algorithm and preferable for large amount of data elements.  Average time complexity of quick sort is O(n log n) and worst case complexity is O(n2).

In quick sort we pick any element and call it as pivot.

We will find pivot sorted position in the list, again select another element as pivot and finds its sorted position, this process will be continue until we get all element's sorted positions in the list.

Assuming we have list of 8 elements ...

STEP - 1

In the mentioned array list - 20, 2, 8, 39, 67, 5

I am taking 20 (first element of list ) as pivot.

pivot

20, 2, 8, 39, 67, 5

STEP - 2

Quick sort algorithm divides list on the basis of pivot value, left part of the list will have elements that are smaller than pivot and right part will have elements that are greater than pivot and at last will get the position of pivot in the list.

Again same process (selecting pivot, arranging elements, and get pivot position) will be continue with left and right side list recursively.

Let's understand quick sort with example - 20, 2, 8, 39, 67, 5

Rule - 1
Running two loops i and j, i will read from left and j will read from right i.e index = 5.

Rule - 2
Compare elements with pivot element <pivot element will be in left side of list and >pivot will be in right side of list.

Rule - 3

If small element swap with pivot then i counter will be incremented by 1.
If greater element swap with pivot element  then j counter will be decremented
by 1.

Rule - 4

Do comparing until i , j and pivot index are equal at this condition we will get sorted pivot index.

Quick Sort Method -
``````
pivot

````Array List````   - 20, 2, 8, 39, 67, 5

i=0              j=5

i = 0 , j = 5  ,  if (pivot < array[j] ) 20  < 5 = False

``````
Small element is swapping with pivot i.e. i will be incremented by 1.
``````

pivot

Array List   - 5, 2, 8, 39, 67, 20

i=1          j=5

i = 1 , j = 5, if if (pivot >array[i] ) 20 > 2 = True

````Element already sorted no swapping required. Increment i by 1.````

pivot

Array List   - 5, 2, 8, 39, 67, 20

i=2       j=5

i = 2 , j = 5  , if (pivot >array[i] )  20 > 8 = True

````Element already sorted no swapping required. Increment i by 1.````

pivot

Array List   - 5, 2, 8, 39, 67, 20

i=3    j=5

i = 3 , j = 5  , if (pivot >array[i]) 20 > 39 = False

``````Greater element is swapping with pivot i.e. j will be decremented by 1.
``````

pivot

Array List   - 5, 2, 8, 20 67, 39

i=3 j=4

i = 3 , j = 4 ,  if (pivot < array[j]) 20 < 67= True

``````Element already sorted no swapping required. decremented j by 1
``````

pivot

Array List   - 5, 2, 8, 20 67, 39

i=3

j=3

````i = 3, j = 3 ,pivot index = 3 i.e. we got the sorted position of pivot.````

Sorted List- 5, 2, 8, 20 67, 39

Now divide the list into two small parts,

``````left list from 0 to pivot position  - 5, 2, 8, 20 .
``````

````right list from pivot position+1 to list size. -  67, 39````

will send left list and right list to the quick sort process recursively.

Let's start with left side list, i=0 is the pivot element.

pivot

Array List   - 5, 2, 8, 20

i=0      j=3

i = 0, j = 3  , if (pivot < array[j] ) 5 < 20 = True

````Element already sorted no swapping required, decrements  j by 1.````

pivot

Array List   - 5, 2, 8, 20

i=0  j=2

i = 1, j = 2  ,  if (pivot < array[j] ) 5 < 8 = False

````Element already sorted no swapping required, decrements  j by 1.````

pivot

Array List   - 5, 2, 8, 20

i=0 j=1

i = 0, j = 1  ,  if (pivot < array[j] ) 5 < 2 = True

````Small element is swapping with pivot i.e. i will be incremented by 1.````

pivot

Array List   - 2, 5, 8, 20

i=1

j=1

````i = 1, j = 1 ,pivot index = 1 i.e. we got the sorted position of pivot.````

Sorted Left Side List - 2, 5, 8, 20

Next, Right side list, i=0 is the pivot element.

pivot

Array List   - 67, 39

i=0  j=1

i = 0, j = 1  ,  if (pivot < array[j] ) 67 < 39 = False

````Small element is swapping with pivot i.e. i will be incremented by 1.````

pivot

Array List   - 39, 67

i=0

j=0

````i = 1, j = 1 ,pivot index = 1 i.e. we got the sorted position of pivot.````

Sorted Right Side List - 39,67

Final List is  -  2, 5, 8, 20,39,67

``````

Quick Sort Implementation In Java –

``````

public class ````QuickSortingExample ````{

public static int pivot = 0;

public static int pivot_index = 0;

````public static void main(String []args) {````

System.out.println("Quick Sorting Algorithm Starts ...\n");

int array[] = {20,2,8,39,67,5};

int size = 6;

// sending array and size

array = quickSortingMethod (array,0,size);

if (!isSorted(array,0, size)) {

System.out.println("\nList is not sorted yet. " );

System.out.println ("\nDivide List in two small parts,

left list from 0 to pivot_index and right list from

pivot_index+1 to array size");

System.out.println ("\nLeft list - ");

printList(array,0,pivot_index+1);

System.out.println ("\nRight list - ");

printList(array,pivot_index+1,size);

System.out.println("\nSending left list to quickSorting

method to be sorted");

int previous_pivot = pivot_index;

quickSortingMethod(array,0,pivot_index+1);

quickSortingMethod(array,previous_pivot+1,size);

}

System.out.println("Congrats your list is sorted \n " );

printList(array,0,size);

} // end of main

````public static int[] quickSortingMethod(int array[],int initial,int size){````

// Get pivot value

pivot = array [initial];

pivot_index = initial;

int i =initial;

int j = size-1;

System.out.println("\nList is = ");

printList (array,initial,size);

System.out.println ("\nPivot = " +pivot);

while (i != j) {

int temp ;

System.out.println ("\ni =" +i  + " j = "+j+"\n");

if ( pivot > array [j]) {

System.out.println (pivot +" > "+array [j]

+ ", swap elements\n");

temp = array [j] ;

array[j] = pivot;

array[pivot_index] = temp;

pivot_index = j;

printList (array,initial,size);

System.out.println ("\nSmall element is swapping with

pivot, i will be incremented by 1. \n");

i++;

}

else if ( pivot < array [i]) {

System.out.println (pivot +" < "+array [i]

+ ", swap elements\n");

temp = array [i] ;

array[i] = pivot;

array[pivot_index] = temp;

pivot_index = i;

printList (array,0,size);

System.out.println ("\nGreater element is swapping

with pivot, j will be decremented by 1. \n");

j--;

}

else {

System.out.println (array [i] +" < "+pivot+"\n");

System.out.println ("Element is already sorted.");

}

if( pivot < array [j]) {

j--;

}

if(pivot > array[i]) {

i++;

}

if ( i == j) {

System.out.println ("\n i = j = pivot_index , at this point

loop will be end because we got thepivot sorted position.");

break;

}

} // end of while

System.out.println("\nProcess completed updated list is \n " );

printList(array,initial,size);

return array;

````}```` // end of quickSortingMethod

``````public static void printList (int array[],int intial,int size) {
``````

for (int i=intial;i<size-1;i++) {

if (array [i] < array [i+1])

counter ++;

}

if (counter == size) return true;

return false;

````}````// end of isSorted Method

}// end of class
``````