Posted By

acecengic on 12/17/14


Tagged

sort algorithm quick


Versions (?)

Quicksort


 / Published in: C++
 

quicksort algorithm in c++

  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. void printVector(vector<int> & h)
  8. {
  9. unsigned int i;
  10. // cout << "[";
  11. // for (i = 0; i < h.size() - 1; ++i)
  12. // {
  13. // cout << setfill(' ') << setw(2) << i << ",";
  14. // } // end for
  15. // cout << i << "]" << endl;
  16.  
  17. cout << "[";
  18. for (i = 0; i < h.size() - 1; ++i)
  19. {
  20. cout << setfill(' ') << setw(2) << h[i] << ",";
  21. } // end for
  22. cout << h[i] << "]" << endl;
  23. }
  24.  
  25. void printVector(vector<int> & h, int start, int end)
  26. {
  27. int i;
  28. cout << "[";
  29. for (i = start; i < start+end - 1; ++i)
  30. {
  31. cout << h[i] << ",";
  32. } // end for
  33. cout << h[i] << "]" << endl;
  34. }
  35.  
  36. /**
  37.  * Return median of left, center, and right.
  38.  * Order these and hide the pivot.
  39.  */
  40. template<typename Comparable>
  41. const Comparable & median3(vector<Comparable> & a, int left, int right)
  42. {
  43. int center = (left + right) / 2;
  44. cout << "In: " << a[left] << ", " << a[center] << ", " << a[right] << endl;
  45. if (a[center] < a[left])
  46. swap(a[left], a[center]);
  47. if (a[right] < a[left])
  48. swap(a[left], a[right]);
  49. if (a[right] < a[center])
  50. swap(a[center], a[right]);
  51. cout << "In: " << a[left] << ", " << a[center] << ", " << a[right] << endl;
  52.  
  53. // Place pivot at position right - 1
  54. printVector(a);
  55. swap(a[center], a[right]); //a[right - 1]
  56. printVector(a);
  57. return a[right]; // return a[right - 1];
  58. }
  59.  
  60. /**
  61.  * Internal insertion sort routine for subarrays
  62.  * that is used by quicksort.
  63.  * a is an array of Comparable items.
  64.  * left is the left-most index of the subarray.
  65.  * right is the right-most index of the subarray.
  66.  */
  67. template<typename Comparable>
  68. void insertionSort(vector<Comparable> & a, int left, int right)
  69. {
  70. cout << "starting insertion sort" << endl;
  71. printVector(a, left, right - left + 1);
  72. for (int p = left + 1; p <= right; p++)
  73. {
  74. Comparable tmp = a[p];
  75. int j;
  76.  
  77. for (j = p; j > left && tmp < a[j - 1]; j--)
  78. a[j] = a[j - 1];
  79. a[j] = tmp;
  80. }
  81. }
  82.  
  83. /**
  84.  * Internal quicksort method that makes recursive calls.
  85.  * Uses median-of-three partitioning and a cutoff of 10.
  86.  * a is an array of Comparable items.
  87.  * left is the left-most index of the subarray.
  88.  * right is the right-most index of the subarray.
  89.  */
  90. template<typename Comparable>
  91. void quicksort(vector<Comparable> & a, int left, int right)
  92. {
  93. cout << "In Quick Sort" << endl;
  94. printVector(a);
  95. if (left + 5 <= right)
  96. {
  97. Comparable pivot = median3(a, left, right);
  98. cout << "The Pivot is " << pivot << endl;
  99. // Begin partitioning
  100. int i = left, j = right; // -1;
  101. for (;;)
  102. {
  103. cout << "In for loop" << endl;
  104. while (a[++i] < pivot)
  105. {
  106. cout << "In i while" << endl;
  107. }
  108. while (pivot < a[--j])
  109. {
  110. cout << "In j while" << endl;
  111. }
  112. if (i < j)
  113. {
  114. swap(a[i], a[j]);
  115. cout << "swapped " << a[i] << " with " << a[j] << endl;
  116. printVector(a);
  117. }
  118. else
  119. break;
  120. }
  121. swap(a[i], a[right - 1]); // Restore pivot
  122.  
  123. // printVector(a);
  124. quicksort(a, left, i - 1); // Sort small elements
  125. quicksort(a, i + 1, right); // Sort large elements
  126. }
  127. else
  128. {
  129. // Do an insertion sort on the subarray
  130. insertionSort(a, left, right);
  131. }
  132. }
  133.  
  134.  
  135. /**
  136.  * Quicksort algorithm (driver).
  137.  */
  138. template<typename Comparable>
  139. void quicksort(vector<Comparable> & a)
  140. {
  141. quicksort(a, 0, a.size() - 1);
  142. }
  143.  
  144.  
  145.  
  146. int main()
  147. {
  148. vector<int> h(12);
  149.  
  150. h[0] = 3;
  151. h[1] = 1;
  152. h[2] = 4;
  153. h[3] = 1;
  154. h[4] = 5;
  155. h[5] = 9;
  156. h[6] = 2;
  157. h[7] = 6;
  158. h[8] = 5;
  159. h[9] = 3;
  160. h[10] = 5;
  161. h[11] = 6;
  162.  
  163. //3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 6
  164. // printVector(h);
  165. quicksort(h);
  166. printVector(h);
  167. return 0;
  168. }

Report this snippet  

You need to login to post a comment.