#include <iostream>
#include <algorithm>

void quick_sort(int* begin, int* end) {
	if (begin+1<end) {
		if (begin+2==end) {
			if (begin[1]<begin[0])
				std::swap(begin[1], begin[0]);
		}
		else {
			int low(0);
			int high(end-begin-1);
			int middle((low+high)/2);
			if (begin[middle]<begin[low])
				std::swap(begin[middle], begin[low]);
			if (begin[high]<begin[low])
				std::swap(begin[high], begin[low]);
			if (begin[high]<begin[middle])
				std::swap(begin[high], begin[middle]);
			int pivot(begin[middle]);
			std::swap(begin[middle], begin[high-1]);
			int i(low);
			int j(high-1);
			while (true) {
				while( begin[++i]<pivot) /* niets */;
				while( pivot<begin[--j]) /* niets */;
				if (i<j)
					std::swap(begin[i], begin[j]);
				else
					break;
			}
			std::swap(begin[i], begin[high-1]);
			quick_sort(begin+low, begin+i);
			quick_sort(begin+i+1, begin+high+1);
		}
	}
}

class Student {
public:
	Student(const char* vn, const char* an, int n):
		voornaam(vn), achternaam(an), nummer(n) {
	}
	const std::string& geefVoornaam() const {
		return voornaam;
	}
	const std::string& geefAchternaam() const {
		return achternaam;
	}
	int geefNummer() const {
		return nummer;
	}
private:
	std::string voornaam;
	std::string achternaam;
	int nummer;
};

std::ostream& operator<<(std::ostream& o, const Student& s) {
	return o<<s.geefVoornaam()<<' '<<s.geefAchternaam()<<' '<<s.geefNummer();
}

int main() {
	std::randomize();
	const int aantal(20);
	int a[aantal];
	for (int i(0); i<aantal; ++i) {
		a[i]=std::rand();
	}
	quick_sort(a, a+aantal);
	for (int i(0); i<aantal; ++i) {
		std::cout<<a[i]<<std::endl;
	}
	std::cin.get();
	Student array[]={
		Student("Gerben", "Arkel van", 7459),
		Student("Wendy", "Endt van der", 7145),
		Student("Gabor", "Bos", 7111),
		Student("Eddie", "Horde", 7016),
		Student("Patrick", "Deelman", 7333),
		Student("Joost", "Veelen van", 7233),
		Student("Talle", "Golverdingen", 7524),
		Student("Martijn", "Kirsten", 7174),
		Student("Erik", "Hoogeveen", 8145),
		Student("Stefan", "Kohler", 8159),
		Student("Stefan", "Hurk van den", 7107),
		Student("Vincent", "Kester", 7319),
		Student("Dirk", "VeefKind", 7470),
		Student("Berend-Jan", "Wever", 7588),
		Student("Stefan", "Extra", 1234)
	};
	const int n(sizeof array/sizeof array[0]);
//	Sorteer op nummer van hoog naar laag.
//	quick_sort(array, array+n, /* vul hier een functie in! */);
	for (int i(0); i<n; ++i) {
		std::cout<<array[i]<<std::endl;
	}
	std::cin.get();
//	Sorteer op voornaam van laag naar hoog, sorteer studenten
//	met dezelfde voornaam op achternaam.
//	quick_sort(array, array+n, /* vul hier een Functor in! */);
	for (int i(0); i<n; ++i) {
		std::cout<<array[i]<<std::endl;
	}
	std::cin.get();
}