Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Various sorting algorithms in C++
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment