Skip to content

Instantly share code, notes, and snippets.

@onlined
Last active November 10, 2016 13:13
Show Gist options
  • Save onlined/cbac386bb90795739256c91d650c4c21 to your computer and use it in GitHub Desktop.
Save onlined/cbac386bb90795739256c91d650c4c21 to your computer and use it in GitHub Desktop.
Comparison of different sort algorithms
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>
#define SWAP(x,y) do { int tmp = (x); (x) = (y); (y) = tmp; } while(false)
// For heapsort
#define LEFT(x) (2*(x)+1)
#define RIGHT(x) (2*(x)+2)
#define TOP(x) (((x)-1)/2)
void bubble_sort(int *array, int len) {
for(int i=0;i<len-1;i++) {
bool changed = false;
for(int j=0;j<len-1;j++)
if(array[j] > array[j+1]) {
SWAP(array[j],array[j+1]);
changed = true;
}
if(!changed)
break;
}
}
void selection_sort(int *array, int len) {
for(int i=0;i<len-1;i++) {
int min_index = i;
for(int j=i+1;j<len;j++) {
if(array[j] < array[min_index])
min_index = j;
}
SWAP(array[min_index], array[i]);
}
}
void insertion_sort(int *array, int len) {
for(int i=1;i<len;i++) {
int elem = array[i];
int j;
for(j=i-1;j>=0 && array[j] > elem;j--)
array[j+1] = array[j];
array[j+1] = elem;
}
}
void merge_sort(int *array, int len) {
if(len < 2)
return;
int *first = array;
int first_len = len/2;
int *second = array + first_len;
int second_len = len - first_len;
merge_sort(first,first_len);
merge_sort(second,second_len);
int *new_array = malloc(sizeof(int)*len);
int i,j;
for(i=0, j=0;i<first_len && j<second_len;) {
if(first[i] <= second[j]) {
new_array[i+j] = first[i];
i++;
}
else {
new_array[i+j] = second[j];
j++;
}
}
for(;i<first_len;i++)
new_array[i+j] = first[i];
for(;j<second_len;j++)
new_array[i+j] = second[j];
for(int k=0;k<len;k++)
array[k] = new_array[k];
free(new_array);
}
void quicksort(int *array, int len) {
if(len < 2)
return;
int pivot_pos = 0;
for(int i=1;i<len;i++) {
if(array[i] < array[0]) {
pivot_pos++;
SWAP(array[i], array[pivot_pos]);
}
}
SWAP(array[0], array[pivot_pos]);
quicksort(array, pivot_pos);
quicksort(array + pivot_pos + 1, len - pivot_pos - 1);
}
void push_down_root(int *heap, int len, int root) {
while(1) {
int max = root;
if(LEFT(root) < len && heap[LEFT(root)] > heap[max]) // left node
max = LEFT(root);
if(RIGHT(root) < len && heap[RIGHT(root)] > heap[max]) // right node
max = RIGHT(root);
if(root == max)
break;
SWAP(heap[root], heap[max]);
root = max;
}
}
void heapsort(int *array, int len) {
for(int j=TOP(len-1);j>=0;j--)
push_down_root(array, len, j);
for(int i=0;i<len-1;i++) {
SWAP(array[0], array[len-1-i]);
push_down_root(array, len-i-1, 0);
}
}
void print_array(int *array, int len) {
for(int i=0;i<len;i++)
printf("%d ",array[i]);
puts("");
}
struct timespec ts_diff(struct timespec first, struct timespec second) {
struct timespec diff;
if(first.tv_nsec < second.tv_nsec) {
diff.tv_sec = -1;
diff.tv_nsec = 1000000000;
}
else {
diff.tv_sec = diff.tv_nsec = 0;
}
diff.tv_sec += first.tv_sec - second.tv_sec;
diff.tv_nsec += first.tv_nsec - second.tv_nsec;
return diff;
}
void test_sort(void (*sort)(int *, int), char* test_name, int *array, int len) {
struct timespec start, end, diff;
int *test_array = malloc(len*sizeof(int));
memcpy(test_array, array, len*sizeof(int));
puts("--------------------------");
printf("%s\n", test_name);
printf("Before: ");
print_array(test_array, len);
timespec_get(&start, TIME_UTC);
sort(test_array, len);
timespec_get(&end, TIME_UTC);
printf("After: ");
print_array(test_array, len);
diff = ts_diff(end, start);
printf("Time: ");
if(diff.tv_sec > 0)
printf("%lld seconds ", (long long int) diff.tv_sec);
if(diff.tv_nsec > 0)
printf("%lld nanosec", (long long int) diff.tv_nsec);
puts("\n--------------------------");
}
int main(void) {
int array[] = {4,6,8,1,5,0,3,9,7,2};
int long_array[] = {3002,9483,2802,8502,6147,2322,2378,1807,5198,7647,704,7956,9505,1413,1078,7683,764,6949,5481,8143,2661,6212,1706,9177,5403,6593,4324,8228,8126,8463,2714,2088,6028,2740,1132,4275,9385,7704,5130,4917,8637,8439,4218,341,3299,5579,9003,4531,4227,2719,3485,7409,5416,9645,9920,8333,3131,3745,5961,8871,5696,4277,7718,8311,8048,3944,512,9104,7697,4921,1848,6263,4759,4851,8856,3674,9115,8031,1601,415,6543,2937,7600,4607,7631,1045,6408,8000,379,8491,5478,5103,3977,1534,5042,8606,7073,6382,1873,6134};
test_sort(bubble_sort, "Bubble sort", array, 10);
test_sort(selection_sort, "Selection sort", array, 10);
test_sort(insertion_sort, "Insertion sort", array, 10);
test_sort(merge_sort, "Merge sort", array, 10);
test_sort(quicksort, "Quicksort", array, 10);
test_sort(heapsort, "Heapsort", array, 10);
test_sort(bubble_sort, "Bubble sort (Long)", long_array, 100);
test_sort(selection_sort, "Selection sort (Long)", long_array, 100);
test_sort(insertion_sort, "Insertion sort (Long)", long_array, 100);
test_sort(merge_sort, "Merge sort (Long)", long_array, 100);
test_sort(quicksort, "Quicksort (Long)", long_array, 100);
test_sort(heapsort, "Heapsort (Long)", long_array, 100);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment