fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. template <class T>
  8. void printVector(vector<T>& A) {
  9. 	for(int i=0; i < A.size(); ++i)
  10. 		cout << A[i] << " ";
  11. 	cout << endl;
  12. }
  13.  
  14. template <class T>
  15. int partition(vector<T>& arr, int left, int right, int piv) {
  16. 	int leftmostSmallerThanPivot = left;
  17.  
  18. 	if(piv != left)
  19. 		swap(arr[piv], arr[left]);
  20. 	for(int i=left+1; i <= right; ++i) {
  21. 		if(arr[i] < arr[left])
  22. 			swap(arr[++leftmostSmallerThanPivot], arr[i]);
  23. 	}
  24. 	swap(arr[left], arr[leftmostSmallerThanPivot]);
  25.  
  26. 	return leftmostSmallerThanPivot;
  27. }
  28.  
  29. template <class T>
  30. void quickSort(vector<T>& arr, int p, int r) {
  31.     if (p < r) {
  32.         int q, piv(p);
  33.  
  34.         piv = ((p + r) / 2); // doesn't work
  35.  
  36.         q = partition(arr, p, r, piv);
  37.  
  38.         quickSort(arr, p, q - 1); //Sort left half
  39.         quickSort(arr, q + 1, r); //Sort right half
  40.     }
  41. }
  42.  
  43. int main()
  44. {
  45. 	vector<int> A(10);
  46.     for(int i=0; i < 10; ++i)
  47.     	A[i] = 10 - i;
  48.  
  49.     quickSort(A, 0, 9);
  50. 	printVector(A);
  51. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 7 8 9 10
https://ideone.com/7fIKgQ
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!