Quick Sort Algorithm

Quick Sort:

Quick Sort algorithm is based on divide-and-conquer approach, recursively processing small and small parts of array list at each level. Here is the three-step divide-and-conquer process for sorting a typical subarray A[p....r].

Divide:  Partition(rearrange) the array A[p ...r] into two sub-arrays A[p ...q-1] and A[q+1 ...r] such that each element of A[p...q-1] is less than and or equal to A[q], which is, in turn less than and or equal to A[q+1 ..r]. Compute the index q as part of this partitioning procedure.

Conquer: Sort the two subarray A[p ...q-1] and A[q+1 ..r] by recursive calls of quicksort.

Combine: Subarrays are sorted in place, no work is needed to combine them.

  Quick Sort algorithm chooses an element as a pivot. And partitions the given array around choose the pivot element. There are many ways to choose a pivot element for partition.
Always choose the first element as a pivot.
Always choose the last element as a pivot. Choose a random element as a pivot. Choose median as a pivot.

The key process in quickSort is partition(). The target of partitions is, given an array and an element x of the array as a pivot, put x at its correct position in the sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Ex: choose the last element as a pivot.

techie delight




Algorithm:

QUICKSORT(A, p, r)
  1. if  p < r
  2.   then q <-- PARTITION(A, p, r)
  3.         QUICKSORT(A, p, q-1)
  4.          QUICKSORT(A, q+1, r)       
 To sort an entire array A, the initial call is QUICKSORT(A, 1, length[A]).

Partition the array
the Key to the algorithm is PARTITION procedure, which rearranges the subarray A[p ...r] in place.

PARTITION(A, p, r)
  1. x <-- A[r]
  2. i <-- p-1
  3. for j <-- p to r -1
  4.    do if  A[j] <= x
  5.          then i <-- i+1
  6.                exchange A[i] <--> A[j]
  7. exchange A[i+1] <--> A[r]
  8. return i+1
T(n) = f(n) + T(q) + T(n-q-1)

T(n): Time complexity of Quicksort
T(n-q-1): Time complexity of left partition algorithm

T(q): Time complexity of right partition algorithm
f(n): Time complexity of partition algorithm

Best case: O( nlogn ) 
Worse case: O( n2 )


case 1: If element of array, already sorted in increasing order.
 ex:  1 < 2 <3 <4 <5          5 is pivot

n-q-1 = 0      q = n-1
                                     T(n) = T(n-1) + n ==> O( n2 )
case 2: If element of array, already sorted in decreasing order.
 ex:  5< 4< 3< 2< 1         1 is pivot

n-q-1 = n-1      q = 0
                                     T(n) = T(n-1) + n ==> O( n2 )

case 3: If Partition algorithm divides the array into two equal halves.

q=n-q-1       ==>>       q=(n-1)/2


           T(n) = T((n-1)/2) + T((n-1)/2) + n

        T(n) = 2 T((n-1)/2) + n

        T(n) = O( nlogn)



case 4: General case











      
                              

Comments

Popular posts from this blog

C program that contains a string XOR each character in this string with 0 ,127

Queue in Data Structure(DS)

Implementation of stack Using Array