C++: Implementation of Quicksort (Sorting)

I have studied this algorithm from Introduction to Algorithm and if you want to learn Data Structure and Algorithm I would strongly recommend this book.

Quicksort applies Divide and Conquer paradigm.

Divide: Partition the array A[p…r] into two subarrays A[p…q-1] and A[q+1…r] such that each element of A[p...q-1] is
less than or equal to a[q] which is, in turn, less than or equal to each element
of  A[q+1…r]

Conquer: Sort the two subarrays A[p…q-1] and A[q+1…r]by recursive calls
to quicksort

Combine: Because the subarrays are already sorted, no work is needed to combine them the entire array A[p...r] is now sorted.
1. #include <iostream>2.3. int partition(int a[],int start_index,int end_index){4. int x=a[end_index];5. int i=start_index-1;6. for(int j=start_index;j<end_index;j++){7.    if(a[j]<=x){8.        i++;9.      int temp=a[i];10.      a[i]=a[j];11.      a[j]=temp;//swap(a[i],a[j])12.    }13. }14. int temp=a[i+1];15. a[i+1]=a[end_index];16. a[end_index]=temp;//swap(a[i+1],a[end_index])17.18. return i+1;19. }20.21. void quicksort(int a[],int start_index,int end_index){22. if(start_index<end_index){23.    int mid_index=partition(a,start_index,end_index);24.                quicksort(a,start_index,mid_index-1);25.                quicksort(a,mid_index+1,end_index);26. }27. }28.29. int main()30. {31.  int arr[8]={2,8,7,1,3,5,6,4};32.    quicksort(arr,0,7);33.    for(int i=0;i<8;i++){34.        std::cout<<arr[i]<<" ";35.    }36.    return 0;37. }

Running time of partition is Θ(n)

Worst case running time of algorithm when the partition is unbalanced means partition procedure produces one subarray of n-1 elements and other of 0 elements  that is unbalanced partitioning.Then its running time is 

Best case running time is when there is balanced partitioning. Then its running time is 

(n lg n).

The version of partition algorithm I have used above is not original partitioning algorithm. The original partition algorithm was given by C.A.R. Hoare. Use it in your program.

1. x=A[p]
2. i=p-1
3. j=r+1
4. while TRUE
5.      repeat
6.         j=j-1
7.      until
8.      repeat
9.         i=i-1
10.     until A[i]>=x
11.     if i<j
12.        exchange A[i]with A[j]
13     else return j


You may also like:
C++ STL :Implementation of Counting sort
C++: Implementation of Heapsort
C++: Insertion Sort using STL (Sorting)
C++: Implementation of Merge Sort
C++:Program to find prime factor of given no.

Popular Posts

C++: Selection sort using STL

Top 10 Web Sites Every Programmer Should Visit Daily