Skip to content

Instantly share code, notes, and snippets.

@aajjbb
Created November 22, 2014 02:43
Show Gist options
  • Save aajjbb/d674bca3ddc075ed404d to your computer and use it in GitHub Desktop.
Save aajjbb/d674bca3ddc075ed404d to your computer and use it in GitHub Desktop.
A few wrap of sorting algorithms to remember a little of pointer arithmetics in C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXL 15
#define MAX_VALUE 10;
int* generate(void) {
int i;
int* array = (int*) malloc(MAXL * sizeof(int));
if (array == NULL) {
fprintf(stderr, "unable to allocate memory");
exit(0);
}
for (i = 0; i < MAXL; i++) {
array[i] = rand() % MAX_VALUE;
}
return array;
}
void print(int* array, int len) {
int i;
for (i = 0; i < len; i++) {
printf("%d ", *(array + i));
}
printf("\n");
}
//O(n^2)
void bubble_sort(int* array, int len) {
int i, j;
for (i = 0; i < len; i++) {
for (j = i + 1; j < len; j++) {
if (array[j] < array[i]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
//O(n^2)
void selection_sort(int* array, int len) {
int i, j;
for (i = 0; i < len; i++) {
int pos = i;
int value = array[i];
for (j = i; j < len; j++) {
if (array[j] < value) {
value = array[j];
pos = j;
}
}
if (pos != i) {
int tmp = array[i];
array[i] = array[pos];
array[pos] = tmp;
}
}
}
//O(n^2)
void insertion_sort(int* array, int len) {
int i, j;
for (i = 1; i < len; i++) {
j = i;
while (j - 1 >= 0 && array[j] < array[j - 1]) {
int tmp = array[j];
array[j] = array[ + j - 1];
array[j - 1] = tmp;
j -= 1;
}
}
}
//Helper method for quicksort
void quick_sort_helper(int* array, int l, int r, int len) {
int bound_l = l;
int bound_r = r;
int pivot = array[(l + r) / 2];
do {
while (array[l] < pivot) {
l += 1;
}
while (array[r] > pivot) {
r -= 1;
}
if (l <= r) {
int tmp = array[l];
array[l] = array[r];
array[r] = tmp;
l += 1;
r -= 1;
}
} while (l <= r);
if (r > bound_l) {
quick_sort_helper(array, bound_l, r, len);
}
if (l < bound_r) {
quick_sort_helper(array, l, bound_r, len);
}
}
//O(n*log(n)) but can be O(n^2)
void quick_sort(int* array, int len) {
quick_sort_helper(array, 0, len - 1, len);
}
int main(int argc, char** argv) {
srand(time(NULL));
int* array = generate();
print(array, MAXL);
quick_sort(array, MAXL);
print(array, MAXL);
free(array);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment