fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // using Lomuto partition scheme
  5. int Partition(int a[], int start, int end)
  6. {
  7. 	// Pick rightmost element as pivot from the array
  8. 	int pivot = a[end];
  9.  
  10. 	// elements less than pivot will be pushed to the left of pIndex
  11. 	// elements more than pivot will be pushed to the right of pIndex
  12. 	// equal elements can go either way
  13. 	int pIndex = start;	
  14.  
  15. 	// each time we finds an element less than or equal to pivot, pIndex
  16. 	// is incremented and that element would be placed before the pivot. 
  17. 	for (int i = start; i < end; i++)
  18. 	{
  19. 		if (a[i] <= pivot)
  20. 		{
  21. 			swap(a[i], a[pIndex]);
  22. 			pIndex++;
  23. 		}
  24. 	}
  25. 	// swap pIndex with Pivot
  26. 	swap (a[pIndex], a[end]);
  27.  
  28. 	// return pIndex (index of pivot element)
  29. 	return pIndex;
  30. }
  31.  
  32. /* We select the smaller sub-array, recurse on that portion,
  33. the continually shrink the array from the recursing side 
  34. through the iterative control until the array is sorted. 
  35. As such, we successfully sort the array in a way that 
  36. maximizes while control, while minimizing recursive depth. */
  37. void tailRecursiveQuicksort(int A[], int start, int end)
  38. {
  39. 	while (start < end) 
  40. 	{
  41. 		int pivot = Partition(A, start, end);
  42.  
  43. 		// recurse on smaller sub-array
  44. 		if (pivot - start < end - pivot) 
  45. 		{
  46. 			tailRecursiveQuicksort(A, start, pivot - 1);
  47. 			start = pivot + 1;
  48. 		} 
  49. 		else 
  50. 		{
  51. 			tailRecursiveQuicksort(A, pivot + 1, end);
  52. 			end = pivot - 1;
  53. 		}
  54. 	}
  55. }
  56.  
  57. int main()
  58. {
  59. 	int a[] = { 9, -3, 5, 2, 6, 8, -6, 1, 3 };
  60. 	int n = sizeof(a)/sizeof(a[0]);
  61.  
  62. 	// tail Recursive Quicksort routine
  63. 	tailRecursiveQuicksort(a, 0, n - 1);
  64.  
  65. 	// print the sorted array
  66. 	for (int i = 0 ; i < n; i++)
  67. 		cout << a[i] << " ";
  68. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-6 -3 1 2 3 5 6 8 9
https://ideone.com/dESnqy
Tail Recursive Quicksort
language:
C++14 (gcc 8.3)
created:
7 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!