Skip to content

Instantly share code, notes, and snippets.

@nishidy nishidy/sorts.c
Last active Nov 4, 2016

Embed
What would you like to do?
Run sort algorithms with randomized single data
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
void print(int* a, int n){
int i=0;
printf("[");
for(i=0;i<(n>100?100:n);i++){
if(i>0) printf(",");
printf("%d",*(a+i));
}
if(n>100) printf("...");
printf("]\n");
}
double print_time(struct timeval *s, struct timeval *e){
int si = (s->tv_sec%1000000)*1000+s->tv_usec/1000;
int ei = (e->tv_sec%1000000)*1000+e->tv_usec/1000;
return (double)(ei-si)/1000.0;
}
int* sample(int n){
int* sample_data = (int*)malloc(sizeof(int)*n);
int i=0;
int j=0;
while(j<n){
if(rand()%2){
*(sample_data+j) = i;
j++;
if(rand()%100){
i++;
}
}else{
i++;
}
}
return sample_data;
}
int* sample_input(int n, char** argv){
int* sample_data = (int*)malloc(sizeof(int)*n);
int i;
for(i=0;i<n;i++){
*(sample_data+i) = atoi(*(argv+i));
}
return sample_data;
}
int* shuffle(int* data, int n){
int* random_data = (int*)malloc(sizeof(int)*n);
memcpy(random_data,data,sizeof(int)*n);
int s = rand()%n;
int i, d, tmp;
for(i=0;i<n;i++){
d = rand()%n;
tmp = *(random_data+d);
*(random_data+d) = *(random_data+s);
*(random_data+s) = tmp;
s = d;
//print(random_data,n);
}
return random_data;
}
int assert(int* a, int* b, int n){
int i=0;
if(memcmp(a,b,n)){
return 0;
}else{
// memcmp returns 0 if they are same
return 1;
}
}
int* quick_sort(int *data, int n){
int pivot = *data;
int *sg = (int*)malloc(sizeof(int)*n); // small group
int *lg = (int*)malloc(sizeof(int)*n); // large group
int i;
int sgi=0;
int lgi=0;
for(i=1;i<n;i++){
if(*(data+i) < pivot){
*(sg+sgi) = *(data+i);
sgi++;
}
}
for(i=1;i<n;i++){
if(*(data+i) >= pivot){
*(lg+lgi) = *(data+i);
lgi++;
}
}
int *sorted_sg, *sorted_lg;
if(sgi>0){
sg = quick_sort(sg,sgi);
}
if(lgi>0){
lg = quick_sort(lg,lgi);
}
int *new = (int*)malloc(sizeof(int)*n);
for(i=0;i<sgi;i++){
*(new+i) = *(sg+i);
}
*(new+sgi) = pivot;
for(i=0;i<lgi;i++){
*(new+sgi+1+i) = *(lg+i);
}
free(sg);
free(lg);
return new;
}
int* merge_sort(int *data, int n){
if(n==1){
return data;
}else{
int *left = (int*)malloc(sizeof(int)*n);
int *right = (int*)malloc(sizeof(int)*n);
int half = n/2;
int i;
for(i=0;i<half;i++){
*(left+i) = *(data+i);
}
for(i=half;i<n;i++){
*(right+i-half) = *(data+i);
}
left = merge_sort(left,half);
right = merge_sort(right,n-half);
int left_idx=0;
int right_idx=0;
int *new = (int*)malloc(sizeof(int)*n);
while(left_idx<half || right_idx<n-half){
if(left_idx == half){
*(new+left_idx+right_idx) = *(right+right_idx);
right_idx++;
}else if(right_idx == n-half){
*(new+left_idx+right_idx) = *(left+left_idx);
left_idx++;
}else if( *(left+left_idx) < *(right+right_idx) ){
*(new+left_idx+right_idx) = *(left+left_idx);
left_idx++;
}else{
*(new+left_idx+right_idx) = *(right+right_idx);
right_idx++;
}
}
free(left);
free(right);
return new;
}
}
int* bubble_sort(int *data, int n){
int i, tmp, m;
m = n;
while(m>1){
for(i=0;i<m-1;i++){
if(*(data+i)>*(data+i+1)){
tmp = *(data+i+1);
*(data+i+1) = *(data+i);
*(data+i) = tmp;
}
}
m--;
}
return data;
}
void do_assert(int* data, int* random_data, int* sorted_data, int n){
if(assert(sorted_data,data,n)){
printf("Sorted check OK.\n");
}else{
print(data,n);
print(random_data,n);
print(sorted_data,n);
}
}
int main(int argc, char *argv[]){
//printf("%d\n",RAND_MAX);
int n = atoi(argv[1]);
int *sample_data;
int* sorted_data;
struct timeval s, e;
if(argc>2){
sample_data = sample_input(n,argv+2);
gettimeofday(&s,NULL);
sorted_data = quick_sort(sample_data,n);
gettimeofday(&e,NULL);
printf("Quick sort : %.2lf sec.\n",print_time(&s,&e));
print(sorted_data,n);
gettimeofday(&s,NULL);
sorted_data = merge_sort(sample_data,n);
gettimeofday(&e,NULL);
printf("Merge sort : %.2lf sec.\n",print_time(&s,&e));
print(sorted_data,n);
if(n<=50000){
gettimeofday(&s,NULL);
sorted_data = bubble_sort(sample_data,n);
gettimeofday(&e,NULL);
printf("Bubble sort : %.2lf sec.\n",print_time(&s,&e));
print(sorted_data,n);
}
}else{
sample_data = sample(n);
int *random_data = shuffle(sample_data,n);
gettimeofday(&s,NULL);
sorted_data = quick_sort(random_data,n);
gettimeofday(&e,NULL);
printf("Quick sort : %.2lf sec.\n",print_time(&s,&e));
do_assert(sample_data,random_data,sorted_data,n);
gettimeofday(&s,NULL);
sorted_data = merge_sort(random_data,n);
gettimeofday(&e,NULL);
printf("Merge sort : %.2lf sec.\n",print_time(&s,&e));
do_assert(sample_data,random_data,sorted_data,n);
if(n<=50000){
gettimeofday(&s,NULL);
sorted_data = bubble_sort(random_data,n);
gettimeofday(&e,NULL);
printf("Bubble sort : %.2lf sec.\n",print_time(&s,&e));
do_assert(sample_data,random_data,sorted_data,n);
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.