Pchełki Bash: senne sortowanie

Tym razem wyborny żart ze stajni linuksowej, a konkretnie Bash. Będziemy sortować!

Jak być może co poniektórzy Czytelnicy się orientują, sortowanie to jeden z pierwszych tematów poruszanych podczas nauki większości języków programowania. Sortowanie bąbelkowe, sortowanie przez wstawianie, wreszcie Graal wszystkich algorytmów sortujących, czyli quicksort – i tak dalej. Kto przez to przechodził, ten dokładnie wie, o czym mówię. A kto nie przechodził – cóż, jego strata. Albo zysk…

Tak czy siak, dziś chciałbym zaprezentować algorytm sortujący całkowicie inny od wszystkiego, czego uczą w szkołach. Algorytm tak piękny, że Mona Lisa przy nim to rysunek pięciolatka. Algorytm tak niezwykły, że witki opadają.

Zaczniemy od kodu.

Kod jest w Bash-u – jeżeli ktoś nie zna Basha, tutaj jest link do szybkiego zapoznania się z podstawami.

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

Kod powyższy działa następująco: dla każdego argumentu wejściowego,

który nawiasem mówiąc powinien być liczbą dodatnią (to drobne ograniczenie, ale weźmy pod uwagę, że to pierwsza implementacja algorytmu – docelowo prawdopodobnie uda się rozszerzyć algorytm na dowolne wartości, nie tylko numeryczne)

poczekajmy tyle czasu, ile wynosi wartość tego argumentu, a następnie wypiszmy argument na ekran.

W efekcie na większe liczby trzeba poczekać dłużej niż na mniejsze, co oznacza, że pojawią się one na ekranie później. Problem rozwiązany…

Zobaczmy teraz algorytm w działaniu. Zapisujemy powyższy kod do pliku o nazwie sleepsort.sh, nadajemy mu atrybut +x i lecimy z koksem:

\>./sleepsort.sh 4 3 2 1
1
2
3
4
\>./sleepsort.sh 1.1 1.01 1.001 1.00001
1.00001
1.001
1.01
1.1
\>./sleepsort.sh 2 3 2 1
1
2
2
3
\>./sleepsort.sh 3.3 3.2 3.1 2 2.1 2.2 2.3 2.4 1.1 0
0
1.1
2
2.1
2.2
2.3
2.4
3.1
3.2
3.3

Jak widać sortowanie działa i na wyjściu za każdym razem dostajemy poprawnie posortowane liczby. Oczywiście nie ma róży bez kolców: po pierwsze, jeżeli dwie liczby na naszej liście będą różnić się bardzo nieznacznie (np. o kilka milionowych), oraz będą wystarczająco daleko od siebie na liście argumentów, efekt może być taki, że zostaną one posortowane nieprawidłowo. Inna (drobna, ale jednak) wada jest taka, że dla większych liczb znacząco wydłuża się czas oczekiwania na wynik. Na przykład jeżeli chcemy za pomocą naszego algorytmu posortować zbiór dwuelementowy {1, 31556925}, będziemy musieli poczekać na wynik prawie rok.

[yop_poll id=”49″]

 

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz