Skip to main content

Smoothsort

Smoothsort is a comparison-based sorting algorithm that was developed by Edsger Dijkstra in 1981. It is a variation of heapsort that uses a data structure known as a Leonardo heap to efficiently sort a list.

The basic idea behind Smoothsort is to perform a series of heap operations on the list being sorted, gradually transforming it into a sorted sequence. Unlike traditional heapsort, which uses a binary heap data structure, Smoothsort uses a heap data structure known as a Leonardo heap, which is a special type of binary tree that is composed of a sequence of Leonardo numbers.

During the sorting process, Smoothsort maintains a "tree-like" structure of Leonardo heaps that is used to keep track of the current state of the list being sorted. The algorithm begins by partitioning the list into a series of "subheaps", each of which is either a single element or a Leonardo heap. It then iteratively merges adjacent subheaps together, while maintaining the heap property of the resulting merged heap.

Smoothsort has a worst-case time complexity of O(n log n), which is the same as heapsort. However, in practice, Smoothsort tends to be faster than heapsort on partially sorted lists, since it takes advantage of the existing order in the input to minimize the number of comparisons and swaps needed to sort the list.

Overall, Smoothsort is an interesting and efficient sorting algorithm that is not as well-known as some of the more popular sorting algorithms like quicksort or mergesort.

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

Smoothsort works by using a data structure called a Leonardo Heap, which is a specialized form of binary heap. The basic idea is to partition the input list into sub-heaps, which are either single elements or Leonardo Heaps, and then merge them together in a way that maintains the heap property.

Here's a step-by-step overview of how Smoothsort works:

  1. Initialize the Leonardo Heap data structure with an empty heap.
  2. Partition the input list into sub-heaps, starting from the leftmost element. For each element, compare it with the two previous elements in the list. If it is smaller than both of them, create a new sub-heap consisting of that element. If it is larger than both of them, merge the two previous sub-heaps together to form a new sub-heap, and then recursively merge that sub-heap with any existing sub-heaps that it violates the heap property of.
  3. Once all elements have been processed, merge all sub-heaps together into a single, sorted sequence. This is done by repeatedly extracting the minimum element from the top of each sub-heap and adding it to the output list, until all elements have been extracted.

The key to the efficiency of Smoothsort is the use of the Leonardo Heap data structure, which allows for efficient merging of sub-heaps without requiring expensive re-heapifying operations. The use of sub-heaps also allows Smoothsort to take advantage of existing order in the input list, resulting in fewer comparisons and swaps than some other sorting algorithms.





Comment

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