quicksort.cpp

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

// skilgreiningar:
void quicksort(vector<int>&);
void quicksorts(vector<int>&, int, int);
int partition(vector<int>&, int, int);
void exchange(vector<int>&, int, int);

void quicksort(vector<int>& v) {
  // Hingað þarf að koma útfærsla á quicksort!
  // Mælt er með því að fylgja hugmyndunum í Quick.java.

    // ég skil útfrá ábendingu 1 að það eigi að shuffla aftur?:
    random_shuffle(v.begin(), v.end());
    quicksorts(v, 0, v.size()-1);
}

// sorterar undirvigurinn frá lo til hi
void quicksorts(vector<int>& v, int lo, int hi) {
    if (hi <= lo) return;
    int j = partition(v, lo, hi);
    quicksorts(v, lo, j-1);
    quicksorts(v, j+1, hi);
}

// skiptir undirvigrinum
int partition(vector<int>& v, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    int a = v[lo];
    while (true) {
        // finnum gildi fyrir lo til að skipta
        while (v[++i] < a) {
            if (i == hi) break;
        }
        // finnum gildi fyrir hi til að skipta
        while (a < v[--j]) {
            if (j == lo) break;
        }

        if (i >= j) break;

        exchange(v, i, j);
    }

    exchange(v, lo, j);
    return j;
}

// skiptum á v[i] og v[j]
void exchange(vector<int>& v, int i, int j) {
    int skipta = v[i];
    v[i] = v[j];
    v[j] = skipta;
}

bool issorted(vector<int>& v) {
    /*
     * Athugar hvort vigurinn v sé í stígandi röð
     */
    cout << endl;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] < v[i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    // Prófum sort á vigrum af lengdunum 0, 101, og 1000:
    vector<int> sizes = {0, 10, 20};
    for (int n : sizes) {
        // Upphafstillum v með tölunum 0 upp í n-1 í slembinni röð
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            v[i] = i;
        }
        random_shuffle(v.begin(), v.end());

        // Röðum v aftur
        quicksort(v);

        // Athugum hvort röðunin tókst
        if (issorted(v)) {
            cout << "Röðun á " << v.size() << " staka vigri tókst" << endl;
        } else {
            cout << "Röðun á " << v.size() << " staka vigri mistókst" << endl;
        }
    }
}