Sleep Sort – El rey de la pereza / Ordenar mientras se duerme

En este algoritmo, creamos diferentes subprocesos para cada uno de los elementos en la array de entrada y luego cada subproceso duerme durante un período de tiempo que es proporcional al valor del elemento de la array correspondiente.

Por lo tanto, el subproceso que tiene la menor cantidad de tiempo de inactividad se despierta primero y se imprime el número y luego el segundo elemento menos y así sucesivamente. El elemento más grande se despierta después de mucho tiempo y luego el último elemento se imprime. Por lo tanto, la salida es ordenada.

Todo este proceso de subprocesos múltiples ocurre en segundo plano y en el núcleo del sistema operativo. No llegamos a saber nada sobre lo que sucede en segundo plano, por lo tanto, este es un algoritmo de clasificación «misterioso».

Ejemplo: supongamos (por conveniencia) que tenemos una computadora que es tan lenta que tarda 3 segundos en procesar cada elemento:

INPUT: 8 2 9 

3s: sleep 8
6s: sleep 2
8s: "2" (2 wakes up so print it)
9s: sleep 9
11s: "8" (8 wakes up so print it)
18s: "9" (9 wakes up so print it)

OUTPUT: 2 8 9

Implementación
Para implementar la ordenación de suspensión, necesitamos funciones de subprocesos múltiples, como _beginthread() y WaitForMultipleObjects() . Por lo tanto, debemos incluir windows.h para usar estas funciones. Esto no se compilará en el IDE en línea . Debemos ejecutarlo en su PC (Observe que este código es para WINDOWS y no para LINUX).

Para realizar una clasificación de suspensión, necesitamos crear subprocesos para cada uno de los valores en la array de entrada. Hacemos esto usando la función _beginthread() .

En cada uno de los hilos asignamos dos instrucciones:

1) Dormir : Dormir este subproceso hasta arr[i] milisegundos (donde arr[i] es el elemento de array al que está asociado este subproceso). Hacemos esto usando la función Sleep(). La función Sleep(n) suspende la actividad asociada con este hilo hasta ‘n’ milisegundos. Por lo tanto, si escribimos Sleep (1000), significa que el subproceso dormirá durante 1 segundo (1000 milisegundos = 1 segundo)

2) Imprimir: cuando el subproceso se ‘despierta’ después de la suspensión, imprima el elemento de array – arr[i] al que está asociado este subproceso.

Después de crear los hilos, procesamos estos hilos. Hacemos esto usando WaitForMultipleObjects() .

// C implementation of Sleep Sort
#include <stdio.h>
#include <windows.h>
#include <process.h>
  
// This is the instruction set of a thread
// So in these threads, we "sleep" for a particular
// amount of time and then when it wakes up
// the number is printed out
void routine(void *a)
{
    int n = *(int *) a; // typecasting from void to int
  
    // Sleeping time is proportional to the number
    // More precisely this thread sleep for 'n' milliseconds
    Sleep(n);
  
    // After the sleep, print the number
    printf("%d ", n);
}
  
/* A function that performs sleep sort
_beginthread() is a C run-time library call that creates a new
'thread' for all the integers in the array and returns that
thread.
  
Each of the 'thread' sleeps for a time proportional to that
integer and print it after waking.
  
We pass three parameters to _beginthread :-
1) start_address --> start address of the routine/function
                     which creates a new thread
2) stack_size --> Stack Size of the new thread (which is 0)
3) arglist --> Address of the argument to be passed
  
The return value of _beginthread() function is a handle to the
thread which is created. So we must accept is using the datatype-
'HANDLE' which is included in windows.h header
'HANDLE' datatype is used to represent an event/thread/process etc
So 'HANDLE' datatype is used to define a thread
We store the threads in an array - threads[] which is declared
using 'HANDLE' datatype.
  
WaitForMultipleObjects() is a function that processes the threads
and has four arguments-
1) no_of_threads --> Number of threads to be processed
2) array_of_threads --> This is the array of threads which should be
                        processed. This array must be of the type
                        'HANDLE'
3) TRUE or FALSE --> We pass TRUE if we want all the threads in the
                     array to be processed
4) time_limit --> The threads will be processed until this time limit
                  is crossed. So if we pass a 0 then no threads will
                  be processed, otherwise if we pass an INFINITE, then
                  the program will stop only when all the threads
                  are processed. We can put a cap on the execution
                  time of the program by passing the desired time
                  limit */
void sleepSort(int arr[], int n)
{
    // An array of threads, one for each of the elements
    // in the input array
    HANDLE threads[n];
  
    // Create the threads for each of the input array elements
    for (int i = 0; i < n; i++)
        threads[i] = (HANDLE)_beginthread(&routine, 0,  &arr[i]);
  
    // Process these threads
    WaitForMultipleObjects(n, threads, TRUE, INFINITE);
    return;
}
  
// Driver program to test above functions
int main()
{
    // Doesn't work for negative numbers
    int arr[] = {34, 23, 122, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    sleepSort (arr, n);
  
    return(0);
}

Limitaciones
1) Este algoritmo no funcionará para números negativos ya que un subproceso no puede dormir por una cantidad de tiempo negativa.

2) Dado que este algoritmo depende de los elementos de entrada, un gran número en la array de entrada hace que este algoritmo se ralentice drásticamente (ya que el subproceso asociado con ese número tiene que dormir durante mucho tiempo). Entonces, incluso si el elemento de la array de entrada contiene solo 2 elementos, como {1, 100000000}, entonces también tenemos que esperar una duración mucho más larga para ordenar.

3) Este algoritmo no produce una salida ordenada correcta cada vez. Esto generalmente sucede cuando hay un número muy pequeño a la izquierda de un número muy grande en la array de entrada.
Por ejemplo: {34, 23, 1, 12253, 9}.
La salida después de la clasificación del sueño es {9, 1, 23, 34, 1223}

También se produce una salida incorrecta cuando la array de entrada se ordena inversamente inicialmente, como {10, 9, 8, 7, 6, 5}.

El motivo de una salida tan inesperada es que transcurre cierto tiempo entre la exploración de cada elemento y otras operaciones del sistema operativo (como la inserción de cada subproceso en una cola de prioridad para la programación). No podemos simplemente ignorar el tiempo que tardan todas estas cosas.

Describimos esto usando el siguiente ejemplo:

Let's assume (for convenience) we have a computer that's
so slow it takes 3 seconds to work through each element: 
INPUT: 10 9 8 7 6 5

3s: sleep 10
6s: sleep 9
9s: sleep 8
12s: sleep 7
13s: "10" (10 wakes up so print it)
15s: sleep 6
15s: "9" (9 wakes up so print it)
17s: "8" (8 wakes up so print it)
18s: sleep 5
19s: "7" (7 wakes up so print it)
21s: "6" (6 wakes up so print it)
23s: "5" (5 wakes up so print it)

OUTPUT: 10 9 8 7 6 5 

La salida anterior es solo un ejemplo.
Obviamente, las computadoras de hoy en día no son tan lentas (toman 3 segundos para escanear cada elemento).
En realidad, ejecutar sleep sort en una computadora moderna en la array anterior da como resultado: {9, 5, 7, 10, 8, 6}

Cómo arreglar esto ?
1) Podemos arreglar esto ordenando repetidamente la nueva salida hasta que la salida se ordene. Cada vez ordenará los elementos con mayor precisión.

2) La salida incorrecta, como se mencionó anteriormente, ocurre debido al tiempo que tardan otros sistemas operativos en trabajar y escanear a través de cada elemento.

En nuestro programa hemos utilizado la función Sleep(arr[i]) , lo que significa que cada subproceso asociado con los elementos de la array duerme durante ‘arr[i]’ milisegundos. Dado que los milisegundos son una cantidad muy pequeña y otras tareas del sistema operativo pueden llevar más tiempo que los milisegundos ‘arr[i]’, lo que en última instancia puede causar un error en la clasificación del sueño. Aumentar el tiempo de sueño incluso 10 veces puede dar un resultado ordenado ya que las tareas del sistema operativo terminarán todas sus tareas entre esta cantidad de sueño, por lo tanto, no producirán ningún error.

Si hubiéramos usado Sleep(10*arr[i]) en lugar de Sleep(arr[i]), seguramente obtendremos una salida más precisa que la última. Por ejemplo, la array de entrada: {10, 9, 8, 7, 6, 5} dará la salida ordenada correcta: {5, 6, 7, 8, 9, 10} si usamos Sleep(10*arr[i] ) en lugar de solo Sleep(arr[i]) .

Sin embargo, todavía es posible que Sleep(10*arr[i]) dé resultados incorrectos en algunos casos de prueba. Para hacerlo más preciso, aumente más el tiempo de sueño, diga algo como: Dormir (20 * arr [i]).

Por lo tanto, la conclusión es que cuanto mayor sea el tiempo de sueño, más precisos serán los resultados. (Suena interesante, ¿eh?). Pero nuevamente, eso aumentaría el tiempo de ejecución de este algoritmo.

Ejercicio para los lectores:
1) El algoritmo anterior intenta clasificarlo en orden ascendente. ¿Puede ordenar una array de entrada en orden descendente utilizando la ordenación de suspensión? Piénsalo.

2) ¿Es un algoritmo de clasificación basado en comparación? ¿Cuántas comparaciones hace este algoritmo?
[Respuesta: No, hace cero comparaciones]

3) ¿Podemos ordenar el modo de dormir sin usar el encabezado windows.h y sin usar la función Sleep()?
[Una idea puede ser crear una cola de prioridad donde los elementos se organicen de acuerdo con el tiempo que queda antes de despertarse e imprimirse. El elemento al frente de la cola de prioridad será el primero en despertarse. Sin embargo, la implementación no parece fácil. Piénsalo.]

Complejidad del tiempo
Aunque hay muchas opiniones contradictorias sobre la complejidad del tiempo del tipo de sueño, podemos aproximarnos a la complejidad del tiempo usando el siguiente razonamiento:

Dado que la función Sleep() y la creación de múltiples subprocesos se realizan internamente por el sistema operativo utilizando una cola de prioridad (utilizada con fines de programación). Por lo tanto, la inserción de todos los elementos de la array en la cola de prioridad lleva un tiempo O (Nlog N). Además, la salida se obtiene solo cuando se procesan todos los subprocesos, es decir, cuando todos los elementos se ‘despiertan’. Ya que toma tiempo O(arr[i]) para activar el subproceso del i-ésimo elemento de la array. Por lo tanto, se necesitará un máximo de O(max(input)) para que se despierte el elemento más grande de la array. Por lo tanto, la complejidad de tiempo general se puede asumir como O (NlogN + max (entrada)),
donde, N = número de elementos en la array de entrada y entrada = elementos de la array de entrada

Espacio auxiliar
Todo lo hace la cola de prioridad interna del sistema operativo. Por lo tanto, el espacio auxiliar puede ignorarse.

Conclusión
Sleep Sort está más relacionado con el sistema operativo que con cualquier otro algoritmo de clasificación. Este algoritmo de clasificación es una demostración perfecta de subprocesos múltiples y programación realizada por el sistema operativo.

La frase «Clasificar mientras se duerme» en sí misma suena muy singular. En general, es un algoritmo divertido, perezoso y extraño. Pero como bien dijo alguien: «Si funciona, entonces no es perezoso».

Echa un vistazo al curso de autoaprendizaje de DSA

Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.