Quick Sort

1. #include <iostream>
2. #include <algorithm>
3.  
4. void print(int *a, int n)
5. {
6. int i = 0;
7. while(i < n){
8. std::cout << a[i] << ",";
9. i++;
10. }
11. std::cout << "\n";
12. }
13.  
14. int partition(int *arr, const int left, const int right) {
15. const int mid = left + (right - left) / 2;
16. const int pivot = arr[mid];
17. // move the mid point value to the front.
18. std::swap(arr[mid],arr[left]);
19. int i = left + 1;
20. int j = right;
21. while (i <= j) {
22. while(i <= j && arr[i] <= pivot) {
23. i++;
24. }
25.  
26. while(i <= j && arr[j] > pivot) {
27. j--;
28. }
29.  
30. if (i < j) {
31. std::swap(arr[i], arr[j]);
32. }
33. }
34. std::swap(arr[i - 1],arr[left]);
35. return i - 1;
36. }
37.  
38. void quicksort(int *arr, const int left, const int right, const int sz){
39.  
40. if (left >= right) {
41. return;
42. }
43.  
44.  
45. int part = partition(arr, left, right);
46. std::cout << "QSC:" << left << "," << right << " part=" << part << "\n";
47. print (arr, sz);
48.  
49. quicksort(arr, left, part - 1, sz);
50. quicksort(arr, part + 1, right, sz);
51. }
52.  
53. int main() {
54. int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
55. int sz = sizeof(arr)/sizeof(arr[0]);
56. print(arr, sz);
57. quicksort(arr, 0, sz - 1, sz);
58. print(arr, sz);
59. return 0;
60. }