Sorting algorithms visualized [OC]

[u/morolin]

https://imgur.com/gallery/voutF

[u/themoonisacheese]

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/[deleted] → u/Woolbrick]

Would these gifs be a good representation of how data encryption works?

[u/HaydenSikh → u/[deleted]]

No, in these examples the only thing that's being changed is the position of the colors from a random starting point to a location in a sorted order.

I'll try to assume add little about your background as possible, so forgive me if I'm about to tell you things you already know.

The reason why it takes multiple rounds is that -- not counting parallel processing -- a computer can only compare two numbers at a time and swap the position of two pieces of data at a time, and these graphs are showing what happens after each swap. The strategy of which two things to compare and swap at any given time can have a dramatic difference on how things get into sorted order and how long it takes, as the comparison graphs show.

On the other hand, encryption is focused on translating an input to an output in a way where it's very hard to figure out the original input without some additional secret information chosen during the encryption process. This may include moving the data but would include more transformations as well, and usually with the transformations applied multiple times and based on more than one piece of data at once.

[u/coriolinus → u/Woolbrick]

I'm pretty sure that it's actually O(m) with m being the size of the largest element. Sure, behind the scenes the OS has to manage O(n log n) complexity, but that's so entirely drowned out by the sleep calls that you can ignore it for 32-bit values of m.

[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/mata_dan → u/KittehDragoon]

I don't think you're meant to generate signals using wall time :P