Pigeonhole druh - Pigeonhole sort

Pigeonhole druh
TřídaAlgoritmus řazení
Datová strukturaPole
Nejhorší případ výkon, kde N je rozsah klíčových hodnot a n je velikost vstupu
Nejhorší případ složitost prostoru

Třídění holubí díry je třídicí algoritmus který je vhodný pro třídění seznamů prvků, kde je počet prvků (n) a délku rozsahu možných hodnot klíčů (N) jsou přibližně stejné.[1] To vyžaduje Ó (n + N) čas. Je to podobné jako počítání řazení, ale liší se v tom, že „přesune položky dvakrát: jednou do pole kbelíku a znovu do konečného cíle [vzhledem k tomu] počítání řazení vytvoří pomocné pole a poté použije pole k výpočtu konečného cíle každé položky a přesunutí položky tam.“[2]

Algoritmus pigeonhole funguje následovně:

  1. Vzhledem k řadě hodnot, které mají být tříděny, nastavte pomocné pole původně prázdných "pigeonholes", jeden pigeonhole pro každý klíč v rozsah klíčů v původním poli.
  2. Při přechodu na původní pole vložte každou hodnotu do pigeonhole odpovídající jeho klíči, takže každý pigeonhole nakonec obsahuje seznam všech hodnot s tímto klíčem.
  3. Iterujte přes pole pigeonhole ve vzestupném pořadí klíčů a pro každý pigeonhole vložte jeho prvky do původního pole ve vzestupném pořadí.

Příklad

Předpokládejme, že jeden třídí tyto hodnotové páry podle jejich prvního prvku:

  • (5, „ahoj“)
  • (3, „koláč“)
  • (8, „jablko“)
  • (5, „král“)

Pro každou hodnotu mezi 3 a 8 nastavíme pigeonhole a poté přesuneme každý prvek do jeho pigeonhole:

  • 3: (3, „pie“)
  • 4:
  • 5: (5, „ahoj“), (5, „král“)
  • 6:
  • 7:
  • 8: (8, „apple“)

Pole pigeonhole je poté iterováno v pořadí a prvky jsou přesunuty zpět do původního seznamu.

Rozdíl mezi druhem třídění a počítáním spočívá v tom, že v pořadí počítání pomocné pole neobsahuje seznamy vstupních prvků, pouze počítá:

  • 3: 1
  • 4: 0
  • 5: 2
  • 6: 0
  • 7: 0
  • 8: 1

Pro pole kde N je mnohem větší než n, kbelík třídění je zobecnění, které je efektivnější v prostoru a čase.

Implementace Pythonu

def pigeonhole_sort(první) -> Žádný:    "" "Třídit seznam párů (klíč, hodnota) podle klíče." ""    základna = min(klíč pro klíč, hodnota v první)    velikost = max(klíč pro klíč, hodnota v první) - základna + 1    holubí díry = [[] pro _ v rozsah(velikost)]    pro klíč, hodnota v první:        i = klíč - základna        rozškatulkovat = holubí díry[i]        rozškatulkovat.připojit((klíč, hodnota))    i = 0    pro rozškatulkovat v holubí díry:        pro živel v rozškatulkovat:            první[i] = živel            i += 1

Viz také

Reference

  1. ^ Slovník NIST's of Algorithms and Data Structures: pigeonhole sort
  2. ^ Černý, Paul E. "Slovník algoritmů a datových struktur". NIST. Citováno 6. listopadu 2015.