fork download 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <functional>
  4.  
  5. void quickSort(std::vector<long>& numberList, long low, long high)
  6. {
  7. 	struct lh { long low; long high; };
  8. 	std::vector<lh> stack;
  9. 	stack.push_back(lh{low, high});
  10.  
  11. 	while (!stack.empty())
  12. 	{
  13. 		lh popped = stack.back();
  14. 		stack.pop_back();
  15. 		low = popped.low;
  16. 		high = popped.high;
  17.  
  18. 		long pivot, indexLow, indexHigh, temp;
  19.  
  20. 	    if(low<high){
  21. 	        pivot = low;
  22. 	        indexLow = low;
  23. 	        indexHigh = high;
  24.  
  25. 	        while(indexLow<indexHigh){
  26. 	            while(numberList[indexLow] <= numberList[pivot]){
  27. 	            indexLow++;
  28. 	            }
  29. 	            while(numberList[indexHigh] > numberList[pivot]){
  30. 	            indexHigh--;
  31. 	            }
  32.  
  33. 	            if(indexLow<indexHigh){
  34. 	                temp = numberList[indexLow];
  35. 	                numberList[indexLow] = numberList[indexHigh];
  36. 	                numberList[indexHigh] = temp;
  37. 	                }
  38. 	        }
  39.  
  40. 	        temp = numberList[pivot];
  41. 	        numberList[pivot] = numberList[indexHigh];
  42. 	        numberList[indexHigh] = temp;
  43.  
  44. 	        //std::string s = std::accumulate(
  45. 	        //	numberList.begin()+1, numberList.end(), std::to_string(numberList[0]),
  46. 	        //    [](const std::string& a, auto& b) {
  47. 	        //        return a + '-' + std::to_string(b);
  48. 	        //    });
  49. 	        //printf("%s\n", s.c_str());
  50. 	        //printf("%d, %d, %d, %d, %d\n", low, indexLow, pivot, indexHigh, high);
  51.  
  52. 	        //printf("left %d %d\n", low, indexHigh-1);
  53. 	        //quickSort(numberList, low, indexHigh-1);
  54. 	        stack.push_back(lh{low, indexHigh-1});
  55.  
  56. 	        //printf("right %d %d\n", indexHigh+1, high);
  57. 	        //quickSort(numberList, indexHigh+1, high);
  58. 	        stack.push_back(lh{indexHigh+1, high});
  59.  
  60. 	        //printf("end\n");
  61. 	    }
  62. 	}
  63. }
  64.  
  65. int main()
  66. {
  67. 	constexpr size_t count = 1'000'000;
  68. 	std::vector<long> arr(count);
  69. 	std::generate(arr.begin(), arr.end(), bind(std::uniform_int_distribution<>(0,count-1), std::mt19937()));
  70. 	quickSort(arr, 0, count-1);
  71. 	return std::is_sorted(arr.begin(), arr.end()) ? 0 : 1;
  72. }
  73.  
Success #stdin #stdout 0.21s 3408KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/gwWSjV
Quicksort stack
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!