Bubblesort - Optimization

Content of the lesson:

When the counter reaches the value of variable n then the cycle is terminated and the program returns to the first FOR cycle. The first counter is then increased to value 2 and the inner FOR cycle starts. It will run until the second counter reaches the n-k value because the rest of the array has already been sorted so it is not required to browse it anymore.

One more thing remains to be explained - why does the first FOR cycle has the maximum value n-1 instead of n. It is because of the fact that you have to make n-1 comparisons for n elements - if you select the four biggest values of an array of 5 elements, it is clear that the last one will be the smallest one.

Thanks to the change from n-1 to n-k our program does not have to check all numbers in every step but it checks less and less numbers in each following step (because the value of k variable is increased permanently).

Sample: We have an array of 5 numbers

*this step will be skipped because there is no data to be compared to - it is shown only for the completeness of all "stairs".

Bubblesort - Variant 3

The third version - it is even more optimized than the previous ones because of removing several more problems from the previous versions.

WHILE

The first FOR cycle was replaced with the WHILE cycle which allows us to change the counter and to master the final number of steps (the FOR cycle has the possibility to change counter in a few programming languages but the WHILE cycle is more general and better manageable).

Because the basic version of C does not support boolean values (as Pascal for example) you have to use an integer value to store a boolean (0 for false, 1 for true). We added a variable s (sorted) and set it as FALSE (s=0;) before the cycle is launched. Immediately after the BEGIN command we can assume that the array is sorted and set s=1 - using this step we can handle a situation when all numbers have already been sorted but the cycle continues because of the counter.

In case that the array is not sorted (IF p[i]>p[i+1] condition is true), the s variable is set back to false (s=0;) and the WHILE cycle is repeated. Otherwise the WHILE cycle is terminated because there is no more data to process (s=1).

Difference between pmax-1 and pmax-k

The principle of stairs can be handled similarly to the second variant of cycle for (i=0; i < pmax-k; i++) - you can change pmax-1 to pmax-k. You should not forget to assign k:=0 before launching the WHILE cycle, otherwise the program would not function. There also cannot be value 2 for example because the array would not be browsed to the end. Then you have to increase the value of k by one after each step inside the WHILE cycle to create the principle of stairs. We improved several more possibilities which can occur when sorting an array and we reduced the number of steps so the algorithm can run faster.

The following graph compares numbers of browsed items and rows when using 10 000 items.

Bubblesort - Variant 4 - The Last Optimization

The last optimization is to speed up the whole sorting process. This variant does not only put the highest value to the end but it also puts the smallest value to the beginning inside one step. In every following step only numbers between 0+k and pmax-k are being processed (k is increased by one in each step). The schema looks like a reversed pyramid.

You can see a graph comparing this variant with the previous ones:

Source Code Used to Compare the Speed of Each Variant

#include "stdafx.h"#include <stdlib.h>
#include <time.h>

#define pmax 1000

int _tmain(int argc, _TCHAR* argv[])
{
	int p[pmax], pz[pmax];
	int s, pocetk, poceti, opakovani;
	int i, k;

	srand((unsigned int) time(NULL));

	opakovani = 0;

	while (opakovani < 10)
	{
		for (i = 0; i < pmax; i++)
		{
			p[i] = rand()%3000;
		}

		for (i = 0; i < pmax; i++)
		{
			pz[i] = p[i];
		}

		// start neoptimalizovane bez K
		pocetk = 0;
		poceti = 0;

		for (k = 0; k < pmax-1; k++)
		{
			for (i = 0; i < pmax-1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
				}
				poceti = poceti + 1;
			}
			pocetk = pocetk + 1;
		}
		printf("Pocet K neop: %d\n", pocetk);
		printf("Pocet I neop: %d\n", poceti);

		//konec neoptimalizovane bez K}
		//start neoptimalizovane s K}
		for (i = 0; i < pmax; i++)
		{
			p[i] = pz[i];
		}
		pocetk = 0;
		poceti = 0;

		for (k = 0; k < pmax-1; k++)
		{
			for (i = 0; i < pmax-k-1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
				}
				poceti = poceti + 1;
			}
			pocetk = pocetk + 1;
		}
		printf("Pocet K (s K): %d\n", pocetk);
		printf("Pocet I (s K): %d\n", poceti);
	
		//konec neoptimalizovane s K
		//start optimalizovane
		for (i = 0; i < pmax; i++)
		{
			p[i] = pz[i];
		}
		k = 0;
		pocetk = 0;
		poceti = 0;
		s = 0;

		while (s == 0)
		{
			s = 1;
			for (i = 0; i < pmax - k -1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
					s = 0;
				}
				poceti = poceti + 1;
			}
			k = k+1;
			pocetk = pocetk + 1;
		}
		printf("Pocet K optimal: %d\n", pocetk);
		printf("Pocet I optimal: %d\n", poceti);
		//konec optimalizovane
		//start optimalizovane 2
		for (i = 0; i < pmax; i++)
		{
			p[i] = pz[i];
		}
		k = 0;
		pocetk = 0;
		poceti = 0;
		s = 0;

		while (s == 0)
		{
			s = 1;
			for (i = 0+k; i < pmax-k -1; i++)
			{
				if (p[i]>p[i+1])
				{
					int pom = p[i];
					p[i] = p[i+1];
					p[i+1] = pom;
					s = 0;
				}
				poceti = poceti + 1;
			}

			for (i = pmax-k-1; i > 1+k; i--)
			{
				if (p[i]<p[i-1])
				{
					int pom = p[i];
					p[i] = p[i-1];
					p[i-1] = pom;
					s = 0;
				}
				poceti = poceti + 1;
			}

			k=k+1;
			pocetk=pocetk+2;
		}

		printf("Pocet K optimal2: %d\n",pocetk);
		printf("Pocet I optimal2: %d\n",poceti);
		// konec optimalizovane 2
		opakovani=opakovani+1;
		printf("Pocet kompletniho cyklu %d\n",opakovani);
		printf("\n");
	}
	fflush(stdin);
	getchar();
	return 0;
}

Homework

Find at least two more samples of sorting algorithms and realize one of them in C language.

Questions

1. Describe the principle of the BubbleSort algorithm.
2. Which optimizations can be used for the BubbleSort algorithm?
3. Find at least two more samples of sorting algorithms.