Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void swap(VI& a, int from, int to){
- int temp = a[from];
- a[from] = a[to];
- a[to] = temp;
- }
- int median_of_3(VI& a, int lo, int hi){
- int l = a[lo];
- int h = a[hi];
- int mid = (lo + hi)/2;
- int m = a[mid];
- cout << "Taking median of " << l << " " << h << " " << m << endl;
- if (compareTo(l, m) < 0 && compareTo(m, h) < 0){
- return m;
- }
- if (compareTo(h, m) < 0 && compareTo(m, l) < 0){
- return m;
- }
- if (compareTo(m, l) < 0 && compareTo(l, h) < 0){
- return l;
- }
- if (compareTo(h, l) < 0 && compareTo(l, m) < 0){
- return l;
- }
- return h;
- }
- int qs3_Partition(VI& a, int lo, int hi) {
- int x = median_of_3(a, lo, hi); //Coffee choice of partition
- //cout << endl;
- cout << "Choice of partition element is: " << x << " and lo is: " << lo << " and hi is: " << hi << endl;
- while (lo < hi) {
- while (compareTo(a[lo], x) < 0){
- cout << "Comparing " << a[lo] << " and " << x << " yielding: " << compareTo(a[lo], x) << endl;
- ++lo;
- }
- while (compareTo(a[hi], x) > 0){
- cout << "Comparing " << a[hi] << " and " << x << " yielding: " << compareTo(a[hi], x) << endl;
- --hi;
- }
- if (lo < hi) {
- cout << "Swapping " << a[lo] << " and " << a[hi] << endl;
- swap(a, lo, hi);
- /*int temp = a[lo];
- a[lo++] = a[hi];
- a[hi--] = temp;*/
- if (compareTo(a[lo], a[hi] == 0)){
- lo++;
- }
- //print(a);
- //cout << endl;
- //cout << "lo is: " << lo << " and hi is: " << hi << endl;
- }
- }
- //print(a);
- //cout << endl;
- return lo;
- }
- int THRESHOLD = 4;
- void qs4 (VI& a, int lo, int hi) {
- while (hi - lo > THRESHOLD) { //THRESHOLD from 30 years ago was 20, experiment!
- while (lo < hi) {
- int m = qs3_Partition(a, lo, hi);
- if (m - lo < hi - m + 1) {
- qs4(a, lo, m - 1);
- lo = m;
- } else {
- qs4(a , m , hi);
- hi = m - 1;
- }
- }
- }
- }
- void insertion_sort_int(vector<int>& a){
- for(int j = 1; j < a.size(); ++j){
- int t = a[j];
- //cout << j << ": t = " << t << std::endl;
- for (int i = j; i > 0 && compareTo(a[i-1], t) >= 0; --i){
- //cout << a[i-1] << " >= " << t << std::endl;
- a[i] = a[i - 1];
- a[i - 1] = t;
- //print(a, n);
- //cout << std::endl;
- }
- }
- }
- void quick_sortCh (VI& a, int n) {
- qs4(a, 0, n-1);
- //print(a);
- //insertion_sort_int(a);
- }
Add Comment
Please, Sign In to add comment