what is Quick Sort?

Quick Sort

Quick sort is the widely used sorting algorithm that makes n log n comparisons in average case for sorting of an array of n elements. This algorithm follows divide and conquer approach. The algorithm processes the array in the following way.

1. Set the first index of the array to left and loc variable. Set the last index of the array to right variable. i.e. left = 0, loc = 0, en d = n ? 1, where n is the length of the array.
2. Start from the right of the array and scan the complete array from right to beginning comparing each element of the array with the element pointed by loc.
Ensure that, a[loc] is less than a[right].

1. If this is the case, then continue with the comparison until right becomes equal to the loc.
2. If a[loc] > a[right], then swap the two values. And go to step 3.
3. Set, loc = right

1. start from element pointed by left and compare each element in its way with the element pointed by the variable loc. Ensure that a[loc] > a[left]
1. if this is the case, then continue with the comparison until loc becomes equal to left.
2. [loc] < a[right], then swap the two values and go to step 2.
3. Set, loc = left.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(n) for 3 way partition or O(n log n) simple partition	O(n log n)	O(n2)
Space Complexity			O(log n)

Algorithm

PARTITION (ARR, BEG, END, LOC)

• Step 1: [INITIALIZE] SET LEFT = BEG, RIGHT = END, LOC = BEG, FLAG =
• Step 2: Repeat Steps 3 to 6 while FLAG =
• Step 3: Repeat while ARR[LOC] <=ARR[RIGHT]
  AND LOC != RIGHT
  SET RIGHT = RIGHT - 1
  [END OF LOOP]
• Step 4: IF LOC = RIGHT
  SET FLAG = 1
  ELSE IF ARR[LOC] > ARR[RIGHT]
  SWAP ARR[LOC] with ARR[RIGHT]
  SET LOC = RIGHT
  [END OF IF]
• Step 5: IF FLAG = 0
  Repeat while ARR[LOC] >= ARR[LEFT] AND LOC != LEFT
  SET LEFT = LEFT + 1
  [END OF LOOP]
• Step 6:IF LOC = LEFT
  SET FLAG = 1
  ELSE IF ARR[LOC] < ARR[LEFT]
  SWAP ARR[LOC] with ARR[LEFT]
  SET LOC = LEFT
  [END OF IF]
  [END OF IF]
• Step 7: [END OF LOOP]
• Step 8: END

QUICK_SORT (ARR, BEG, END)

• Step 1: IF (BEG < END)
  CALL PARTITION (ARR, BEG, END, LOC)
  CALL QUICKSORT(ARR, BEG, LOC - 1)
  CALL QUICKSORT(ARR, LOC + 1, END)
  [END OF IF]
• Step 2: END

C Program

1. #include <stdio.h>  
2. int partition(int a[], int beg, int end);  
3. void quickSort(int a[], int beg, int end);  
4. void main()  
5. {  
6.     int i;  
7.     int arr[10]={90,23,101,45,65,23,67,89,34,23};  
8.     quickSort(arr, 0, 9);  
9.     printf("\n The sorted array is: \n");  
10.     for(i=0;i<10;i++)  
11.     printf(" %d\t", arr[i]);  
12. }  
13. int partition(int a[], int beg, int end)  
14. {  
15.       
16.     int left, right, temp, loc, flag;     
17.     loc = left = beg;  
18.     right = end;  
19.     flag = 0;  
20.     while(flag != 1)  
21.     {  
22.         while((a[loc] <= a[right]) && (loc!=right))  
23.         right--;  
24.         if(loc==right)  
25.         flag =1;  
26.         else if(a[loc]>a[right])  
27.         {  
28.             temp = a[loc];  
29.             a[loc] = a[right];  
30.             a[right] = temp;  
31.             loc = right;  
32.         }  
33.         if(flag!=1)  
34.         {  
35.             while((a[loc] >= a[left]) && (loc!=left))  
36.             left++;  
37.             if(loc==left)  
38.             flag =1;  
39.             else if(a[loc] <a[left])  
40.             {  
41.                 temp = a[loc];  
42.                 a[loc] = a[left];  
43.                 a[left] = temp;  
44.                 loc = left;  
45.             }  
46.         }  
47.     }  
48.     return loc;  
49. }  
50. void quickSort(int a[], int beg, int end)  
51. {  
52.       
53.     int loc;  
54.     if(beg<end)  
55.     {  
56.         loc = partition(a, beg, end);  
57.         quickSort(a, beg, loc-1);  
58.         quickSort(a, loc+1, end);  
59.     }  
60. }  

Output:

The sorted array is: 
23
23
23
34
45
65
67
89
90
101

Java Program

1. public class QuickSort {  
2. public static void main(String[] args) {  
3.         int i;  
4.         int[] arr={90,23,101,45,65,23,67,89,34,23};  
5.         quickSort(arr, 0, 9);  
6.         System.out.println("\n The sorted array is: \n");  
7.         for(i=0;i<10;i++)  
8.         System.out.println(arr[i]);  
9.     }  
10.     public static int partition(int a[], int beg, int end)  
11.     {  
12.           
13.         int left, right, temp, loc, flag;     
14.         loc = left = beg;  
15.         right = end;  
16.         flag = 0;  
17.         while(flag != 1)  
18.         {  
19.             while((a[loc] <= a[right]) && (loc!=right))  
20.             right--;  
21.             if(loc==right)  
22.             flag =1;  
23.             elseif(a[loc]>a[right])  
24.             {  
25.                 temp = a[loc];  
26.                 a[loc] = a[right];  
27.                 a[right] = temp;  
28.                 loc = right;  
29.             }  
30.             if(flag!=1)  
31.             {  
32.                 while((a[loc] >= a[left]) && (loc!=left))  
33.                 left++;  
34.                 if(loc==left)  
35.                 flag =1;  
36.                 elseif(a[loc] <a[left])  
37.                 {  
38.                     temp = a[loc];  
39.                     a[loc] = a[left];  
40.                     a[left] = temp;  
41.                     loc = left;  
42.                 }  
43.             }  
44.         }  
45.         returnloc;  
46.     }  
47.     static void quickSort(int a[], int beg, int end)  
48.     {  
49.           
50.         int loc;  
51.         if(beg<end)  
52.         {  
53.             loc = partition(a, beg, end);  
54.             quickSort(a, beg, loc-1);  
55.             quickSort(a, loc+1, end);  
56.         }  
57.     }  
58. }  

Output:

The sorted array is: 
23
23
23
34
45
65
67
89
90
101

C# Program

1. using System;  
2. public class QueueSort{  
3. public static void Main() {  
4.         int i;  
5.         int[] arr={90,23,101,45,65,23,67,89,34,23};  
6.         quickSort(arr, 0, 9);  
7.         Console.WriteLine("\n The sorted array is: \n");  
8.         for(i=0;i<10;i++)  
9.         Console.WriteLine(arr[i]);  
10.     }  
11.     public static int partition(int[] a, int beg, int end)  
12.     {  
13.           
14.         int left, right, temp, loc, flag;     
15.         loc = left = beg;  
16.         right = end;  
17.         flag = 0;  
18.         while(flag != 1)  
19.         {  
20.             while((a[loc] <= a[right]) && (loc!=right))  
21.             right--;  
22.             if(loc==right)  
23.             flag =1;  
24.             else if(a[loc]>a[right])  
25.             {  
26.                 temp = a[loc];  
27.                 a[loc] = a[right];  
28.                 a[right] = temp;  
29.                 loc = right;  
30.             }  
31.             if(flag!=1)  
32.             {  
33.                 while((a[loc] >= a[left]) && (loc!=left))  
34.                 left++;  
35.                 if(loc==left)  
36.                 flag =1;  
37.                 else if(a[loc] <a[left])  
38.                 {  
39.                     temp = a[loc];  
40.                     a[loc] = a[left];  
41.                     a[left] = temp;  
42.                     loc = left;  
43.                 }  
44.             }  
45.         }  
46.         return loc;  
47.     }  
48.     static void quickSort(int[] a, int beg, int end)  
49.     {  
50.           
51.         int loc;  
52.         if(beg<end)  
53.         {  
54.             loc = partition(a, beg, end);  
55.             quickSort(a, beg, loc-1);  
56.             quickSort(a, loc+1, end);  
57.         }  
58.     }  
59. }  

Output:

The sorted array is: 
23
23
23
34
45
65
67
89
90
101