Skip to content

Instantly share code, notes, and snippets.

@parvinderandroid
Created August 8, 2019 13:36
Show Gist options
  • Save parvinderandroid/e46d4b374d8ba1b2bbe41343b5f04651 to your computer and use it in GitHub Desktop.
Save parvinderandroid/e46d4b374d8ba1b2bbe41343b5f04651 to your computer and use it in GitHub Desktop.
Trying to compare different sorts of sorting algorithms in C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int *arr, int len) {
int i, j, t, minIndex;
for(i=0; i<len-1; i++) {
minIndex = i;
for(j=i+1; j<len; j++)
if(*(arr + j) < *(arr + minIndex))
minIndex = j;
t = *(arr + i);
*(arr + i) = *(arr + minIndex);
*(arr + minIndex) = t;
}
}
void bubbleSort(int *arr, int len) {
int i, j, temp;
for(i=0; i<len-1; i++) {
for(j=0; j<len-1-i; j++) {
if(*(arr + j) > *(arr + j + 1)) {
temp = *(arr + j);
*(arr + j) = *(arr + j + 1);
*(arr + j + 1) = temp;
}
}
}
}
void insertionSort(int *arr, int len) {
int i, j, temp;
for(i=1; i<len; i++) {
for(j=0; j<i; j++) {
if(*(arr + i) < *(arr + j)) {
temp = *(arr + i);
*(arr + i) = *(arr + j);
*(arr + j) = temp;
}
}
}
}
void merge(int *left, int *right, int *arr, int leftlen, int rightlen) {
int i, j, k;
i = j = k = 0;
while(i<leftlen && j<rightlen)
if(*(left + i) < *(right + j))
*(arr + k++) = *(left + i++);
else
*(arr + k++) = *(right + j++);
while(i<leftlen)
*(arr + k++) = *(left + i++);
while(j<rightlen)
*(arr + k++) = *(right + j++);
}
void mergeSort(int *arr, int len) {
if(len==1)
return;
int i, mid, *left, *right;
mid = len / 2;
left = (int *)calloc(mid, sizeof(int));
right = (int *)calloc(len - mid, sizeof(int));
for(i=0; i<mid; i++)
*(left + i) = *(arr + i);
for(; i<len; i++)
*(right + i - mid) = *(arr + i);
mergeSort(left, mid);
mergeSort(right, len-mid);
merge(left, right, arr, mid, len-mid);
}
int partition(int *arr, int start, int end) {
int pivot = *(arr + end), pIndex = start, i, temp;
for(i=start; i<end; i++) {
if(*(arr + i) <= pivot) {
temp = *(arr + i);
*(arr + i) = *(arr + pIndex);
*(arr + pIndex) = temp;
pIndex++;
}
}
temp = *(arr + end);
*(arr + end) = *(arr + pIndex);
*(arr + pIndex) = temp;
return pIndex;
}
void quickSort(int *arr, int start, int end) {
if(start >= end)
return;
int pIndex = partition(arr, start, end);
quickSort(arr, start, pIndex-1);
quickSort(arr, pIndex+1, end);
}
int main()
{
int *source, *copy, len = 100000;
clock_t start, end;
double time_spent;
source = (int *)calloc(len, sizeof(int));
copy = (int *)calloc(len, sizeof(int));
srand(time(0));
for(int c = 0; c < len; c++)
*(source + c) = rand() % 256;
//Starting Selection sort
start = clock();
copy = source;
selectionSort(copy, len);
end = clock();
time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Selection Sort finished in %lf seconds\n", time_spent);
//Starting Bubble sort
start = clock();
copy = source;
bubbleSort(copy, len);
end = clock();
time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Bubble Sort finished in %lf seconds\n", time_spent);
//Starting Insertion sort
start = clock();
copy = source;
insertionSort(copy, len);
end = clock();
time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Insertion Sort finished in %lf seconds\n", time_spent);
//Starting Merge sort
start = clock();
copy = source;
mergeSort(copy, len);
end = clock();
time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Merge Sort finished in %lf seconds\n", time_spent);
//Starting Quick sort
start = clock();
copy = source;
quickSort(copy, 0, len-1);
end = clock();
time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Quick Sort finished in %lf seconds\n", time_spent);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment