Schlafsortierung – Sleep Sort, ein weiterer Vertreter deterministischer seltsamer Sortieralgorithmen.
Es funktioniert so:
- Durchläuft eine Liste von Elementen
- Für jede Schleife wird ein separater Thread gestartet
- Der Thread schläft für eine gewisse Zeit – Elementwert und Wertausgabe nach dem Ruhezustand
- Warten Sie am Ende der Schleife, bis der längste Ruhezustand des Threads abgeschlossen ist, und zeigen Sie die sortierte Liste an
Beispielcode für den Schlafsortierungsalgorithmus in C:
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
typedef struct {
int number;
} ThreadPayload;
void *sortNumber(void *args) {
ThreadPayload *payload = (ThreadPayload*) args;
const int number = payload->number;
free(payload);
usleep(number * 1000);
printf("%d ", number);
return NULL;
}
int main(int argc, char *argv[]) {
const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
const int length = sizeof(numbers) / sizeof(int);
int maximal = 0;
pthread_t maximalThreadID;
printf("Sorting: ");
for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d ", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
pthread_create(&threadID, NULL, sortNumber, (void *) payload);
if (maximal < number) {
maximal = number;
maximalThreadID = threadID;
}
}
printf("\n");
printf("Sorted: ");
pthread_join(maximalThreadID, NULL);
printf("\n");
return 0;
}
In dieser Implementierung habe ich die Funktion usleep für Mikrosekunden verwendet, wobei der Wert mit 1000 multipliziert wurde, d. h. in Millisekunden.
Zeitliche Komplexität des Algorithmus – O(sehr lang)
Links
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/sleepSort
Quellen
https://codoholicconfessions.wordpress. com/2017/05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang=en
https://stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort
