### 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.

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: