Created
August 8, 2019 13:36
-
-
Save parvinderandroid/e46d4b374d8ba1b2bbe41343b5f04651 to your computer and use it in GitHub Desktop.
Trying to compare different sorts of sorting algorithms in C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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