An implementation of Quick Sort algorithm with median.

QuickSort.cpp

#include <sstream>
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <math.h>

using namespace std;

int divide(int* a, int bottom, int top);
void switchAt(int* a, int bottom, int top);

void quickSort(int* a, int bottom, int top)
{
	if(top < bottom) {
		return;
	}

	int j = divide(a, bottom, top);

	quickSort(a, bottom, j - 1);
	quickSort(a, j + 1, top);
}

void quickSort(int* a, int size)
{
	quickSort(a, 0, size - 1);
}

int divide(int* a, int bottom, int top)
{
	int mediana = (bottom + top) / 2;
	switchAt(a, bottom, mediana);

	int pivot = a[bottom]; // comparing element
	int left = bottom; // left index
	int right = top; // right index

	while(right>left) {
		// indexes have not yet crossed

		// move the left index to the right, until you get to a number that is bigger than pivot
		while(left<top && a[left] <= pivot) {
			++left;
		}
		// move the right index to the left, until you get to a number that is smaller than pivot
		while(right>bottom && a[right] >= pivot) {
			--right;
		}

		if(right>left) {
			// indexes have not crossed
			switchAt(a, left, right);
		}
	}

	switchAt(a, bottom, right);

	return right;
}

void switchAt(int* a, int i1, int i2)
{
	int z = a[i1];
	a[i1] = a[i2];
	a[i2] = z;
}

// Checks if a portion of the sequence is correctly sorted.
bool check(int* a, int bottom, int top)
{
	for(int i = bottom; i<top; ++i) {
		if(a[i + 1] < a[i]) {
			return false;
		}
	}
	return true;
}

// Checks if the sequence is correctly sorted.
bool check(int* a, int size)
{
	return check(a, 0, size - 1);
}

void generateRandomSequence(int* a, int size);
void generateAscendinglySortedSequence(int* a, int size);
void generateDescendinglySortedSequence(int* a, int size);
void output(int* a, int size);

int showMenu();
int getIntBetween(string prompt, int bottom, int top);
int getInt(string prompt);

int main()
{
	srand(time(NULL));

	const int M = 10000000;

	int* a = new int[M];
	int size = -1;

	while(true) {
		switch(showMenu()) {
			case 1: // Generate random sequence
			{
				size = getIntBetween("Size of the sequence: ", 1, M);
				generateRandomSequence(a, size);
				break;
			}
			case 2: // Generate ascendingly sorted sequence
			{
				size = getIntBetween("Size of the sequence: ", 1, M);
				generateAscendinglySortedSequence(a, size);
				break;
			}
			case 3: // Generate descendingly sorted sequence
			{
				size = getIntBetween("Size of the sequence: ", 1, M);
				generateDescendinglySortedSequence(a, size);
				break;
			}
			case 4: // Output sequence
			{
				if(size < 1) {
					cout << "No sequence has been generated yet!" << endl;
					break;
				}

				cout << "Sequence:" << endl;
				output(a, size);
				cout << endl;
				break;
			}
			case 5: // Sort with Quick Sort algorithm
			{
				if(size < 1) {
					cout << "No sequence has been generated yet!" << endl;
					break;
				}

				clock_t start, finish;
				double duration;

				start = clock();
				quickSort(a, size);
				finish = clock();

				duration = ((double)(finish - start)) / CLOCKS_PER_SEC;
				cout << "Time: " << duration << " s" << endl;
				break;
			}
			case 6: // Check if the sequence is sorted
			{
				if(size < 1) {
					cout << "No sequence has been generated yet!" << endl;
					break;
				}

				if(check(a, 0, size - 1)) {
					cout << "Sequence is correctly sorted!" << endl;
				} else {
					cout << "Sequence is not sorted!" << endl;
				}
				break;
			}
			case 7: // Exit
			{
				delete a;
				return 0;
			}
		}
	}
}

int showMenu()
{
	cout << endl;
	cout << "Quick Sort - menu:" << endl;
	cout << endl;
	cout << "1) Generate random sequence" << endl;
	cout << "2) Generate ascendingly sorted sequence" << endl;
	cout << "3) Generate descendingly sorted sequence" << endl;
	cout << "4) Output sequence" << endl;
	cout << "5) Sort with Quick Sort algorithm" << endl;
	cout << "6) Check if the sequence is sorted" << endl;
	cout << "7) Exit" << endl;
	cout << endl;
	int option;
	do {
		option = getIntBetween("Choose: ", 1, 7);
	} while(option < 1 || option > 7);
	cout << endl;
	return option;
}

void generateRandomSequence(int* a, int size)
{
	for(int i = size-1; i>=0; --i) {
		a[i] = rand();
	}
}

void generateAscendinglySortedSequence(int* a, int size)
{
	for(int i = 0; i<size; ++i) {
		a[i] = i + 1;
	}
}

void generateDescendinglySortedSequence(int* a, int size)
{
	for(int i = size - 1; i >= 0; --i) {
		a[i] = i + 1;
	}
}

void output(int* a, int size)
{
	for(int i = 0; i<size; ++i) {
		cout << a[i] << " ";
	}
}

int getIntBetween(string prompt, int bottom, int top)
{
	int n;
	do {
		n = getInt(prompt);
	} while(n<bottom || n>top);
	return n;
}

int getInt(string prompt)
{
	int output;
	string input;

	while(true) {
		cout << prompt;
		getline(cin, input);
		stringstream ss(input);

		if(ss >> output && !(ss >> input)) {
			return output;
		}
		cin.clear();
	}
}