fork(1) download
copy 
  1. /**
  2.  * partition, quicksort, ith element
  3.  * Template functions
  4.  *
  5.  * Author: Erel Segal
  6.  * Date: 2010-10-17
  7.  */
  8.  
  9. #include <stdlib.h>
  10. #include <iostream>
  11. #include <sstream>
  12. using namespace std;
  13.  
  14.  
  15. /**
  16. * partition the given array [iFrom,iTo) into: less than pivot / pivot / greater than pivot.
  17. * @return an iterator right after the partition point.
  18. */
  19. template <class Iterator, typename T> Iterator partition (Iterator iFrom, Iterator iTo, T pivot) {
  20. 			while (iFrom<iTo) {
  21. 							if (*iFrom<pivot)
  22. 											++iFrom;
  23. 							else if (*iTo>pivot)
  24. 											--iTo;
  25. 							else if (*iFrom>*iTo) {   /* pivot <= iFrom and *iTo <= pivot */
  26. 											swap(*iFrom, *iTo);
  27. 											++iFrom;
  28. 							} else {     /* pivot == *iFrom == *iTo == pivot */
  29. 											++iFrom;
  30. 							}
  31. 			}
  32. 			return iFrom;
  33. }
  34.  
  35.  
  36. /**
  37. * partition the given array [iFrom,iTo) into: less than pivot / greater than pivot
  38. * @return the index where the pivot element should be inserted
  39. */
  40. template <class Iterator> void quicksort (Iterator iFrom, Iterator iTo) {
  41. 	int size = iTo-iFrom;
  42. 	//cout << prefix << "quicksorting " << size << " elements: "; print(iFrom, iTo);
  43. 	if (size<=1) return;
  44. 	Iterator pivot = iFrom+rand()%size;
  45. 	Iterator pivotAfterPartition = partition(iFrom, iTo-1, *pivot);
  46. 	//cout << prefix << "partitioning by " << *pivot << " at place " << (pivotAfterPartition-iFrom) << endl;
  47. 	if (pivotAfterPartition==iFrom) { // pivot is minimum
  48. 		quicksort(iFrom+1, iTo);
  49. 	} else if (pivotAfterPartition==iTo) { // pivot is maximum
  50. 		quicksort(iFrom, iTo-1);
  51. 	} else {
  52. 		quicksort(iFrom, pivotAfterPartition);
  53. 		quicksort(pivotAfterPartition , iTo);
  54. 	}
  55. 	//cout << prefix << "--------------------------- "; print(iFrom, iTo);
  56. }
  57.  
  58.  
  59. /* find the element whose position in the sorter array is "rank" (rank >= 0) */
  60. template <class Iterator> Iterator ithElement(Iterator iFrom, Iterator iTo, int rank) {
  61. 	int size = iTo-iFrom;
  62. 	//cout << prefix << "quicksorting " << size << " elements: "; print(iFrom, iTo);
  63. 	if (rank>=size) {
  64. 		stringstream error;
  65. 		error << "tried to find element " << rank << " but there are only " << size << " elements!";
  66. 		throw (error.str());
  67. 	} else if (size==1) {
  68. 		return iFrom;
  69. 	}
  70. 	Iterator pivot = iFrom+rand()%size;
  71. 	Iterator pivotAfterPartition = partition(iFrom, iTo-1, *pivot);
  72. 	int numBeforePivot = pivotAfterPartition-iFrom;
  73. 	if (rank < numBeforePivot)
  74. 		return ithElement(iFrom, pivotAfterPartition, rank);
  75. 	else
  76. 		return ithElement(pivotAfterPartition, iTo, rank-numBeforePivot);
  77. }
  78.  
  79.  
  80.  
  81. template <class Iterator> void print (Iterator iFrom, Iterator iTo) {
  82. 	for (; iFrom<iTo; ++iFrom) {
  83. 		cout << *iFrom << " ";
  84. 	}
  85. 	cout << endl;
  86. }
  87.  
  88. template <class Iterator> void assertSorted(Iterator iFrom, Iterator iTo) {
  89. 	for (; iFrom<iTo-1; ++iFrom) {
  90. 		if (*iFrom > *(iFrom+1)) {
  91. 			cerr << "array is out of order: " << *iFrom << " > " << *(iFrom+1) << endl;
  92. 		}
  93. 	}
  94. 	cout << endl;
  95. }
  96.  
  97.  
  98.  
  99. void checkPartition(int array[], int size, int pivot) {
  100. 			cout << "before: "; print (array, array+size);
  101. 			int* pivotAfterPartition = partition(array, array+size-1, pivot);
  102. 			cout << "after (position of "<<pivot<<" = " << (pivotAfterPartition-array) << "): "; print (array, array+size);
  103. 			//assertSorted(array, array+size);
  104. }
  105.  
  106.  
  107. void checkQuicksort(int array[], int size) {
  108. 			cout << "before: "; print (array, array+size);
  109. 			quicksort(array, array+size);
  110. 			cout << "after: "; print (array, array+size);
  111. 			assertSorted(array, array+size);
  112. }
  113.  
  114.  
  115. void checkIthElement(int array[], int size) {
  116. 	for (int i=0; i<size; ++i) {
  117. 		cout << "Element #" << i << ": " << (*ithElement(array, array+size, i)) << endl;
  118. 	}
  119. }
  120.  
  121.  
  122. #include <time.h>
  123. int main() {
  124. 			srand(time(NULL));
  125. 			int size=20;
  126. 			int* a = new int[size];
  127. 			for (int i=0; i<size; ++i)
  128. 							a[i] = rand()%100;
  129. 			checkPartition(a, size, rand()%100);
  130. 			checkIthElement(a,size);
  131. 			checkQuicksort(a, size);
  132. }
  133.  
Success #stdin #stdout 0s 2864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
before: 80 53 70 23 10 2 87 55 45 4 48 7 94 52 37 44 51 53 86 81 
after (position of 60 = 14): 53 53 51 23 10 2 44 55 45 4 48 7 37 52 94 87 70 80 86 81 
Element #0: 2
Element #1: 4
Element #2: 7
Element #3: 10
Element #4: 23
Element #5: 37
Element #6: 44
Element #7: 45
Element #8: 48
Element #9: 51
Element #10: 52
Element #11: 53
Element #12: 53
Element #13: 55
Element #14: 70
Element #15: 80
Element #16: 81
Element #17: 86
Element #18: 87
Element #19: 94
before: 2 4 7 10 23 37 44 45 48 51 52 53 53 55 70 80 81 86 87 94 
after: 2 4 7 10 23 37 44 45 48 51 52 53 53 55 70 80 81 86 87 94
https://ideone.com/UGwlG
language:
C++ (gcc 8.3)
created:
13 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!