codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <cstdio> #include <algorithm> #include <vector> #include <list> #include <iostream> void printArray(const int * const a, const int len) { for(int i=0; i<len; i++) printf("%i ", a[i]); printf("\n"); } template <class T> void printSeq(T iter, T endIter) { while(iter != endIter) { std::cout << *iter << " "; iter++; } std::cout << "\n"; } template <class Titer> void qsort(const Titer iter, const Titer endIter) { if((endIter - iter) < 2) return; const int len = endIter - iter; const int pivot = *(iter + (rand() % len)); Titer lower = iter; Titer upper = endIter - 1; while(true) { while(*lower < pivot) lower++; while(*upper > pivot) upper--; // Case where we have two equal elements. if(*lower == *upper && lower < upper) { lower++; } printSeq(iter, endIter); if(lower == upper) { break; } std::swap(*lower, *upper); } std::cout << "First Part " << "\n"; printSeq(iter, lower); std::cout << "Second Part " << "\n"; printSeq(lower + 1, endIter); std::cout << "\n"; qsort(iter, lower); qsort(lower + 1, endIter); } /* Without templates.. void qsort(int * const a, const int len) { if(len < 2) return; const int pivot = a[rand() % len]; printf("Choosed pivot %i\n", pivot); int lower = 0; int upper = len - 1; while(true) { while(a[lower] < pivot) lower++; while(a[upper] > pivot) upper--; // Case where we have two equal elements. if(a[lower] == a[upper] && lower < upper) { lower++; } printArray(a, len); if(lower == upper) { break; } std::swap(a[lower], a[upper]); } printf("First Part "); printArray(a, lower); printf("Second Part "); printArray(a + lower + 1, len - lower - 1); printf("\n"); qsort(a, lower); qsort(a + lower + 1, len - lower - 1); } */ int main() { int tmp[] = {1, 7, 3, 6, 11, 0, 0, 5, 7, 2, 9, 2, 4, 8, 12, 1, 10}; //int tmp[] = {4, 3, 7}; int len = sizeof(tmp)/sizeof(tmp[0]); std::vector<int> a; a.assign(tmp, tmp + len); qsort(a.begin(), a.end()); printSeq(a.begin(), a.end()); /* // same using a list std::list<int> b; a.assign(tmp, tmp + len); qsort(b.begin(), b.end()); printSeq(b.begin(), b.end()); */ std::cin.get(); }
Private
[
?
]
Run code
Submit