Quick sort is based on the divide & conquer sorting technique. It was developed by Tony Hoare in 1960. In this sorting technique, the elements of arrays are divided into two smaller arrays. Quick sort is a type of In-Place sorting.

In this sorting, firstly, one element is selected from the list, which is called a pivot element. All elements that are smaller than the pivot value remain on the left side of the array, and all elements that are larger than the pivot value remain on the right side of the array. The worst-case complexity of quick-sort is very low, so it is very fast and efficient.

Complexity table of Quick sort

ComplexityBest caseAverage caseWorst case
TimeO(nlogn)O(nlogn)O(n2)
Space  O(nlogn)

Quick sort algorithm

Step 1: Select an element in the array list which is call pivot value.

Step 2: Arrange the array elements in such a way that all those elements which are smaller than pivot value remain on the left side of the array, and all those elements which are larger than pivot value remain on the right side of the array.

Step 3: Both parts of the array are again sorted using the quick sort algorithm.

Partition algorithm

Example of Selection sort

Suppose we have the following array, which we have to sort.

1182196

  Given,            

p = 1, r = 6            

x = A[r] = 6            

i ← 1 -1 = 0            

j ← 1 to 9  

Step 1:  j = 1             

If A[j] < x             

        11 < 6  // false  

Step 2: j = 2        

     If A[j] < x        

           A[2] < x           

          8 < 6 // false

Step 3: j =3        

     If A[j] < x        

          A[3] < x          

           2 < 6 // true      

      i = i + 1,            i = 1  

  Step 4 : j = 4       

        If A[j] < x       

             A[1] < x          

             1 < 6 // true       

          i = i + 1                 i = 2  

  Step 5: j = 5     

        If A[j] < x       

           A[5] < x       

           9 < 6 // false  

Step 6: Swap A[i + 1] and A[r]

Quick sort

    Quicksort(A, 1, 2) Quicksort(A, 4, 6)  

Program of Quick sort in C language

Output

Program of Quick sort in java language

Output

Pin It on Pinterest

Share This