Skip to content

Instantly share code, notes, and snippets.

@gustavorv86
Last active April 12, 2017 06:33
Show Gist options
  • Save gustavorv86/58ab804b274458438445adf1e6d9fd80 to your computer and use it in GitHub Desktop.
Save gustavorv86/58ab804b274458438445adf1e6d9fd80 to your computer and use it in GitHub Desktop.
Sort algorythms in C/C++
#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);
}
}
#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
#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