Skip to content

Instantly share code, notes, and snippets.

@jaseemabid
Last active August 25, 2017 09:51
Show Gist options
  • Save jaseemabid/a5df903f34cc3787da6e83d84eedf937 to your computer and use it in GitHub Desktop.
Save jaseemabid/a5df903f34cc3787da6e83d84eedf937 to your computer and use it in GitHub Desktop.
sort.c
size insertion sort quick sort
0 29.937500 31.562500
1 26.000000 35.437500
2 30.187500 35.250000
3 33.062500 41.125000
4 39.375000 44.750000
5 46.812500 46.750000
6 48.687500 50.875000
7 57.500000 52.187500
8 65.500000 71.562500
9 78.750000 70.625000
10 91.375000 70.000000
11 97.125000 74.625000
12 100.000000 82.250000
13 139.000000 92.875000
14 214.312500 131.937500
15 207.062500 118.375000
16 230.250000 124.562500
17 280.312500 134.937500
18 429.250000 175.125000
19 476.875000 167.250000
20 589.125000 166.000000
21 758.937500 173.500000
22 831.062500 174.312500
23 944.125000 186.625000
24 993.937500 203.937500
25 1101.562500 196.250000
26 1198.812500 199.375000
27 1296.125000 216.000000
28 1368.500000 217.625000
29 1597.375000 236.062500
30 1670.250000 238.000000
31 1828.500000 264.500000
32 1854.687500 265.187500
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
// Max size of input
#define SIZE 32
// Number of times each experiment is repeated
#define TIMES 16
static void swap(int *i, int *j) {
int temp = *i;
*i = *j;
*j = temp;
}
// Insertion sort
void i_sort(int *a, size_t size) {
// (0 i] is already sorted
for (size_t i = 1; i < size; i++) {
// Insert a[j] into (0 j]
for (int j = i; j > 0; j--) {
if (a[j - 1] > a[j]) {
swap(&a[j - 1], &a[j]);
}
}
}
}
// Quick sort
size_t partition(int a[], size_t low, size_t high) {
const int pivot = a[low];
size_t offset = low;
for (size_t i = low + 1; i < high; i++) {
if (a[i] < pivot) {
swap(&a[offset], &a[i]);
offset++;
}
}
return offset + 1;
}
void quick_sort(int a[], size_t low, size_t high) {
if (low < high) {
int pivot = partition(a, low, high);
quick_sort(a, low, pivot - 1);
quick_sort(a, pivot + 1, high);
}
}
void q_sort(int a[], size_t size) {
return quick_sort(a, 0, size);
}
/* void static print(int *a, size_t size) { */
/* for (size_t i = 0; i < size; i++) { */
/* printf("%d ", a[i]); */
/* } */
/* printf("\n"); */
/* } */
long timeit(void (*action)(int[], size_t), int a[], size_t size) {
struct timespec tsi, tsf;
clock_gettime(CLOCK_MONOTONIC, &tsi);
action(a, size);
clock_gettime(CLOCK_MONOTONIC, &tsf);
double elaps_s = difftime(tsf.tv_sec, tsi.tv_sec);
// Just return the ns if the total time is less than 1s
assert(elaps_s == 0);
return tsf.tv_nsec - tsi.tv_nsec;
}
int main() {
int nums[SIZE], c1[SIZE], c2[SIZE];
srand(time(NULL)); // should only be called once
for (size_t i = 0; i < SIZE; i++) {
nums[i] = rand(); // [0, RAND_MAX]
}
printf("size, insertion sort, quick sort\n");
for (int range = 0; range <= SIZE; range++) {
double t1 = 0, t2 = 0;
for(int times = 0; times < TIMES; times++) {
// Copying the whole buffer might be even simpler than range
memcpy(c1, nums, sizeof nums[0] * SIZE);
memcpy(c2, nums, sizeof nums[0] * SIZE);
t1 += timeit(i_sort, c1, range);
t2 += timeit(q_sort, c2, range);
}
printf("%d, %f, %f\n", range, t1/TIMES, t2/TIMES);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment