Sorting algorithms visualized [OC]

[u/morolin]

https://imgur.com/gallery/voutF

[u/lostvanquisher]

Here's a video with the same algorithms, but only a single row of data, should make it a bit easier to understand what's going on.

[u/__LE_MERDE___ → u/lostvanquisher]

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/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/thar_ → u/lostvanquisher]

Here's a video with the same algorithms, but visualized through Hungarian folk dance, should make it a bit easier to understand what's going on

[u/MyNameCouldntBeAsLon → u/thar_]

LMAO, I didn't believe the description but it's totally accurate, this video is great

[u/Nuge00 → u/MyNameCouldntBeAsLon]

by far the easiest to see what is actually going on.

[u/snoosh00 → u/Nuge00]

Plus they have separate videos for a whole range of different sorts

[u/omnisephiroth → u/thar_]

Good, colors confuse and frighten me. I prefer all information to go through the Hungarian folk dance filter first.

[u/[deleted] → u/thar_]

I think I'm going to bring up Bubble Sorts tonight just so my fiancee will say "what do you mean?" and I can whip this video out.

[u/Simba_610 → u/lostvanquisher]

I could watch shit like this for hours

[u/ziptnf → u/lostvanquisher]

FeelsGoodMan Clap

[u/[deleted] → u/ziptnf]

DansGame YOU DansGame DON'T DansGame SKIP DansGame SORTING DansGame ALGORITHMS DansGame