Programmieren, Algorithmen und Datenstrukturen 2 (Vorlesung 20)

Quicksort

/* 
 * File:   main.cpp
 * Author: maximilian.krieg
 *
 * Created on 19. rechtsuni 2012, 14:36
 */

#include 
#include 
#include 
using namespace std;

/*
 * 
 */
void ausgabe(vectorvi) {
    for (int i = 0; i < vi.size(); i++) {
	cout << vi[i];
    }
    cout << endl;
}

void quicksort(vector& vi, int ui, int oi) {
    // Start bei UI und Element links von OI
    // OI == Pivot-Element
    int links = ui;
    int rechts = oi - 1;
    int pivot = oi;

    // Solange die Zeiger noch auf ihrer Seite sind
    while (links <= rechts) {

	// Laufen bis Element gefunden, das kleiner als Pivot
	while (vi[rechts] > vi[pivot]) 
	{rechts--;}

	// Laufen bis Element gefunden, das größer als Pivot
	while (vi[links] < vi[pivot]) 
	{links++;}

	// Tausch der beiden Elemente an dem die Zeiger stehen geblieben sind
	// Nur solange die Zeiger noch nicht die Teilbäume gewechselt haben
	if (links <= rechts) {
	    // Tauschen
	    int tmp = vi[links];
	    vi[links] = vi[rechts];
	    vi[rechts] = tmp;
	    
	    // Noch einen Schritt weiter gehen um 
	    links++;
	    rechts--;
	}
    }

    // Vertauschen des kleinsten Elements im rechten Teilbaum mit Pivot-Element
    // Links steht nun auf dem 1. Element im rechten Teilbaum
    int tmp = vi[pivot];
    vi[pivot] = vi[links];
    vi[links] = tmp;

    // Rechts = neuer OI für linke Seite
    // Wenn eine Seite noch mehr als 1 Element enthält..
    if (ui < rechts)
	quicksort(vi, ui, rechts);
    
    // Links = neuer UI für rechte Seite
    // Wenn eine Seite noch mehr als 1 Element enthält..
    if (oi > links)
	quicksort(vi, links, oi);
}

int main() {

    // Initialisieren und befüllen des Vektors
    vector vi;
    vi.push_back(4);
    vi.push_back(7);
    vi.push_back(2);
    vi.push_back(8);
    vi.push_back(1);
    vi.push_back(9);
    vi.push_back(0);
    vi.push_back(6);
    vi.push_back(3);
    vi.push_back(5);
    
    // Ausgabe des unsortierten Vektors
    ausgabe(vi);
    
    // Parameter für Suche initialisieren
    int ui = 0;
    int oi = vi.size() - 1;
    
    // Aufruf der Suche
    quicksort(vi, ui, oi);
    
    // Ausgabe des sortierten Vektors
    ausgabe(vi);
    return 0;
}