알고리즘-천재 정렬 알고리즘-수면 정렬

이 사건 은 하나의 찌 질 한 실 이 시간 복잡 도가 O(n)인 정렬 알고리즘 을 발표 한 데 서 기원 되 었 다.이 사 이 트 는 다음 과 같다.http://dis.4chan.org/read/prog/1295544154관심 있 으 시 면 보 셔 도 됩 니 다.
사용 가치 가 그리 높 지 는 않 지만 이런 방법 을 찾 아 천재 가 되 는 것 도 지나 치지 않다.
그것 의 기본 사상 은 주로 CPU 의 스케줄 링 알고리즘 에 따라 이 루어 진 것 이다.한 그룹의 데 이 터 를 정렬 하면 마이너스 수치 가 존재 하지 않 는 다 는 것 이다.이 숫자 가 얼마나 큰 지 스 레 드 에서 잠 을 10 배 더 자 는 것 이다.수면 이 그 수치 와 똑 같은 것 이 아니 라 수치 가 너무 시간 적 이 고 오차 가 너무 크 며 수면 시간 이 수출 시간 보다 적 지 않 기 때문이다.그러면 잘못된 출력 결과 가 존재 합 니 다.
다음은 이 정렬 알고리즘 버 전 을 몇 개 쓰 겠 습 니 다.#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7
 

public class SleepSort {

    public static void main(String[] args) {

        int[] ints = {1,4,7,3,8,9,2,6,5};

        SortThread[] sortThreads = new SortThread[ints.length];

        for (int i = 0; i < sortThreads.length; i++) {

            sortThreads[i] = new SortThread(ints[i]);

        }

        for (int i = 0; i < sortThreads.length; i++) {

            sortThreads[i].start();

        }

    }

}

class SortThread extends Thread{

    int ms = 0;

    public SortThread(int ms){

        this.ms = ms;

    }

    public void run(){

        try {

            sleep(ms*10+10);

        } catch (InterruptedException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

        System.out.println(ms);

    }

}

 

<?php

$pids = array();

for ($i=1; $i<$argc; $i++)

{

        if (($pid = pcntl_fork()) == 0)

        {

                $sleep = intval($argv[$i]);

                sleep($sleep);

                echo $sleep."
";

                exit();

        }

        else if ($pid == -1)

        {

                die();

        }

        else

        {

                $pids[] = $pid;

        }

}



foreach($pids as $pid)

        pcntl_waitpid($pid, $status);

?>



php sleepsort.php 1 3 5 6 2

 
아래 이거 옮 겨 싣 는 거 예요.
1000+답장 이 붙 어 있 습 니 다.재 미 있 는 답장 몇 개 를 골 라 공유 하 겠 습 니 다.
행인 A:
Oh god, it works. But I don't like to wait 218382 seconds to sort '(0 218382)
오,춘 형,쓸 수 있 는데 218382 초 로 줄 을 서고 싶 지 않 아 요(0 218382)
행인 B:
If the difference between any two of the numbers is too small, race conditions will fuck you up the ass.
만약 두 수 사이 의 차이 가 너무 작다 면,경쟁 조건 은 너의 국 화 를 폭발 시 킬 것 이다.
행인 C:
What about  ./sleepsort -1 -2 -3  ? If you slept  exp(n)  instead of  n  it could easily include negative integers too!
줄.-1.-2.-3.어 떡 해?n 이 아 닌 exp(n)에서 자 면 음 수 를 포함 할 수 있 습 니 다.
행인 D:
Someone email this to Knuth
Knuth 에 게 메 일 을 보 내 셔 도 됩 니 다.
행인 E:
I think thats brilliant :)
Would be fun to design a hardware sorter, based on this..
이 방법 은 매우 높 아서 이것 에 따라 하드웨어 정렬 기 를 설계 할 수 있다.
행인 F:
This has a best case O(n) and an infinity high worst case. (because its 0(n * Constant) and the constant could be much greater than n)
그것 은 가장 좋 은 O(n)의 시간 복잡 도와 무한대 의 최 악의 복잡 도 를 가지 고 있다.왜냐하면 이 상수 가 n 보다 많 을 수 있 기 때문이다.
행인 G:
I heartily disagree with all the attempts to downplay the brilliance of the sleep sort algorithm. Many of you have missed the important point that while traditional sorting algorithms can only utilize one core, sleep sort has the capacity to use the full power of a massively parallel execution environment. Given that you need nearly no computing in each of the threads, you can implement them using low-power CPUs, so this is in fact a GREEN COMPUTING algorithm. Oh, and did I mention that the algorithm can also run inside a cloud...? Sure, you're a genius!
저 는 sleepsort 라 는 천재 알고리즘 을 과소평가 하 는 행동 에 진심으로 동의 하지 않 습 니 다.많은 사람들 이 중요 한 것 은 전통 적 인 정렬 은 하나의 핵심 만 이용 할 수 있 고 sleepsort 는 이 능력 을 가지 고 대량의 병행 계산 을 할 수 있 는 환경 을 충분히 이용 할 수 있 습 니 다.
모든 스 레 드 에서 계산 이 거의 필요 없 는 부분 을 제시 합 니 다.저 성능 CPU 로 해결 할 수 있 기 때문에 사실상 이것 은'녹색 계산'알고리즘 입 니 다.
그리고 제 가 말씀 드 린 이 방법 은 구름 위 에서 운행 할 수 있 습 니까?
아무튼 너 는 천재 야!
행인 H:
pretty fucking cool !
정말 너무 쿨 해!