Various sorting algorithms in C++

sorting.cpp

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sys/time.h>

using namespace std;

/*
Funkcije
*/

// Zamenjaj 2 elementa v polju
void swap(int *a, int i1, int i2) {
	int temp = a[i1];
	a[i1] = a[i2];
	a[i2] = temp;
}

// QuickSort
// Sprejme polje in zacetni ter koncni indeks v polju
void quickSort(int *array, int left, int right) {
	if (right - left < 2) return; // Polje je ze sortirano, ker ima samo 1 element

	int pivotIndex = left;
	int pivot = array[pivotIndex];

	swap(array, pivotIndex, right);
	int storeIndex = left;

	for (int i = left; i < right; i++) {
		if (array[i] <= pivot) {
			swap(array, i, storeIndex);
			storeIndex++;
		}
	}

	swap(array, storeIndex, right);
	int pivotIndexNew = storeIndex;

	quickSort(array, left, pivotIndexNew - 1);
	quickSort(array, pivotIndexNew + 1, right);
}


// Zdruzi dva polja
void merge(int *a, int *b, int n)
{
	int *temp = (int *)malloc(n * sizeof(int));
	int *temp_a = a, *temp_b = b;
	for (int i = 0; i < n; i++)
	{
		if (temp_a == b) temp[i] = *temp_b++;
		else {
			if (temp_b == a + n) temp[i] = *temp_a++;
			else {
				if (*temp_a < *temp_b) temp[i] = *temp_a++;
				else temp[i] = *temp_b++;
			}
		}
	}
	memcpy(a, temp, n * sizeof(int));
	free(temp);
}

// MergeSort
void mergeSort(int *a, int n) {
	if (n < 2) return;
	int m = n / 2;
	mergeSort(a, m);
	mergeSort(a + m, n - m);
	merge(a, a + m, n);
}

// Potapljanje v kopico
void downHeap(int *a, int v, int n) {
	int w = 2*v + 1;
	while (w < n) {
		if (w + 1 < n) {
			if (a[w+1] > a[w]) w++;
		}
		if (a[v] >= a[w]) return;
		swap(a, v, w);
		v = w;
		w = 2*v + 1;
	}
}

// HeapSort
void heapSort(int *a, int n) {
	// Zgradi kopico
	for (int v = n/2 - 1; v >= 0; v--) {
		downHeap(a, v, n);
	}
	while(n > 1) {
		n--;
		swap(a, 0, n);
		downHeap(a, 0, n);
	}
}

// Izpisi polje
void printArray(int *array, int size) {
	cout << "[";
	for (int i = 0; i < size-1; i++) {
		cout << array[i] << ", ";
	}
	cout << array[size-1] << "]" << endl;
}

int main() {
	srand((unsigned)time(0));
	// Testi
	cout << "#\tQuickSort\tMergeSort\tHeapSort" << endl;
	for (int i = 1000; i <= 1024000; i *= 2) {
		cout << i << "\t";
		cout << flush;
		// Generiraj polje
		int *polje = (int *)malloc(i * sizeof(int));
		for (int j = 0; j < i; j++) {
			// polje[j] = rand();
			// polje[j] = 0;
			polje[j] = i;
		}
		int *tmp_polje = (int *)malloc(i * sizeof(int));
		struct timeval procTime;
		struct timeval procTimeEnd;
		// QuickSort
		memcpy(tmp_polje, polje, i*sizeof(int));
		gettimeofday(&procTime, NULL);
		quickSort(tmp_polje, 0, i-1);
		gettimeofday(&procTimeEnd, NULL);
		// printArray(tmp_polje, i);
		cout << (procTimeEnd.tv_sec - procTime.tv_sec) + (procTimeEnd.tv_usec - procTime.tv_usec)/10e6 << "\t";
		cout << flush;
		// MergeSort
		memcpy(tmp_polje, polje, i*sizeof(int));
		gettimeofday(&procTime, NULL);
		mergeSort(tmp_polje, i);
		gettimeofday(&procTimeEnd, NULL);
		cout << (procTimeEnd.tv_sec - procTime.tv_sec) + (procTimeEnd.tv_usec - procTime.tv_usec)/10e6 << "\t";
		cout << flush;
		// HeapSort
		memcpy(tmp_polje, polje, i*sizeof(int));
		gettimeofday(&procTime, NULL);
		heapSort(tmp_polje, i);
		gettimeofday(&procTimeEnd, NULL);
		cout << (procTimeEnd.tv_sec - procTime.tv_sec) + (procTimeEnd.tv_usec - procTime.tv_usec)/10e6;
		cout << flush;
		// Pocisti
		cout << endl;
		free(tmp_polje);
		free(polje);
	}
	
	return 0;
}