Last active
April 12, 2017 06:33
-
-
Save gustavorv86/58ab804b274458438445adf1e6d9fd80 to your computer and use it in GitHub Desktop.
Sort algorythms in C/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 "sort.h" | |
#include <stdlib.h> | |
#define SWAP(a, b, tmp) ((tmp)=(a), (a)=(b), (b)=(tmp)) | |
void bubble_sort(float*array, int size) { | |
int i, j; | |
float tmp; | |
for (i = 0; i < size; i++) { | |
for (j = (i + 1); j < size; j++) { | |
if (array[i] > array[j]) { | |
SWAP(array[i], array[j], tmp); | |
} | |
} | |
} | |
} | |
void insertion_sort(float *array, int size) { | |
int i, j; | |
float tmp; | |
for (i = 1; i < size; ++i) { | |
tmp = array[i]; | |
j = i; | |
while (j > 0 && tmp < array[j - 1]) { | |
array[j] = array[j - 1]; | |
j--; | |
} | |
array[j] = tmp; | |
} | |
} | |
void merge_sort(float* array, int start, int end) { | |
float* tmp_array; | |
int center, i, tmp_i, lo_i1, lo_i2; | |
if (end - start < 2) { | |
return; | |
} | |
center = start + (end - start) / 2; | |
/* sort array for 'lo' to 'center-1' */ | |
merge_sort(array, start, center); | |
/* sort array for 'center' to 'hi-1' */ | |
merge_sort(array, center, end); | |
tmp_array = (float*) malloc((end-start) * sizeof(float)); | |
tmp_i = 0; | |
/* | |
merge two subarrays into 'tmp_array': | |
first subarray: for 'array[lo]' to 'array[center-1]' | |
second subarray: for 'array[center]' to 'array[hi-1]' | |
*/ | |
lo_i1 = start; | |
lo_i2 = center; | |
while (lo_i1 < center || lo_i2 < end) { | |
if (lo_i2 == end) { | |
tmp_array[tmp_i++] = array[lo_i1++]; | |
} else if (lo_i1 == center) { | |
tmp_array[tmp_i++] = array[lo_i2++]; | |
} else if (array[lo_i1] < array[lo_i2]) { | |
tmp_array[tmp_i++] = array[lo_i1++]; | |
} else { | |
tmp_array[tmp_i++] = array[lo_i2++]; | |
} | |
} | |
/* copy 'tmp_array' into 'array' */ | |
tmp_i = 0; | |
for (i = start; i < end; i++) { | |
array[i] = tmp_array[tmp_i++]; | |
} | |
free(tmp_array); | |
} | |
void quick_sort(float* array, int start, int end) { | |
int lo, hi; | |
float tmp, pivot; | |
if(start < end){ | |
lo = start+1; | |
hi = end; | |
pivot = array[start]; | |
while(lo < hi){ | |
if(array[lo] <= pivot) { | |
lo++; | |
} else if(array[hi] >= pivot) { | |
hi--; | |
} else { | |
SWAP(array[lo], array[hi], tmp); | |
} | |
} | |
if(array[lo] < pivot){ | |
SWAP(array[lo], array[start], tmp); | |
lo--; | |
} else { | |
lo--; | |
SWAP(array[lo], array[start], tmp); | |
} | |
quick_sort(array, start, lo); | |
quick_sort(array, hi, end); | |
} | |
} |
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
#ifndef SORT_H | |
#define SORT_H | |
void bubble_sort(float*array, int size); | |
void insertion_sort(float *array, int size); | |
void merge_sort(float* array, int lo, int hi); | |
void quick_sort(float* array, int lo, int hi); | |
#endif |
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 <time.h> | |
#include "sort.h" | |
int main(int argc, char** argv) { | |
int i; | |
int size = 128; | |
float* array; | |
array = malloc(size * sizeof(float)); | |
srand(time(NULL)); | |
for(i=0; i<size; i++) { | |
array[i] = rand() % 60; | |
} | |
quick_sort(array, 0, size); | |
for(i=0; i<size; i++) { | |
printf("%f\n",array[i]); | |
} | |
return (EXIT_SUCCESS); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment