Sortowanie skarpet

Drogi czytelnik z pewnością napotkał następujący problem:
po praniu skarpetki są przemieszane i by znaleźć parę należy włożyć to trochę czasu każdego ranka.

Poniżej szereg możliwych rozwiązań problemu, wraz z podaną złożonością obliczeniową.

Naiwne

Każdorazowo bierzemy skarpetkę, po czym szukamy dla niej pary, sprawdzając każdą kolejną czy jest jej równa. Mając do dyspozycji zbiór $n$-elementowy, średnio na jedną skarpetkę przypada $n$ porównań. Daje to sumarycznie $\theta (n^2)$ operacji, by wykończyć całą partię skarpetek.

Lepiej

Powiedzmy, że naszym parametrem porównawczym będzie jasność skarpetki. Bierzemy pierwszą z brzegu1 skarpetę i rzucamy2 ją na tapczan. Następnie wszystkie ciemniejsze od niej rzucamy na kupkę po jej lewicy, a jaśniejsze - prawicy. Dla kupek postępujemy rekurencyjnie. W tak posortowanym zbiorze skarpet sąsiednie (parzysta/nieparzysta) tworzą parę. Tym samym udało się nam sparować skarpety w czasie $\theta(n \log n)$.

Uwaga 1: będzie działało to tylko dla zbioru skarpet, w którym każde dwa elementy można porównać ($\leq$/$\geq$). Jednak zawsze można wpierw doczepić metkę z liczbą, zatem prezentowane rozumowanie jest ogólne.

Uwaga 2: w praktyce łatwo o błędy numeryczne (a raczej: optyczne) przy porównywaniu jasności skarpetek.

Jeszcze lepiej

Kupujemy skarpety tylko kilku $k$ rodzajów (np. czarne, białe i łaciate). Ustawiamy $k$ koszy (czy też kubełków) i lecimy z koksem. T.j. każdą kolejną skarpetkę wrzucamy do odpowiadającej jej kosza. Zadania dokonamy w czasie liniowym od $n$, a mianowicie $\theta(k n)$.

Super

Kupujemy skarpety tylko jednego typu. Naiwnie myśląc sprowadzilibyśmy się do powyższego przypadku dla $m=1$. Ale nie: już po wyciągnięciu z pralki są one sparowane. Czyli daje to czas $\theta(1)$. Należy jednak uczciwie zaznaczyć, że i tak w końcu te skarpety będziemy chcieli założyć (co robimy w czasie liniowym), czyli tak naprawdę te rozwiązanie pozwala nam osiągnąć lepszą stałą.

A jak to się robi w praktyce

Powyższe algorytmy wprawdzie mogą stanowić rozrywkę intelektualną, ale nie zastąpią dwóch (istotnie różnych) praktycznych metod:

  • chodzić na bosaka,
  • porzucić przesąd, że "coś jest nie tak" z posiadaniem różnych skarpet na różnych stopach.3
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-NoDerivs 3.0 License