Impractical sorts - meaningless and merciless

And what are we all about smart and efficient algorithms? And let's dispel this dreary autumn Friday with something counterproductive !?

I present to your attention the TOP-5 of the most unconventional sortings of all time.

This is useful for young programmers to show for didactic purposes. All the rest will be amused at least.

Swamp Sort (BogoSort)

With this sorting you need to be extremely careful. Inadvertently landed in a quagmire, you risk perishing forever.

The principle is simple as mold. Shake the array until it is suddenly sorted. The process can happily end immediately, or it can last until the thermal death of the universe. That's how lucky.

Average time complexity: O (nxn!). There is also a better one: Ω (n). Interestingly, the worst temporal complexity of this algorithm is unknown to science.

Neatly. A code to get stuck in.

import java.util.Random;
publicclassBogoSortAlgorithmextendsSortAlgorithm{
	//Если есть массив, значит его можно отсортироватьpublicvoidsort(int data[])throws Exception {
		if (data.length > 0) runBogoSort(data);
	}
	//А вот и сортировочное болотоprivatevoidrunBogoSort(int data[])throws Exception {
		Random generator;
		int tempVariable;
		int randomPosition;
		do {
			generator = new Random();
			for (int i = 0; i < data.length; i++) {
				randomPosition = generator.nextInt(data.length);
				tempVariable = data[i];
				data[i] = data[randomPosition];
				data[randomPosition] = tempVariable;
				pause(i,randomPosition);
			}
		} while(!isSorted(data)); //Пока не отсортируем
	}
	//Проверяем, отсортирован ли массивprivatebooleanisSorted(int data[]){
		for (int i = 1; i < data.length; i++)
			if (data[i] < data[i - 1]) returnfalse;
		returntrue;
	}
}

Bozo Clown Sort (BozoSort)

Where BogoSort is, there is BozoSort. The Bozo baby clown sorting method is easy to explain even to a three-year-old child. We randomly select two elements, swap them, and check to see if this has led to success. If not, then we repeat the same actions - and so on until the end.

It may seem that BozoSort is the same as BogoSort, but it is only at first glance. Clown Bozo sorts with an average time complexity of O (nxn!) And this is also the upper time limit.

UPD. As rightly pointed out to me burdakovd and SkidanovAlexin comments and private messages, sorting the Bozo clown, like BogoSort, has no upper limit for the worst time complexity. Indeed, where does it come from, if in the worst case, in an unsorted array, the random will forever interchange the same two elements !?

I also note that, nevertheless, BozoSort will still sort on average faster than BogoSort. Just because after each exchange the array is checked for ordering. In BogoSort, there are frequent cases when the array is in an ordered state, but if at this moment you do not check, but mix further, then the desired state of sorting is lost for a while.

Clown Bozo is also sparklingly programming.

import java.util.Random;
classBozoSortAlgorithmextendsSortAlgorithm{
    voidsort(int a[])throws Exception {
		boolean sorted = false; //Считаем что не отсортированоwhile (!sorted) {
			//Берём наугад два элемента массива...int index1 = Randomize(a.length);
			int index2 = Randomize(a.length);
			//... и меняем их местамиint temp = a[index2];
			a[index2] = a[index1];
			a[index1] = temp;
			pause(index1, index2);
			//Отсортировали?
			sorted = true;
			for (int i = 1; i < a.length; i++)  {			
				if (a[i-1] > a[i]) {				
					pause(i, i-1);
					sorted = false;
					break;					
				}				
			}
		}
    } 	
	//Выбираем в массиве случайный индексprivateintRandomize( int range ){
		double  rawResult;
		rawResult = Math.random();
		return (int) (rawResult * range);
    }
}

Permutation Sort (PermSort)

Let us take a look at the task of sorting through the prism of combinatorics. Any array is an ordinary finite set of n elements for which n! permutations. Some of them are an array in an ordered state. Having compiled an algorithm for enumerating all the permutations, we will inevitably find the same one.

The worst time difficulty, like the Bozo clown, is O (n x n!). But with the best things are better - O (n).

Elegant enumeration of all permutations of an array.

classPermSortAlgorithmextendsSortAlgorithm{
	//Отсортировали подмассив?booleanissorted(int a[], int i)throws Exception {
		for (int j = a.length-1; j > 0; j--) {
			//Сравниваем и если что - меняем
			compex(j, j - 1);
			if(a[j] < a[j - 1]) {
				returnfalse;
			}
		}
		returntrue;
    }
	//Рекурсивный PermSortbooleansort(int a[], int i)throws Exception {
		int j;
		// Проверка на упорядоченность подмассиваif (issorted(a, i)) {
			returntrue;
		}
		// Подмассив не отсортирован. // Поэтому перебираем перестановки элементов.		for(j = i+1; j < a.length; j++) {			
			compex(i, j); 
			//Попробуем-ка переставитьint T = a[i];
			a[i] = a[j];
			a[j] = T;
			//Рекурсивно призываем новую перестановкуif(sort(a, i + 1)) {
				returntrue;
			}
			//Возврат к исходному состоянию
			T = a[i];
			a[i] = a[j];
			a[j] = T;
		}
		returnfalse;
    }
	//Сортируем исходный массив с помощью алгоритма PermSort.voidsort(int a[])throws Exception {
		sort(a, 0);
    }
}

Silly Sort (Stooge sort)

The sorting is named after the comic troupe Three Stooges, which amused the American public in the last century: from the early 1930s to the late 1960s. By the way, there were six total “idiots”; over 4 decades of creative activity, the composition of the trio sometimes changed.

The jolly trinity specialized in farce and clowning. Sorting also behaves: like a caricature character, she madly rushes about in an array; as it should be in the buffoonery - after ridiculous adventures with the main character, everything is fine. Array sorted, happy end.

The algorithm is witty recursive.

classStoogeSortAlgorithmextendsSortAlgorithm{
	voidsort(int a[], int lo, int hi)throws Exception {
		//Сравниваем/меняем элементы на концах отрезкаif(a[lo] > a[hi]) {
			int T = a[lo];
			a[lo] = a[hi];
			a[hi] = T;
		}
		//Меньше трёх?if(lo + 1 >= hi) return;
		//Чему равна одна треть?int third = (hi - lo + 1) / 3;
		sort(a, lo, hi - third); //Для первых 2/3 массива
		sort(a, lo + third, hi); //Для последних 2/3 массива
		sort(a, lo, hi - third); //Для первых 2/3 массива
	}
	//Вызываем сортировку для всего массиваvoidsort(int a[])throws Exception {
		sort(a, 0, a.length-1);
	}
}

We take a segment of the array (at first it is the whole array) and compare the elements at the ends of the segment. If the left is larger than the right, then, of course, we swap places.
Then, if there are at least three elements in the segment, then:
1) call Stooge sort for the first 2/3 of the segment;
2) call Stooge sort for the last 2/3 of the segment;
3) call Stooge sort again for the first 2/3 of the segment.

The complexity of the algorithm is calculated impressively: O (n ^{log 3 / log 1.5} ). These are not some muddy O (n) there.

Sorting Babushkina (Babushkin sort)

Babushkin himself is not directly the author of the method, however it was Alexey’s deep ideas that formed the basis of the algorithm.

Brief information about Grandma

Алексей Бабушкин, программист из Барнаула, предприниматель, инноватор. Студент 4-го курса АлтГТУ.

Участник региональной образовательной программы для одарённых школьников и молодёжи «Будущее Алтая». Победитель конкурса «Старт в науку».

Грантополучатель программы «У.М.Н.И.К.» проводимой Фондом содействию развития малых форм предприятий в научно-технической сфере.

Разработчик запатентованного антивируса «Иммунитет». Создатель оригинального гаджета «Флешка-маркер». Автор принципиально нового алгоритма архивации файлов.

По приглашению компании Microsoft принимал непосредственное участие в тестировании бета-версии Windows 8.

A fundamentally new file archiving algorithm proposed by Babushkin

Алгоритм архивации таков: любой файл представляет собой HEX-последовательность символов, переводим этот HEX в DEC, получаем неебически-большое число, дописываем перед этим число 0, — получаем число в диапазоне от 0 до 1 с огромным числом знаков после запятой, а дальше всё просто — подбираем 2 таких целочисленных числа, частное которых даст нам искомое число в диапазоне от 0 до 1 с точностью совпадений до последнего знака. Беда в подборе чисел, которое может идти и 2 часа, а может идти и 2 недели. Есть опытные образцы и работающая программа, и всё это работает.

Алексей Бабушкин

Let an array of n elements be given. The sequence of displacements of elements in their places can be represented as a series of n-ric single-digit numbers. This sequence can also be considered a multi-digit n-ric number (we call it the number of Babushkin ). Each bit of this number is an index of the position of the array into which to insert the next element. How to get such a number? If the number of Grandmarepresent in a 10-decimal form, we get a large (or not very, depends on the size of the array) number, add the number 0 before this, we get a fractional number in the range from 0 to 1, with a certain number of decimal places, and then everything is simple - we select 2 such integer numbers, the quotient of which will give us the desired number in the range from 0 to 1 with the accuracy of matches to the last character. We find 2 quotient numbers which gives the number of Babushkin - we automatically get a sequence of permutations that order the array.

Something is not clear to someone? Sorting Babushkin step by step:

1) Suppose you want to sort an array of n elements (indexing starts at 0, the index of the last element is n - 1).
2) We select two mutually simple decimal numbers, x and y (x <y).
3) Divide x by y. We get a fractional number from 0 to 1. We drop the zero, leave the fractional part. In fact, we get a certain decimal integer.
4) The DEC representation of the number obtained in step 3 is translated into the n-decimal number system.
5) We take the 0th element in the array and put it in an additional array at a position whose index is equal to the first digit in the n-decimal representation of the number obtained in step 4.
6) We take the 1st element in the array and put it in an additional array to the position whose index is equal to the second digit in the n-decimal representation of the number obtained in step 4.
7) We take the 2nd element in the array and put it in an additional array to the position whose index is equal to the third digit in the n-decimal representation of the number, obtained in step 4.
...
n + 3) We take the (n - 2) th element in the array and put it in an additional array at the position whose index is the penultimate digit in the n-decimal representation of the number obtained in step 4.
n + 4) We take in the array (n - 1) the element and place it in an additional array at a position whose index is equal to the last digit in the n-decimal representation of the number obtained in step 4.
n + 5) Transfer all elements from the additional array to the main one.
n + 6) PROFIT !!!

The advantage of sorting Babushkin over any other method is obvious - ordering is carried out at minimal cost, the elements are immediately inserted into place. Everything is based on the use of a series of n-richer numbers, which are initially the correct sequence of movements, leading to the desired result. This makes the sorting of Babushkin the undisputed leader in time complexity - the worst, average and best result is O (n). It is only necessary to pick up two numbers, which, when dividing one by another, will immediately give the desired sequence.

There are prototypes and a working program and it all works.

Grandma's Sorting in Java.

К сожалению, java-реализацию сортировки Бабушкина найти не удалось. Извините.

That's all, the express excursion into the world of alternative sortings is over, thank you for your attention. If not difficult, fill out the voting card attached to the handout materials of the lecture.

Special thanks to Patrick Morin for the kindly provided java examples .

Only registered users can participate in the survey. Please come in.

Well, the audience’s prize gets ...

17.2% Swamp sorting 284
6.6% Sort Clown Bozo 110
1.3% Swap Sort 22
6.8% Silly Sort 113
67.9% Sort by Grandma 1119

Tags: