gru 07 2015 7 grudnia 2015 3 listopada 2016 przez Michał Franczak

Sortowanie pozycyjne

Napisano w

Technika porządkowania kubełkowego wykorzystywana jest na przykład przy sortowaniu listów. Listy rozkładamy do różnych przegródek (kubełków). O tym, do której przegródki trafia dany list decydują różne fragmenty adresu. Liczba tych przegródek jest na ogół niewielka – na przykład dla listów krajowych możemy mieć przegródki etykietowane nazwami województw.

Algorytm polega więc na włożeniu elementów porządkowanego zbioru do kubełków, a następnie opróżnieniu kubełków w odpowiedniej kolejności.

Najpierw musimy określić relację porządku w zbiorze słów, to znaczy musimy określić, które z dwóch danych słów (różnych) ma wystąpić w uporządkowanym ciągu wcześniej. Naturalnym jest, aby przyjąć tzw. porządek leksykograficzny (taki, jaki mamy np. w słowniku) – o kolejności słów decydują litery na pierwszej pozycji, na której dane dwa słowa się różnią. Dodatkowo, jeżeli słowa u i w są różnej długości i słowo u jest prefiksem w, to słowo u występuje wcześniej.

Przypuśćmy, że mamy do uporządkowania słowa zbudowane z czterech znaków: O, P, R, T. Należy zatem utworzyć 4 kubełki. Załóżmy, że mamy do uporządkowania cztery słowa: PORT, POR, TOR, TROP.

W pierwszym kroku przeglądamy listę słów i wybieramy najdłuższe słowa (tutaj: PORT, TROP). Przenosimy je do kubełków na podstawie ostatniego znaku. Następnie opróżniamy kubełki według kolejności, dopisując słowa z każdego kubełka na koniec listy (w kolejności w jakiej zostały wstawione do kubełka). W kolejnych krokach bierzemy pod uwagę kolejną pozycję od końca i wszystkie słowa, które mają znak na tej pozycji.

Etapy sortowania listy słów <lista> = {PORT, POR, TOR, TROP} metodą kubełkową.

  1. Tworzymy kubełki: [O], [P], [R], [T]
  2. Bierzemy pod uwagę pozycję 4:
    1. Wstawiamy słowa do kubełków:
      [O]:
      [P]: TROP
      [R]:
      [T]: PORT
      <lista> = {POR, TOR }
    2. opróżniamy kubełki:
      <lista> = {POR, TOR, TROP, PORT}
  3. Bierzemy pod uwagę pozycję 3
    1. Wstawiamy słowa do kubełków:
      [O]: TROP
      [P]:
      [R]: POR, TOR, PORT
      [T]:
      <lista> = {}
    2. opróżniamy kubełki:
      <lista> = {TROP, POR, TOR, PORT }
  4. Bierzemy pod uwagę pozycję 2
    1. Wstawiamy słowa do kubełków:
      [O]: POR, TOR, PORT
      [P]:
      [R]: TROP
      [T]:
      <lista> = {}
    2. opróżniamy kubełki:
      <lista> = {POR, TOR, PORT, TROP }
  5. Bierzemy pod uwagę pozycję 1
    1. Wstawiamy słowa do kubełków:
      [O]:
      [P]: POR, PORT
      [R]:
      [T]: TOR, TROP
      <lista> = {}
    2. opróżniamy kubełki:
      <lista> = {POR, PORT, TOR, TROP }
  6. STOP. <lista> zawiera słowa w porządku leksykograficznym.

 

źródło: http://loprez.pl

Tagi: