Quick Sort

      No Comments on Quick Sort

Quick Sort is partial application of divide and conquer algorithm design technique. It is partial application because there is no step for combining.

Quick Sort

  • It is an in-place sorting technique. This means sorting of the array takes place within the same array.
  • It is an unstable sorting algorithm as the relative ordering of same elements changes during sorting.
  • Quick Sort uses partition algorithm.Array is sorted recursively.

Partition Algorithm

Algorithm:
This algorithm takes array of ‘n’ elements as input along with starting and ending index.

partition(A,i,j)
{
   x=A[i]; //setting pivot point as first element in array
   l=i;    // left iterator initialized to starting index.
   for(int r=i+1;r<=j;r++) //iterate for i+1 to ending index
   {
      if(A[r]<=x)  // check is element at 'r' index is less than equal to element at pivot
      {
          l=l+1;   // if condition validates increment left iterator
          swap(A[r],A[l]); // swapping elements
      }
   }
   swap(A[i],A[l]);
   return l; //return position of left iterator i-e partition point
}

Time complexity:
Time complexity of partition algorithm depends on number of swaps and comparisons made.
In best case number of swaps = 1 where the array is in ascending order and number of comparisons = n-1. Therefore, TC=n-1 + 1 =O(n).
In worst case number of swaps = n-1 where the array is in decreasing order and number of comparisons = n-1. Therefore, TC=n-1 + n-1 =O(n).

Quick Sort algorithm:

Algorithm:

quciksort(A,i,j)
{
  if(i==j) // only 1 element in array
  return A[i];  -----> O(1)
  else
  {
   x=partition(A,i,j); ---->O(n)
   quicksort(A,i,x-1) ----> T(x-i) //conquer
   quicksort(A,x+1,j) ----> T(j-x) //conquer
   return A;  --->O(1)
}

Time complexity:
Let T(n) be the time complexity of quick sort algorithm for array of ‘n’ elements then,
T(n) = T(x-i)+T(j-x)+n
In best case, partition algorithm divides the array into exactly two parts.

 T(n)=T(n/2)+T(n/2-1)+n
     =2T(n/2)+n
     solving recurrence relation 
 T(n)= n + nlogn
     =O(nlogn)

In worst case, partition algorithm divides the array into two parts of size 1 and n-1.

 
 T(n)=T(n-1)+n
     =T(n-2)+n-1+n
     |
     | n-1 times
     |
     =T(1)+2+3......+n-2+n-1+n
     =n(n+1)/2
     =O(n^2)

Summary
Quick Sort
Article Name
Quick Sort
Description
Quick Sort is partial application of divide and conquer algorithm design technique. It is partial application because there is no step for combining.It is an in-place sorting technique. This means sorting of the array takes place within the same array. It is an unstable sorting algorithm as the relative ordering of same elements changes during sorting.Quick Sort uses partition algorithm.Array is sorted recursively.
Author
Publisher Name
Scanfcode
Publisher Logo

Leave a Reply

Your email address will not be published. Required fields are marked *