Question

Krasnoludek jest zamknięty w pokoju. Chciałby jak najszybciej wyjść, ponieważ za drzwiami trwa jego przyjęcie urodzinowe, więc im dłużej siedzi w pokoju, tym mniej tortu zostanie dla niego. Aby wyjść z pokoju musi wpisać kod – dziewięć liczb w rosnącej kolejności. Ma przed sobą rozsypane klocki, na których są napisane liczby z kodu, musi je poukładać rosnąco. Pomóż krasnoludkowi zrobić to w najszybszym czasie. Podaj trzy rozwiązania różniące się szybkością wykonania układania tych dziewięciu klocków.

Answer 1

1. Krasnoludek układa klocki w rządku, bierze dwa pierwsze klocki i jeżeli pierwszy jest mniejszy od drugiego to odkłada je jak były, inaczej zamienia je miejscami i zaczyna od początku, aż dojdzie do ostatniego klocka i przy następnym sprawdzaniu od początku do końca nie zajdzie żadna zamiana klocków:
[1][7][3][9][2][4][6][5][8]
[1]<[7] => [1][7]
[7]>[3] => [1][3][7] -> nawrót do początku
[1]<[3] => [1][3][7]
[3]<[7] => [1][3][7]
[7]<[9] => [1][3][7][9]
[9]>[2] => [1][3][7][2][9] -> nawrót do początku
[1]<[3] => ...

2. Układa klocki w rządku, przypisuje każdemu klockowi jego wartość binarną i dzieli je według pierwszego najstarszego bitu:
[1][7][3][9][2][4][6][5][8]
[0001][0111][0011][1001][0010][0100][0110][0101][1000]
0-[0001], [0111], [0011], [0010], [0100], [0110], [0101]
1-[1001], [1000]
Następnie w każdym zbiorze dzieli je na podzbiory według drugiego najstarszego  bitu:
0.0-[0001], [0011], [0010]
0.1-[0111], [0100], [0110], [0101]
1.0-[1001], [1000]
1.1-
Według trzeciego najstarszego bitu:
0.0.0-[0001]  => posortowane
0.0.1-[0011], [0010]
0.1.0-[0100], [0101]
0.1.1-[0111], [0110]
1.0.0-[1001], [1000]
1.0.1-
I według najmłodszego bitu:
0.0.1.0-[0010]
0.0.1.1-[0011]
0.1.0.0-[0100]
0.1.0.1-[0101]
0.1.1.0-[0110]
0.1.1.1-[0111]
1.0.0.0-[1000]
1.0.0.1-[1001]
I ma teraz posortowane
1, 2, 3, 4, 5, 6, 7, 8, 9

3. Układa klocki w rządku, bierze pierwszy i odkłada go w innym miejscu, bierze kolejny i kładzie/wkłada go do rządku:
[1][7][3][9][2][4][6][5][8]
[1]
[1][7]
[1][3][7]
[1][3][7][9]
[1][2][3][7][9]
[1][2][3][4][7][9]
[1][2][3][4][6][7][9]
[1][2][3][4][5][6][7][9]
[1][2][3][4][5][6][7][8][9]