Created
November 22, 2014 02:43
-
-
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
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 <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