Source

foobar-scripts / merge-sort-struct.c

Full commit
/* Simple Merge Sort implementation- sorts a collection of nodes, using only one of the data members for the sorting operation */

/* Amit Saha. <http://amitksaha.wordpress.com; amitsaha.in@gmail.com>
 */

# include <stdlib.h>
struct obj_values{
	int value;
	int ori_pos
};

int main(int argc, char **argv)
{
    struct obj_values *nodes = (struct obj_values *)malloc(10*sizeof(struct obj_values));
    int i;

    for(i=0;i<=9;i++)
    {
	    (nodes + i)->value= -2*i*i;
	    (nodes + i)->ori_pos=i;
    }
     
    merge_sort(nodes,0,9);

    for(i=0;i<=9;i++)
    {
	    printf("%d %d \n", (nodes + i)->ori_pos,(nodes + i)->value);
	    
    }

}


void merge_sort(struct obj_values *indices, int x, int z )
{
	int y;
	if(x<z){
		y = (x+z)/2;
		merge_sort(indices,x,y);
		merge_sort(indices,y+1,z);
		my_merge(indices,x,y,z);
	}
}

void my_merge(struct obj_values *indices, int x, int y, int z)
{
	struct obj_values *temp = (struct obj_values *)malloc((z-x+1)* sizeof(struct obj_values));

	int mark1=x, mark2=y+1;
	int cnt=0;

	while(mark1 <= y && mark2 <= z){
		if ((indices + mark1)->value < (indices + mark2)->value)
		{
			(temp + cnt)->value = (indices + mark1)->value;
			(temp + cnt)->ori_pos = (indices + mark1)->ori_pos;
			cnt++; mark1++;
		}

		else  	{
			(temp+cnt)->value = (indices+mark2)->value;
			(temp+cnt)->ori_pos = (indices+mark2)->ori_pos;
			cnt++; mark2++;

		}
	}
		while(mark1 <= y)
		{
			(temp + cnt)->value = (indices + mark1)->value;
			(temp + cnt)->ori_pos = (indices + mark1)->ori_pos;
			cnt++; mark1++;
		
		
		}

		while(mark2 <= z)

		{ 	(temp+cnt)->value = (indices+mark2)->value;
			(temp+cnt)->ori_pos = (indices+mark2)->ori_pos;
			cnt++; mark2++;


		}


		memcpy(indices + x,temp,(z - x + 1)*sizeof(struct obj_values));
		free(temp);
	}