This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Algorithm : Quick Sort | |
| * Writer : Mehadi Hasan Menon. | |
| **/ | |
| #include <iostream> | |
| #include <stack> | |
| using namespace std; | |
| int a[] = {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66}; | |
| int loc; | |
| void quick(int beg, int end) | |
| { | |
| int left, right; | |
| left = beg, right = end; | |
| while(a[loc] <= a[right] && loc != right) { | |
| right--; | |
| } | |
| if(loc == right) { | |
| return; | |
| } | |
| if(a[loc] > a[right]) { | |
| int tmp; | |
| tmp = a[loc]; a[loc] = a[right]; a[right] = tmp; | |
| loc = right; | |
| } | |
| while(a[left] <= a[loc] && loc != left) { | |
| left++; | |
| } | |
| if(loc == left) { | |
| return; | |
| } | |
| if(a[left] > a[loc]) { | |
| int tmp; | |
| tmp = a[loc]; a[loc] = a[left]; a[left] = tmp; | |
| loc = left; | |
| } | |
| quick(left, right); | |
| } | |
| int main() | |
| { | |
| stack <int> lower, upper; | |
| lower.push(0); upper.push(11); | |
| while(!lower.empty()) | |
| { | |
| // pop sublist index | |
| int beg = lower.top(); lower.pop(); | |
| int end = upper.top(); upper.pop(); | |
| loc = beg; | |
| // fix the final position of pos | |
| quick(beg, end); | |
| if(beg < loc) { | |
| lower.push(beg); | |
| upper.push(loc - 1); | |
| } | |
| if(loc < end) { | |
| lower.push(loc + 1); | |
| upper.push(end); | |
| } | |
| } | |
| for(int i = 0; i < 12; i++) { | |
| printf("%d ", a[i]); | |
| } | |
| return 0; | |
| } |
Comments
Post a Comment