スリープソート

時間を使ったソート。
今年ちょっと話題になって初めてブログで見たときは、お〜なるほど〜って感じだった。
いつ使うの？と聞かれると、まだわからないとしか言えないけど、何かに使えるはず。
WindowsだったらSleepはミリ秒でスレッド実行できるようなので実用性++か？

[sleep_sort.c]

#include <assert.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <wait.h>

#define N 10 /* データ件数 */

int sort[N];
int count;
void SleepSort(void);
void output(void);

void SleepSort(void) {
    int i;
    for (i = 0; i < N; i++) {
        switch (fork()) {
            case -1:
                assert(0);
                break;
            case 0:
                /* child process */
                sleep(sort[i]);
                printf("%d\n", sort[i]);
                exit(0);
                break;
            default:
                break;
        }   
    }
    for (i = 0; i < N; i++) {
        while (wait(NULL) <= 0)
            assert(errno == EINTR);
    }
}
                                                                                          

int main(void) {
    int i;
    
    srand((unsigned int) time(NULL));
    for (i = 0; i < N; i++) {
        sort[i]  = rand() % 10;
    }

    printf("Stundy...\n");
    output();

    printf("Start...\n");
    SleepSort();
    printf("End...\n");

    return EXIT_SUCCESS;
}


void output(void){
    int i = 0;
    printf("sort => [");
    while(1){
        printf("%d", sort[i]); 
        if (i != N - 1) {
            printf(","); 
        }
        else{
            printf("]\n"); 
            break;
        }
        ++i;
    }
}

cでも、もっとカンタンな実装があるし
シェルでも簡単に書ける。
こっちの方が実用性があるかも。

[sleep_sort.bash]

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

実行サンプル

/bin/bash sleep_sort.bash 7 4 1 3 2 6 8 0 9 5
0
1
2
3
4
5
6
7
8
9