Sort Colors

Sortowanie za pomocą biblioteki działałoby w czasie O(n log n), ale reguły zadania tego zabraniają, ponieważ osoba prowadząca rozmowę chce zobaczyć, co zrobisz, wiedząc, że występują tylko trzy wartości. Podstawowym rozwiązaniem jest więc sortowanie napisane samodzielnie, a najprościej poprawnie zaimplementować sortowanie bąbelkowe: przejdź po tablicy i za każdym razem, gdy dwa sąsiednie elementy są w złej kolejności, zamień je miejscami.

Jedno przejście przesuwa największą napotkaną wartość aż na koniec, niczym unoszący się bąbelek. Po pierwszym przejściu ostatnia pozycja jest już ustalona, po drugim ustalone są już dwie ostatnie pozycje, więc n-1 przejść wystarczy, by cała tablica była uporządkowana. W [2, 1, 0] pierwsze przejście przesuwa 2 na koniec, dając [1, 0, 2], a drugie zamienia miejscami 1 i 0.

To sortowanie jest powolne, ponieważ każde przejście porównuje wszystkie pary, które nie są jeszcze na właściwych pozycjach: łącznie około n²/2 porównań. Dla n = 1.5 × 10^4 oznacza to ponad 10^8 porównań, a także zamianę miejscami każdej pary, która początkowo jest w złej kolejności. Żadna z tych operacji nie wykorzystuje faktu, że występują tylko trzy wartości.

Sortowanie bąbelkowe poświęca cały czas na porównywanie sąsiadujących elementów, ale już wiesz, jakie wartości występują. Jeśli tablica zawiera dwie wartości 0, trzy wartości 1 i dwie wartości 2, wynik jest ustalony, zanim cokolwiek przesuniesz: dwie wartości 0, trzy wartości 1, dwie wartości 2. Liczą się tylko liczności.

Przejdź więc raz przez tablicę i policz każdą wartość. Następnie nadpisz ją od początku: count[0] zer, potem count[1] jedynek, a następnie count[2] dwójek. To sortowanie przez zliczanie, które jest tutaj bezpieczne, ponieważ równe wartości są zamienne. 1 to 1, więc pierwotna kolejność nie musi zostać zachowana.

To dwa przebiegi i trzy liczniki, czas O(n) i pamięć O(1). Spełnia ograniczenia i jest naturalnym rozwiązaniem, gdy kolorów jest wiele. Dalsze pytanie, z którego słynie to zadanie, brzmi: czy da się to zrobić, odczytując tablicę tylko raz?

Przesuwaj trzy obszary podczas odczytywania: 0 z przodu, 1 za nimi, 2 z tyłu, a między 1 i 2 pozostaw nieodczytaną część. Trzy indeksy wyznaczają granice. Wszystko przed low to 0, wszystko od low do mid (bez mid) to 1, wszystko za high to 2, a elementy od nums[mid] do nums[high] są jeszcze nieodczytane.

Odczytaj nums[mid]. 1 jest już w swoim obszarze, więc przesuń mid dalej. 0 należy umieścić z przodu: zamień go z nums[low] i przesuń dalej zarówno low, jak i mid. Wartość, która wraca z low, to 1 (albo to samo 0, jeśli nie napotkano jeszcze żadnej 1), więc jest już na swoim miejscu. 2 należy umieścić z tyłu: zamień go z nums[high] i przesuń high wstecz, ale pozostaw mid na miejscu, ponieważ wartość, która przybyła z high, nie została jeszcze odczytana.

Każdy krok przesuwa mid do przodu albo high wstecz, więc nieodczytana część za każdym razem zmniejsza się o jeden element, a pętla kończy się po n krokach. Prześledź [2, 0, 2]: pierwsza 2 zostaje zamieniona z ostatnią 2, a high zmniejsza się do 1; indeks 0 nadal zawiera 2, która zostaje zamieniona z 0, a high zmniejsza się do 0; indeks 0 zawiera teraz 0, który pozostaje na miejscu, i otrzymujesz [0, 2, 2].