果報は寝て待て：おふざけsortアルゴリズム「sleep sort」を実装した

2023年2月4日 08:17

お疲れ様です。Y研究員です。古典的C言語の教科書を『写経』していたらソートのアルゴリズムが面白いので、あれこれ書いてます。前回はランダムに並べ替える、bogosortを書きました。今回はsleepを使ったソートです。

与えられた数字の長さだけsleepするスレッドを立てると、小さい順番に返ってくるのでソートができる、という塩梅です。どうやら２ｃｈの英語版４ｃｈで書れたものが最初のようです。Wikipediaにも日本語はページがありました。真面目に説明されていて、「実用では絶対に使ってはならない」と念押しまであります。他の処理に邪魔されて、順番に返ってくる保証は無いからです。４ｃｈにはShellスクリプトで書かれたみたいですが、せっかくなのでCで書きました。

#include "sort_lib.h"
#include <pthread.h>
#include <unistd.h>

void *sleeping(void *);

int main()
{
    printf("sleep sort\n");
    int length = 10;
    int array[length];
    get_array(array, length);
    print_array(array, length);
   
    pthread_t thread_id[length];
    for (int i = 0; i < length; i++) 
    {
        pthread_create( &thread_id[i], NULL, sleeping, (void*) &array[i]);
    }

    for (int i = 0; i < length; i++) 
    {
        pthread_join( thread_id[i], NULL);
    }
 
    return 0;
}

void *sleeping(void *ptr)
{
    int *how_long;
    how_long = (int*) ptr;
    usleep(*how_long * 1000); 
    printf("%d \n", *how_long);
}

usleepやpthreadはLinuxでしか動かないのでOS依存のコードになりました。　usleepはそのままだとマイクロ秒で結果がおかしくなるので１０００倍してミリ秒に直しました。大きい数字が含まれると、例えば１６進数の正数だと６万５千くらいが最大値なので最悪で６５秒かかります。遅いですね。。。

ロバストなsleep sortを突き詰めるのも面白そうですが、経典の写経にそろそろ戻りたいと思います。次は関数みたいです。

写真はキュウリです。参考にした資料がカーネギーメロンだったので、メロンをGooglePhotoで検索したら出てきました。ウリ科だから似たようなものなので良しとしましょう。

ではまた！

般若心経の写経とプログラムの『写経』に関する記事はこちらからどうぞ。

参照：
４ｃｈのスクショ

https://www.cs.princeton.edu/courses/archive/fall13/cos226/lectures/52Tries.pdf

日本語のWikipediaページ（バケツソートの一部にねじ込んである。英語版には書いてない）

pthreadはここを参考にしました

無料のプログラミングクラブCoderDojoを運営するにあたり寄付を受け付けています。お金は会場費・Wifiの費用・教科書に使用します。