Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
In-place merge sort
#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;i++){
if(i>0) printf(",");
printf("%d",*(a+i));
}
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>0){
i++;
}
}
return sample_data;
}
int* shuffle(int* data, int n, int* random_data){
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;
}
return random_data;
}
int assert(int* a, int* b, int n){
if(memcmp(a,b,n)){
return 0;
}else{
return 1;
}
}
int find_last_less( int* p, int n, int key )
{
// if the first element of given list is NOT smaller than key
if ( !(p[0]<key) ){
return -1;
}
// if the last element of given list is smaller than key
if ( p[n-1]<key ){
return n-1;
}
// binary search to find the index of an element
// which devides the list by the key
int less=0;
int ge=n-1;
while( less+1<ge ){
int mid = less + (ge-less)/2;
if ( p[ mid ]<key ){
less = mid;
} else {
ge = mid;
}
}
// The last index which is less than key
// Note that less must be less than key
return less;
}
// Least Common Multiple
// = Greatest Common Divisor (GCD)
int gcd( int a, int b )
{
for(;;){
if ( b==0 ){
return a;
}
int c = a%b;
a=b;
b=c;
}
}
void rot_left( int * p, int size, int rot )
{
//
// * Example to explain rotation * //
//
// original p = { 0,2,4,6,8, 1,2,3,4,5 }
// Just suppose key = 5
// rot_left p = { 6,8, 1,2,3,4, (5) }
//
// size = 6 ( p = { < 6,8, 1,2,3,4 > ,5 }
// rot = 2 ( p = { < 6,8 >, 1,2,3,4,5 }
//
// then, gcd is 2 and rotate as follows
// { < 6,8, 1,2,3,4 > ,5 } <= rot_left p
// { < 1,8, 3,2,6,4 > ,5 }
// { < 1,2, 3,4,6,8 > ,5 }
//
int g = gcd( size, rot );
for( int start=0 ; start<g ; ++start ){
int i=( start + rot )%size;
int head = p[i];
while( i != start ){
int next = ( i+rot )%size;
p[i] = p[ next ];
i=next;
}
p[start]=head;
}
}
void merge( int * p, int left, int right )
{
// left is the number of the left list
// right is the number of the right list
if ( left==0 || right==0 ){
return;
}
// p[left-1] is the laste element of left
// [[left] is the first element of right
if ( p[ left-1 ]<=p[ left ] ){
// Right list is already bigger than or equal to left list.
// No need to merge anymore.
return;
}
if ( left==1 && right ==1 ){
if ( p[1]<p[0] ){
int t;
t=p[1]; p[1]=p[0]; p[0]=t;
}
return;
}
// Take the middle of list as a key
int key = left<right ? p[ left + (right+1)/2 ] : p[ (left+1)/2 ];
// If the key is smaller than right and left list, change the key
if ( key <= p[ left ] && key <= p[0] ){
// Take the last bigger element of right or left list
key = p[left-1]<p[left+right-1] ? p[left+right-1] : p[left-1];
}
// find the index which points to the biggest one less than key
int mL = find_last_less( p, left, key );
int mR = find_last_less( p+left, right, key );
// This is the first index which points to the smallest one larger than key
int mLL = mL + 1;
int mRL = mR + 1;
// The number of values which is larger than key in each list
int mLGE = left-mLL;
int mRGE = right - mRL;
// e.g.
// p = { 0,2,4,6,8, 1,2,3,4,5 }
// - left = { 0,2,4,6,8 }
// - right= { 1,2,3,4,5 }
// key = 5
//
// mL = 2 (index points to 4 in left)
// mLL = 3 (mL + 1)
// mLGE = 2 (The size of left(5) - mLL)
//
// mR = 3 (index points to 4 in right)
// mRL = 4
// mRGE = 1 (The size of right(5) - mRL)
// 1st: Pointer points to the first argument larger than the key
// in the left list
// 2nd: The number of values larger than the key in the left list
// + the first index larger than the key in the right list
// 3rd: The number of values larger than the key in the left list
rot_left( p+mLL, mLGE + mRL, mLGE );
// After rotation, p+mLL is
// { < 1,2, 3,4,6,8 > ,5 }
// Then p is
// { 0,2,4, 1,2, 3,4,6,8 ,5 }
//
// Divide this list for four lists as follows
// left is { 0,2,4 }, right { 1,2 }
merge( p, mLL, mRL );
// left is { 3,4,6,8 }, right { 5 }
merge( p+mLL+mRL, mLGE, mRGE );
}
void in_place_merge_sort(int *data, int n){
if(n<=1) return;
if(n==2){
if(data[1]<data[0]){
int t=data[0];
data[0]=data[1];
data[1]=t;
}
return;
}
int half = n/2;
in_place_merge_sort(data,half);
in_place_merge_sort(data+half,n-half);
merge(data,half,n-half);
}
void do_assert(int* sample_data, int* sorted_data, int n){
if(assert(sample_data,sorted_data,n)){
printf("Sorted check OK.\n");
}else{
printf("Sorted check NG.\n");
print(sample_data,n>100?100:n);
print(sorted_data,n>100?100:n);
}
}
int main(int argc, char *argv[]){
if(argc<2){ printf("Give # of samples.\n"); exit(1); }
int n = atoi(argv[1]);
int *sample_data;
struct timeval s, e;
//srand((unsigned) time(NULL));
srand(100);
sample_data = sample(n);
int* random_data = (int*)malloc(sizeof(int)*n);
shuffle(sample_data,n,random_data);
gettimeofday(&s,NULL);
in_place_merge_sort(random_data,n);
gettimeofday(&e,NULL);
printf("In place merge sort : %.2lf sec.\n",print_time(&s,&e));
do_assert(sample_data,random_data,n);
return 0;
}
Owner

nishidy commented Dec 10, 2016 edited

$ gcc -W -O3 in_place_merge_sort.c -o in_place_merge_sort
$ ./in_place_merge_sort 100000000
In place merge sort : 178.77 sec.
Sorted check OK.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment