- Del, der flettes
- Sammenlignet
- Skrevet tilbage
- Flettet indtil nu
Flettesortering
Flettesortering er en del og hersk-algoritme. Den deler listen i to, sorterer hver halvdel på samme måde og fletter de to sorterede halvdele ved hele tiden at tage den mindste forreste værdi. Se halvdelene blive flyttet over i en bufferrække og skrevet tilbage i rækkefølge, i enhver hastighed eller ét trin ad gangen, og tæl sammenligninger, skrivninger og fletninger. Tryk på Afspil for at se sorteringen, eller brug Trin og Tilbage for at gå ét trin ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Felterne tæller sammenligninger, skrivninger tilbage i listen og fletninger. 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
- 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.
- Tryk på Afspil, eller brug Trin og Tilbage for at gå ét trin ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i sorteringen.
- Følg hver fletning: de to sorterede halvdele går ned i bufferen, og den mindste forreste værdi går op igen, én ad gangen.
Sådan virker flettesortering
En enkelt værdi er allerede sorteret. Er listen længere, deles den i to halvdele, og hver halvdel sorteres med flettesortering. Derefter flettes de: se på den forreste værdi i hver halvdel, flyt den mindste over i resultatet, og gentag, indtil begge halvdele er tomme. Fordi begge halvdele er sorteret, bliver resultatet også sorteret.
Altid n log n
At dele i to igen og igen giver omkring log₂ n niveauer, og hvert niveau af fletninger skriver hver værdi én gang, så sorteringen laver omkring n log₂ n skrivninger og højst lige så mange sammenligninger. I modsætning til boblesortering, udvælgelsessortering og indsættelsessortering vokser det ikke med n², og listens rækkefølge betyder langt mindre. Prisen er en buffer så lang som listen. Flettesortering er også stabil, og derfor er den grundlaget for sorteringen i Python og Java.
Ofte stillede spørgsmål
Hvordan virker flettesortering?
Den deler listen i to, sorterer hver halvdel med flettesortering og fletter de to sorterede halvdele ved hele tiden at tage den mindste af deres forreste værdier. En liste med én værdi er allerede sorteret, så der stopper delingen.
Hvor mange sammenligninger laver flettesortering?
Højst omkring n log₂ n − n + 1 og mindst omkring halvdelen af n log₂ n for n værdier. For 40 værdier er det højst 177. Skrivningerne tilbage i listen er altid de samme for et givet n: én pr. værdi på hvert fletteniveau.
Hvorfor kræver flettesortering ekstra hukommelse?
Det er svært at flette to halvdele hurtigt på stedet, så den almindelige flettesortering kopierer halvdelene over i en buffer og skriver dem tilbage i rækkefølge. Bufferen er så lang som listen, og det er den største ulempe i forhold til quicksort og heapsort.
Er flettesortering stabil?
Ja. Når de to forreste værdier er lige store, kommer den fra venstre halvdel først, så ens værdier beholder deres oprindelige 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