Skip to content

Instantly share code, notes, and snippets.

@ahirschberg
Last active February 16, 2017 02:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ahirschberg/4c6f22bfc60ddaac70822949e6b3b02d to your computer and use it in GitHub Desktop.
Save ahirschberg/4c6f22bfc60ddaac70822949e6b3b02d to your computer and use it in GitHub Desktop.
C Code for a CS2110 Sort Example, and my system output
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#define OFFSET(arr, idx, size) ((void*) ((char*)arr) + ( idx ) * ( size ) )
// bubble sort http://www.algolist.net/Algorithms/Sorting/Bubble_sort
void yoursort(void *arr, size_t nelems, size_t size, int (*compar) (const void *, const void *)) {
bool swapped = true;
int j = 0;
// we use malloc because we have no idea what size the tmp variable is gonna be...
void* tmp = malloc(size);
while(swapped) {
swapped = false;
j++;
for (int i = 0; i < nelems - j; i++) {
if (compar(OFFSET(arr, i, size), OFFSET(arr, i + 1, size)) > 0) { // these lines do the following:
memcpy(tmp, OFFSET(arr, i, size), size); // tmp = arr[i]
memcpy(OFFSET(arr, i, size), OFFSET(arr, i + 1, size), size); // arr[i + 1] = arr[i]
memcpy(OFFSET(arr, i + 1, size), tmp, size); // arr[i] = tmp
swapped = true;
}
}
}
free(tmp); // don't forget to free temp at the end
}
typedef struct WEIRDSIZE {
int fill1;
short val;
char fill2;
} WS;
int ws_cmp(const void* a, const void* b) {
return ((WS*)a)->val - ((WS*)b)->val;
}
void ws_print(WS data) {
printf("WS: %d\n", data.val);
}
WS ws_new(short data) {
return (WS) {.fill1 = -1, .fill2 = -1, .val = data};
}
int main(int argc, char *argv[])
{
printf("struct WEIRDSIZE has a sizeof %ld on your system.\n", sizeof(WS));
WS arr[] = {ws_new(5), ws_new(4), ws_new(6), ws_new(1), ws_new(0), ws_new(2), ws_new(3)};
int n = 7;
printf("Before sort:\n");
for (int i = 0; i < n; i++) {
ws_print(arr[i]);
}
printf("Sorting with yoursort(arr=%p, n=%d, sizeof=%ld, func=%p)\n", arr, n, sizeof(WS), ws_cmp);
yoursort(arr, n, sizeof(WS), ws_cmp);
for (int i = 0; i < n; i++) {
ws_print(arr[i]);
}
printf("\n");
return 0;
}
===== Output on my system =====
struct WEIRDSIZE has a sizeof 8 on your system.
Before sort:
WS: 5
WS: 4
WS: 6
WS: 1
WS: 0
WS: 2
WS: 3
Sorting with yoursort(arr=0x7ffd7f5a54a0, n=7, sizeof=8, func=0x400736)
WS: 0
WS: 1
WS: 2
WS: 3
WS: 4
WS: 5
WS: 6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment