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 
\Theta(n^2)
.

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

\Theta(n^2)
(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.

HOARE_PARTITION(A,p,r)
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

Reference:




                                                                  
                                                                  
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

Top 10 Web Sites Every Programmer Should Visit Daily

What is "namespace" and why do we use it?