fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void printVector(vector<int> toPrint){
  6. 	for(int i = 0; i < toPrint.size(); i++){
  7. 		if (i != 0){
  8. 			cout << ", ";
  9. 		}
  10. 		cout << toPrint[i];
  11. 	}
  12. 	cout << endl;
  13. }
  14.  
  15.  
  16. int HoarePartition(vector<int> & in){
  17. 	int startIndex = 0; 
  18. 	int stopIndex = in.size()-1;
  19. 	int pivot = in[ startIndex ];
  20.  
  21. 	cout << "=== Before Partition ===" <<endl;
  22. 	printVector(in);
  23.  
  24. 	while (true){
  25. 		while ( in[ startIndex ] <= pivot ){
  26. 			startIndex++;
  27. 		}
  28. 		while ( in[ stopIndex ] > pivot ){
  29. 			stopIndex--;
  30. 		}
  31. 		if( startIndex < stopIndex ){
  32. 			// swap!
  33. 			int swapCup = in[ startIndex ];
  34. 			in[ startIndex ] = in[ stopIndex ];
  35. 			in[ stopIndex ] = swapCup;
  36. 		}
  37. 		else{
  38. 			cout << "=== After Partition ===" << endl;
  39. 			printVector(in);
  40. 			return stopIndex;
  41. 		}
  42. 	}
  43.  
  44. }
  45.  
  46.  
  47. int main() {
  48. 	vector<int> test;
  49.  
  50. 	test.push_back(5);
  51. 	test.push_back(9);
  52. 	test.push_back(8);
  53. 	test.push_back(4);
  54. 	test.push_back(1);
  55. 	test.push_back(2);
  56.  
  57. 	HoarePartition(test);
  58. 	return 0;
  59. }
  60.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
=== Before Partition ===
5, 9, 8, 4, 1, 2
=== After Partition ===
5, 2, 1, 4, 8, 9
https://ideone.com/uLPi8v
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!