Back

ⓘ Pigeonhole sort




                                     

ⓘ Pigeonhole sort

Pigeonhole je algoritam za sortiranje koji je dobar za sortiranje nizova elemenata, gde je broj elemenata jednak n i broj mogućih vrednosti ključeva jednak N. N i n su otprilike jednaki. Algoritam ima složenost od O. Vrlo je sličan sortiranju s prebrojavanjem, ali se razlikuje jer" pomera” članove dva puta. Jednom u" kofu” nizova i onda drugi put na konačno odredište, dok counting sort pravi pomoćni niz i onda ga koristi da izračuna konačno odredište svakog člana I stavlja ga na to mesto.

Pigeonhole sort radi na sledeći način:

  • Prolazi kroz pigeonhole niz po redu i stavlja elemente iz nepraznih rupa nazad u niz.
  • Prolazeći kroz niz koji treba da se sortira, svaka vrednost se stavlja u rupu koja odgovara ključu, tako da svaka rupa sadrži listu vrednosti koje imaju taj ključ.
  • Pošto smo dobili niz vrednosti koje treba sortirati, pravimo pomoćni niz "golubljih rupa" koje su inicijalno prazne, gde svaka rupa odgovara jednom ključu.
                                     

1. Primer

Pretpostavimo da sortiramo ove vrednosti parova po prvom elementu:

  • 5, "hello"
  • 3, "pie"
  • 8, "apple"
  • 5, "king"

Za svaku vrednost koja je izmedu 3 i 8 pravimo rupu, i onda u nju stavljamo odgovarajući element:

  • 4
  • 3: 3, "pie"
  • 5: 5, "hello", 5, "king"
  • 7
  • 8: 8, "apple"
  • 6

Onda prolazimo kroz niz rupa po redu i onda vraćamo elemente u prvobitni niz.

Razlika izmedu pigeonhole sorta i counting sorta je ta što u counting sortu ne postoji lista elemenata u pomoćniom nizu nego samo broj elemenata.

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

Za nizove koji gde je N mnogo veće od n koristi se bucket sort i on se smtra generalizacijom koja je efektivnija što se tiče i vremenske i prostorne složenosti.

Users also searched:

...