Pseudo sort or swamp sort, one of the most useless sorting algorithms.
It works like this:
1. Input is an array of numbers
2. An array of numbers is shuffled randomly (shuffle)
3. Checking if the array is sorted
4. If not sorted, then the array is shuffled again
5. All this action is repeated until the array is sorted randomly.
As you can see, the performance of this algorithm is terrible, smart people think that even O(n * n!) there is a chance to get stuck throwing dice for the glory of the god of chaos for many years, the array will not be sorted, or maybe sorted?
Implementation
For the TypeScript implementation, I needed to implement the following functions:
1. Shuffling an array of objects
2. Comparing arrays
3. Generating a random number between zero and a number (sic!)
4. Seal of progress, as the sorting seems to run indefinitely
Below is the TypeScript implementation code:
const printoutProcess = (numbers: number[], sortedNumbers: number[], numberOfRuns: number) => console.log(`Still trying to sort: ${numbers}, current shuffle ${sortedNumbers}, try number: ${numberOfRuns}`);
const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); vartemp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();
let numberOfRuns = 1;
do {
if (numberOfRuns % 1000 == 0) {
printoutProcess(originalNumbers, numbers, numberOfRuns);
}
shuffle(numbers);
numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)
console.log(`Success!`);
console.log(`Run number: ${numberOfRuns}`)
console.log(`Original numbers: ${originalNumbers}`);
console.log(`Current numbers: ${originalNumbers}`);
console.log(`Sorted numbers: ${sortedNumbers}`);
You can use VSCode and kakumei’s TypeScript Debugger plugin for debugging.
How long
Output of the algorithm:
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 2,9,7,8,0,7,4,5,2 ,5, try number: 144000
src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9
For an array of 10 numbers, Bogosort shuffled the original array 148798 times, too much right?
The algorithm can be used as a training one, to understand the capabilities of the language with which to work on the market. Personally, I was surprised to learn that vanilla JS and TS still do not have their own algorithm for shuffling arrays, generating an integer in a range, accessing object hashes for quick comparison.
Links
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName= kakumei.ts-debug
Sources
https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort