sleep sort

睡眠並べ替え – sleep sort は、決定論的な奇妙な並べ替えアルゴリズムのもう 1 つの代表です。

次のように動作します:

<オル>

要素のリストをループします

ループごとに別のスレッドが起動される

スレッドは一定期間スリープします –要素の値とスリープ後に出力される値

ループの最後で、スレッドの最長スリープが完了するまで待機し、並べ替えられたリストを表示します

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;
}

この実装では、マイクロ秒で usleep 関数を使用し、値に 1000 を乗算しました。ミリ秒単位
で。アルゴリズムの時間計算量 – O(とても長い)

リンク

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/sleepSort

ソース

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

Tag Archives: sleep sort

スリープソート

リンク

ソース