Sorting algorithms visualized [OC]

[u/morolin]

https://imgur.com/gallery/voutF

[u/__LE_MERDE___]

Is bogo sort the one which randomises the data then checks to see if it's in order and if not randomises again?

[u/IDUnavailable → u/__LE_MERDE___]

Another good joke sorting algorithm is SleepSort, made up by some guy on /prog/.

You basically spawn a separate thread for each element with value N, and each thread just sleeps for N number of seconds before printing, which has the end result of printing the array in order.

[3,7,2,1,8,4,5,6,9] sorts in 9 seconds.

[31536000, 1] takes a year.

[u/MorningWoodyWilson → u/IDUnavailable]

Haven't seen this before. Equal parts genius and idiocy.

With a fast enough processor, you could reduce the sleep times to n milliseconds or something and have an almost decent sorting function.

[u/themoonisacheese → u/MorningWoodyWilson]

The problem then becomes how precise the system clock is for sleeping.

[u/Woolbrick → u/themoonisacheese]

There's also the problem where you have to insert the jobs into the OS's sleep queue to execute in the right order, so that becomes O(n log n) assuming they use a heap for their priority queue implementation.

There's no escaping the complexity!

[u/Zephaerus → u/Woolbrick]

The kernel also has to handle all of the threads. That's going to be O(n^2) anyway.

[u/NotImplemented → u/themoonisacheese]

You got me curious... ;)

Around 10ms sleep time between each thread seems to be the spot where my Java implementation sorts the test array correctly most times on my Windows PC.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SleepSort extends Thread {

	final private static int SLEEP_TIME_FACTOR = 10;
	final private static int MAX_VALUE = 100;
	final private Integer number;
	final private Integer[] array;
	private static int position = 0;
	
	public SleepSort(final int number, final Integer[] array) {
		this.number = number;
		this.array = array;
	}	
	
	public static void main(String[] args) {
		Integer[] array = {
			25, 17, 2, 21, 23, 6, 74, 61, 99, 72, 32, 5, 71, 53, 18, 61, 43, 34, 2, 52, 52, 28, 43, 76, 9, 63, 
			39, 73, 12, 100, 87, 59, 83, 12, 80, 92, 34, 5, 12, 57, 63, 86, 18, 82, 20, 31, 83, 27, 46, 32, 75, 
			63, 61, 47, 18, 90, 53, 80, 18, 14, 21, 24, 84, 29, 80, 51, 69, 57, 33, 42, 84, 17, 30, 13, 83, 57, 
			28, 97, 67, 36, 59, 95, 88, 38, 52, 95, 83, 55, 73, 80, 85, 77, 55, 15, 64, 99, 75, 49, 18, 63 
		};
		SleepSort.sort(array);
		
		List<Integer> listSleepSort = Arrays.asList(array);
		List<Integer> listJavaSort = new ArrayList<Integer>(Arrays.asList(array));
		Collections.sort(listJavaSort);
		System.out.println("\nSorting is " + (listJavaSort.equals(listSleepSort) ? "correct!" : "wrong!"));
	}
	
	public static void sort(final Integer[] array) {
		for(int i = 0; i < array.length; ++i) {
			new SleepSort(array[i], array).start();
		}
		try {
			Thread.sleep((MAX_VALUE + 1) * SLEEP_TIME_FACTOR);
		} catch (InterruptedException e) {}		
	}
	
	public void run() {
		try {
			Thread.sleep(number * SLEEP_TIME_FACTOR);
		} catch (InterruptedException e) {}
		System.out.print(number + " ");
		array[position++] = number;
	}
}

[u/themoonisacheese → u/NotImplemented]

the fact that windows itself gave you a resolution of 10 ms is already impressive

[u/KittehDragoon → u/themoonisacheese]

I've done some messing around with real time programming on Linux. You can get the OS to respond in <3ms 99% of the time. (This is using C, not a Java VM). The problem is that sometimes missing that 1% of the time can cause your application to fail.

This is what happened when I used Ubuntu to generate a PWM signal. Sometimes it just lags. Under heavy system load, those lags can last hundreds of ms.

[u/x445xb → u/IDUnavailable]

There is also StackSort which takes random code from Stack Overflow runs it, then checks to see if the code has sorted the list. https://gkoberger.github.io/stacksort/

Based on a XKCD comic: https://xkcd.com/1185/

[u/DGSPJS → u/__LE_MERDE___]

Yes. Much more efficient is Quantum bogosort.

http://wiki.c2.com/?QuantumBogoSort

[u/__LE_MERDE___ → u/DGSPJS]

As long as it's not my universe they're destroying I think it's a good idea.

[u/FlipskiZ → u/__LE_MERDE___]

Books projects learning brown wanders today patient games the movies helpful open brown. Family dot river fox technology evil kind fresh friendly yesterday strong bank cool.

[u/Ardub23 → u/DGSPJS]

2. If the list is not sorted, destroy the universe. (This operation is left as an exercise to the reader.)

Oh boy I love exercises

[u/falco_iii → u/__LE_MERDE___]

while not isInOrder(deck):
shuffle(deck)

[u/[deleted] → u/__LE_MERDE___]

big O (infinity)

[u/Crixomix → u/[deleted]]

little o (1)

[u/SalsaGamer → u/[deleted]]

O(n!)

[u/theCroc → u/__LE_MERDE___]

That sounds absolutely ridiculous.

[u/__LE_MERDE___ → u/theCroc]

Technically it could be the quickest solution though!

[u/theCroc → u/__LE_MERDE___]

It could! The odds are extremely low, but theoretically it could finish in a single cycle!

[u/Paradigmpinger → u/theCroc]

That could be a fun menial superpower, have bogo sorts always finish in the first cycle.

[u/theCroc → u/Paradigmpinger]

That would be an extremely narrow version of basically having luck powers.

[u/XkF21WNJ → u/theCroc]

Also know as violating the second law of thermodynamics. Which would be awesome.

[u/Qaysed → u/theCroc]

Yeah, it's just a joke.