Quick Sort Method

Quick Sort Method

Description: 
Also known as Partition Exchange Method because it sorts data by partitioning the the array / list into two sub arrays / lists. Each partition is in turn sorted recursively. In each step, the goal is
to place a particular data known as key in its final position. In general, key element is the first data of an array / list and rest of the data grouped into  such that

i. One partition contains data smaller than the key value.

ii. Another partition contains data larger the key value.

Example:

Consider following elements, the quick sort
method to sort data in ascending order is

44,33,11,55,77,90,40,60,99,22,88,66

Step 1: Key is 44.
The First step is as follows

i. Scan: Right to Left

• stop when find first number less than key, 44
• 22
• Data after interchange: 22,
  33,11,55,77,90,40,60,99,44,88,66

ii. Left to Right

• stop when find first number greater than key, 44
• 55
• Data after interchange:: 22,33,11,44,77,90,40,60,99,55,88,66

iii. Right to Left

• stop when find first number less than key, 44
• 40
• Data after interchange:: 22, 33,11,40,77,90,44,60,99,55,88,66

iii. Left to Right

• stop when find first number greater than key, 44
• 77
• Data after interchange:: 22,33,11,40,44,90,77,60,99,55,88,66

so the list can be partitioned into two sub list

Sub Part 1: 22,33,11,40. 

Sub Part 2: 90,77,60,99,55,88,66.  

Step 2: Repeat
same steps on Sub Part1 with
key as 22

Step 3: Repeat
same steps on Sub Part2 with
key as 99

and so on

Efficiency:

• Worst Case:: O(n²) 
• Best case performance    O(n log n)  
• Average case performance    O(n log n)

Algorithm

Quicksort (int data[],int left,int right) 

{

int mid,tmp,i,j;

i = left;

j = right;

mid = data[(left + right)/2];

do 

{

     while(data[i] < mid)

         i++;

      while(mid < data[j])

         j--;

      if (i <= j) 

     {

            tmp = data[i];

            data[i] = data[j];

            data[j] = tmp;

            i++;

            j--;

     }

} while (i <= j);

   

if (left < j) Quicksort(data,left,j);

if (i < right) Quicksort(data,i,right);

}