Smoothsort

Here given code implementation process.

//C program for
//Sort the words elements by using smoothsort
#include <stdio.h>

#include <string.h>

struct state
{
	const char **record;
	size_t q, r, p, b, c, r1, b1, c1;
};
//Compare two string elements
int compare(const char *a , const char *b)
{
	return strcmp(a, b);
}
void up(size_t *a, size_t *b)
{
	size_t temp;
	temp = *a;*a += *b + 1;*b = temp;
}
void down(size_t *a, size_t *b)
{
	size_t temp;
	temp = *b;*b = *a - *b - 1;*a = temp;
}
void sift(struct state *s)
{
	int r0 = s->r1;
	int r2 = 0;
	const char *temp = s->record[r0];
	while (s->b1 > 2)
	{
		r2 = s->r1 - s->b1 + s->c1;
		if (compare(s->record[s->r1 - 1], s->record[r2]) >= 0)
		{
			r2 = s->r1 - 1;
			down( & s->b1, & s->c1);
		}
		if (compare(s->record[r2], temp) < 0)
		{
			s->b1 = 1;
		}
		else
		{
			s->record[s->r1] = s->record[r2];
			s->r1 = r2;
			down( & s->b1, & s->c1);
		}
	}
	if (s->r1 - r0 > 0)
	{
		s->record[s->r1] = temp;
	}
}
void trinkle(struct state *s)
{
	int p1 = s->p;
	int r0 = s->r1;
	int r2 = 0;
	int r3 = 0;
	const char *temp = s->record[r0];
	s->b1 = s->b;
	s->c1 = s->c;
	while (p1 > 0)
	{
		while ((p1 & 1) == 0)
		{
			p1 >>= 1;
			up( & s->b1, & s->c1);
		}
		r3 = s->r1 - s->b1;
		if (p1 == 1 || compare(s->record[r3], temp) < 0)
		{
			p1 = 0;
		}
		else
		{
			p1--;
			if (s->b1 == 1)
			{
				s->record[s->r1] = s->record[r3];
				s->r1 = r3;
			}
			else if (s->b1 >= 3)
			{
				r2 = s->r1 - s->b1 + s->c1;
				if (compare(s->record[s->r1 - 1], s->record[r2]) >= 0)
				{
					r2 = s->r1 - 1;
					down( & s->b1, & s->c1);
					p1 <<= 1;
				}
				if (compare(s->record[r2], s->record[r3]) < 0)
				{
					s->record[s->r1] = s->record[r3];
					s->r1 = r3;
				}
				else
				{
					s->record[s->r1] = s->record[r2];
					s->r1 = r2;
					down( & s->b1, & s->c1);
					p1 = 0;
				}
			}
		}
	}
	if (s->r1 - r0 != 0)
	{
		s->record[s->r1] = temp;
	}
	sift(s);
}
void semi_trinkle(struct state *s)
{
	const char *temp;
	s->r1 = s->r - s->c;
	if (compare(s->record[s->r1], s->record[s->r]) >= 0)
	{
		temp = s->record[s->r];
		s->record[s->r] = s->record[s->r1];
		s->record[s->r1] = temp;
		trinkle(s);
	}
}
void smooth_sort(const char **a, int size)
{
	struct state s;
	//set initial values
	s.record = a;
	s.r = 0;
	s.p = 1;
	s.b = 1;
	s.c = 1;
	int temp = 0;
	int work = 1;
	//Build tree 
	for (s.q = 1; s.q < size; s.q++)
	{
		s.r1 = s.r;
		if ((s.p & 7) == 3)
		{
			s.b1 = s.b;
			s.c1 = s.c;
			sift( & s);
			s.p = (s.p + 1) >> 2;
			/*Two "up"s, saves us a little time */
			temp = s.b + s.c + 1;
			s.b += temp + 1;
			s.c = temp;
		}
		else if ((s.p & 3) == 1)
		{
			if (s.q + s.c < size)
			{
				s.b1 = s.b;
				s.c1 = s.c;
				sift( & s);
			}
			else
			{
				trinkle( & s);
			}
			work = 1;
			while (work == 1)
			{
				work = 0;
				down( & s.b, & s.c);
				s.p <<= 1;
				if (s.b > 1)
				{
					work = 1;
				}
			}
			s.p++;
		}
		s.r++;
	}
	s.r1 = s.r;
	trinkle( & s);
	//Build sorted array 
	while (s.q--> 1)
	{
		if (s.b == 1)
		{
			s.r--;
			s.p--;
			while ((s.p & 1) == 0)
			{
				s.p >>= 1;
				up( & s.b, & s.c);
			}
		}
		else if (s.b > 2)
		{
			s.p--;
			s.r = s.r - s.b + s.c;
			if (s.p > 0)
			{
				semi_trinkle( & s);
			}
			down( & s.b, & s.c);
			s.p = (s.p << 1) + 1;
			s.r += s.c;
			semi_trinkle( & s);
			down( & s.b, & s.c);
			s.p = (s.p << 1) + 1;
		}
	}
}
//This are display the elements of given collection 
void display(const char *collection[], int size)
{
	int i = 0;
	for (i = 0; i < size; ++i)
	{
		//Display elements
		printf("%s\n", collection[i]);
	}
}
int main()
{
	//Define the string word
	const char *collection[] = {
		"time" , "life" , "dear" , "zero" , "moon" , "crazy" , "approach" , "code" , "today" , "sun" , "date"
	};
	//Get the size of unsorted elements
	int size = sizeof(collection) / sizeof(collection[0]);
	printf("Before Sort : \n");
	display(collection, size);
	//Perform the smooth sort
	smooth_sort(collection, size);
	printf("\nAfter Sort : \n");
	display(collection, size);
	return 0;
}

Output

Before Sort :
time
life
dear
zero
moon
crazy
approach
code
today
sun
date

After Sort :
approach
code
crazy
date
dear
life
moon
sun
time
today
zero


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved