Impractical triage - meaningless and merciless
And what are we all about smart but about efficient algorithms? And let this dreary autumn Friday dispel something counterproductive!?
I present to your attention the TOP-5 of the most non-traditional sorting of all time and peoples.
')
It is useful for young programmers to show this for didactic purposes. All the others at least amused.
Bog Sorting (BogoSort)
With this sorting you need to be extremely careful. Inadvertently land in the quagmire, you risk perishing forever.
The principle is simple as mold. Shake the array until it is suddenly sorted. The process can happily complete immediately, and can last until the thermal death of the universe. This is as lucky.
Average time complexity: O (nxn!). There is also a better one: Ω (n). Interestingly, the worst time complexity of this algorithm is unknown to science.
Neatly. Code in which you can get bogged down.
import java.util.Random; public class BogoSortAlgorithm extends SortAlgorithm { // , public void sort(int data[]) throws Exception { if (data.length > 0) runBogoSort(data); } // private void runBogoSort(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)); // } //, private boolean isSorted(int data[]) { for (int i = 1; i < data.length; i++) if (data[i] < data[i - 1]) return false; return true; } } Sort clown Bozo (BozoSort)
Where BogoSort, there and BozoSort. The method of sorting the children's clown Bozo is easy to explain even to a three-year-old child. We choose two elements at random, change places, check whether this has led to success. If not, then repeat the same actions - and so on until the bitter end.
It may seem that BozoSort is the same as BogoSort, but this is only at first glance. Clown Bozo sorts with the average time complexity O (nxn!) And this is also the upper limit in time.
UPD. As I was rightly told by burdakovd and SkidanovAlex in the comments and personal messages, the sorting of the clown Bozo, like BogoSort, does not have an upper limit for the worst time complexity. Indeed, where will it come from, if in the worst case, in the unsorted array, the random two elements will forever interchange the same two elements !?
Also note that nevertheless, on average, BozoSort will still sort faster than BogoSort. Just because after each exchange the array is checked for orderliness. In BogoSort, there are frequent cases when an array is in an ordered state, however, if at this point you do not make a check, but mix further, then the desired state of sorting is temporarily lost.
Clown Bozo also sparklingly programs.
import java.util.Random; class BozoSortAlgorithm extends SortAlgorithm { void sort(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; } } } } // private int Randomize( int range ) { double rawResult; rawResult = Math.random(); return (int) (rawResult * range); } } Sort permutations (PermSort)
Let's look at the task of sorting through the prism of combinatorics. Any array is a usual finite set of n elements for which there is n! permutations. Some of them are an array in an ordered state. Having compiled an algorithm for iterating over all permutations, we inevitably find the one.
The worst complexity in time as a clown Bozo - O (n x n!). But with better things are better - O (n).
Elegant search of all permutations of the array.
class PermSortAlgorithm extends SortAlgorithm { // ? boolean issorted(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]) { return false; } } return true; } // PermSort boolean sort(int a[], int i) throws Exception { int j; // if (issorted(a, i)) { return true; } // . // . 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)) { return true; } // T = a[i]; a[i] = a[j]; a[j] = T; } return false; } // PermSort. void sort(int a[]) throws Exception { sort(a, 0); } } Silly sorting (Stooge sort)
Sorting is named after the comic troupe “Three Stooges” (“Three imbeciles”) that amused the American public in the last century: from the beginning of the 30s to the end of the 60s. By the way, there were six “imbeciles" in total; over the 4 decades of creative activity, the composition of the trio sometimes changed.
The famous trio specialized in farce and eccentric. The sorting also behaves: like a caricature character, she is madly torn along an array; as befits a buffoon - after the ridiculous adventures with the main character everything is fine. Array sorted, happy end.
The algorithm is ingeniously recursive.
class StoogeSortAlgorithm extends SortAlgorithm { void sort(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 } // void sort(int a[]) throws Exception { sort(a, 0, a.length-1); } } 
We take a segment of the array (at first this is the entire array) and compare the elements at the ends of the segment. If the left is more than the right, then, of course, change 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 conclusively accurately: O (n log 3 / log 1.5 ). These are not some muddy O (n).
Sorting Grandmother (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
Alexey Babushkin, a programmer from Barnaul, an entrepreneur, an innovator. 4th year student of Altai State Technical University.
Participant of the regional educational program for gifted schoolchildren and youth “The Future of Altai”. Winner of the "Start to Science" competition.
The grantee of the “U.M.N.I.K.” program conducted by the Foundation to promote the development of small enterprises in the scientific and technical field.
The developer of the patented antivirus "Immunity". The creator of the original gadget "Flash marker". Author of a fundamentally new file archiving algorithm.
At the invitation of Microsoft, he was directly involved in testing the beta version of Windows 8.
Participant of the regional educational program for gifted schoolchildren and youth “The Future of Altai”. Winner of the "Start to Science" competition.
The grantee of the “U.M.N.I.K.” program conducted by the Foundation to promote the development of small enterprises in the scientific and technical field.
The developer of the patented antivirus "Immunity". The creator of the original gadget "Flash marker". Author of a fundamentally new file archiving algorithm.
At the invitation of Microsoft, he was directly involved in testing the beta version of Windows 8.
Fundamentally new file archiving algorithm proposed by Babushkin
The archiving algorithm is as follows: any file is a HEX-sequence of characters, we translate this HEX to DEC, we get a non-logical number, add the number 0 before this, we get a number in the range from 0 to 1 with a huge number of decimal places, and then simply - 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 digit. The trouble is in the selection of numbers, which can go 2 hours, and can go 2 weeks. There are prototypes and a working program, and it all works.
Alexey Babushkin
Alexey Babushkin
Let an array of n elements be given. The sequence of displacements of elements into their places can be represented in the form of a series of n-ary single-digit numbers. This sequence can also be considered a multi-digit n-ary number (let's call it Babushkin number ). Each digit of this number is an index of the position of the array into which the next element should be inserted. How to get such a number? If the Babushkin number is presented in a 10-hour form, we get a large (or not very much, depends on the size of the array) number, we add a 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 digit. Let us find 2 partial numbers which give Babushkin's number - we automatically get the sequence of permutations ordering the array.
Someone something is not clear? Sorting Grandma's steps:
1) Suppose you need to sort an array of n elements (indexing starts from 0, the index of the last element is n - 1).
2) Specially select two mutually simple decimal numbers, x and y (x <y).
3) Divide x by y. We obtain a fractional number from 0 to 1. Zero is rejected, leaving the fractional part. In fact, we get a certain decimal number.
4) DEC-representation of the number obtained in step 3, we translate into n-ary number system.
5) Take the 0th element in the array and place it in the additional array at the position whose index is equal to the first digit in the n-th representation of the number obtained in step 4.
6) We take the 1st element in the array and place it in the additional array at the position whose index is equal to the second digit in the n-number representation of the number obtained in step 4.
7) We take the 2nd element in the array and place it in the additional array at the position whose index is equal to the third digit in the n-number representation of the number obtained in step 4.
...
n + 3) Take an array in the (n - 2) -th element and put it in an additional array in a position whose index is equal to the penultimate digit in the n-number representation of the number obtained in step 4.
n + 4) We take in the array (n - 1) -th element and put it in an additional array on a position whose index is equal to the last digit in the n-th 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 Grandma's sorting over any other method is obvious - the ordering is carried out with minimal cost, the elements are immediately inserted into their places. Everything is based on the use of a series of n-riche numbers, which are the inherently correct sequence of displacements, leading to the desired result. This makes Grandma's sorting the undisputed leader in time complexity — the worst, average, and best result — O (n). It is only necessary to pick up two numbers, which, when dividing one by the other, immediately give the desired sequence.
There are prototypes and a working program and it all works.
Sort Grandma's Java.
Unfortunately, the java-implementation of Grandma's sorting could not be found. Excuse me.
That's all, an express excursion into the world of alternative sorts is over, thank you for your attention. If it is not difficult, fill in the voting card attached to the lecture handouts.
Special thanks to Patrick Morin for kindly provided java-examples .
Source: https://habr.com/ru/post/198114/
All Articles