Sammenligninger
Ombytninger
Udtaget

  • Synker ned
  • Sammenlignet
  • Byttet
  • På plads

Mere om heapsort

Heapsort

Heapsort (hobsortering) læser listen som et binært træ og omordner den til en max-hob, hvor hver forælder er mindst lige så stor som sine børn. Den største værdi står så øverst. Byt den til enden, hvor den bliver, reparer hoben, og gentag. Appen tegner hoben som et træ over søjlerne, så du kan følge hver værdi, mens den synker ned. Tryk på Afspil for at se sorteringen, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Træet over søjlerne viser de samme værdier som en hob. Felterne tæller sammenligninger, ombytninger og de værdier, der er taget ud af hoben. Vælg hvor mange søjler, hvordan de starter, eller skriv dine egne tal. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.

Sådan virker det

  1. Vælg hvor mange søjler og hvordan de starter: tilfældigt, næsten sorteret, omvendt eller med få unikke værdier. Eller skriv dine egne tal.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
  3. Se træet: først synker hver forælder ned, til hoben er bygget, derefter byttes roden til enden, og hoben bliver én kortere.

Sådan virker heapsort

Læs listen som et træ: værdien på plads i har sine børn på pladserne 2i + 1 og 2i + 2. Byg en max-hob ved at lade hver forælder synke ned, begyndende med den sidste forælder: så længe en værdi er mindre end det største af sine børn, bytter de to. Når roden har den største værdi, så byt den med hobens sidste værdi. Den værdi er nu endelig, hoben er én kortere, og den nye rod synker ned, så det igen er en hob. Gentag, til hoben er tom.

Altid n log n, in-place

Træet har omkring log₂ n niveauer, så hver nedsynkning tager højst omkring 2 log₂ n sammenligninger, og at bygge hoben tager under 2n. Det giver heapsort et værste tilfælde på omkring 2n log₂ n sammenligninger, uden buffer: for 40 værdier højst 352. I modsætning til quicksort findes der ingen dårlige input, og i modsætning til merge sort kræver den ingen ekstra hukommelse. I praksis er den som regel langsommere end begge, fordi den hopper rundt i listen, og den er ikke stabil.

Ofte stillede spørgsmål

Hvordan virker heapsort?

Den gør listen til en max-hob, et træ gemt i listen, hvor hver forælder er mindst lige så stor som sine børn. Derefter bytter den gang på gang den største værdi, i roden, til enden af hoben og lader den nye rod synke ned for at reparere hoben.

Hvad er en hob?

Et komplet binært træ gemt i en liste uden pointere: børnene til plads i er pladserne 2i + 1 og 2i + 2. I en max-hob er hver forælder mindst lige så stor som sine børn, så den største værdi står altid i roden, plads 0.

Hvorfor går det hurtigt at bygge hoben?

De fleste værdier ligger nær bunden af træet og kan kun synke et niveau eller to. Lægger man arbejdet sammen over alle niveauer, giver det under 2n sammenligninger for hele opbygningen, ikke n log n.

Er heapsort stabil?

Nej. Når roden byttes til enden, flyttes værdier over lange afstande, så ens værdier kan skifte rækkefølge.

Bliver mine tal sendt nogen steder hen?

Nej. Sorteringen kører i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor