Hvorfor sorterer utvalget raskere enn boblesortering?

Alle kompleksiteter du oppga er sanne, men de er gitt i Stor O-notasjon , så alle additivverdier og konstanter er utelatt.

For å svare på spørsmålet ditt trenger vi d å fokusere på en detaljert analyse av disse to algoritmene. Denne analysen kan gjøres for hånd, eller finnes i mange bøker. Jeg vil bruke resultater fra Knuths Art of Computer Programming .

Gjennomsnittlig antall sammenligninger:

• Boblesortering : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Innsettingssort : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Valgsortering : $ (N + 1) H_N – 2N $

Hvis du plotter disse funksjonene, får du noe slikt:

Som du kan se, er boblesortering mye verre ettersom antall elementer øker, selv om begge sorteringsmetodene har samme asymptotiske kompleksitet.

Denne analysen er basert på antagelsen om at inngangen er tilfeldig – noe som kanskje ikke er sant hele tiden. Før vi begynner å sortere, kan vi imidlertid tilfeldig inngi sekvensen (ved hjelp av en hvilken som helst metode) for å oppnå gjennomsnittlig sak.

Jeg har utelatt tidskompleksitetsanalyse fordi det avhenger av implementering, men lignende metoder kan brukes. / p>

Kommentarer

• Jeg har et problem med » vi kan tilfeldig tillate inngangssekvens for å oppnå gjennomsnittlig tilfelle «. Hvorfor kan det gjøres raskere enn tiden det tar å sortere?
• Du kan tillate en hvilken som helst sekvens av tall det vil ta $ N $ tid der $ N $ er sekvenslengde. ‘ er åpenbart at enhver sammenligningsbasert sorteringsalgoritme må ha minst $ \ mathcal O (N \ log N) $ kompleksitet, så selv om du legger til $ N $ til den ‘ s kompleksitet vantes ‘ t så mye. Uansett snakker vi om sammenligning ikke om tid, tidskompleksitet avhenger av implementering og maskin som kjører, som jeg nevnte i svaret.
• Jeg antar at jeg var søvnig, du har rett, sekvensen kan permuteres i lineær tid .
• Siden $ H_N = \ Theta (log N) $, er sammenligningen din riktig for valgsortering? Det ser ut til at du ‘ antyder at det i gjennomsnitt gjør O (n log n) sammenligninger.
• Gamma = 0.577216 er Euler-Mascheroni ‘ s konstant. Det aktuelle kapittelet er » Kunsten å programmere » vol 3 seksjon 5.2.2 s. 109 og 129. Hvordan plottet du boblesorteringssaken, spesielt O (sqrt (N)) begrepet? Forsømte du det bare?

Den asymptotiske kostnaden, eller $ \ mathcal O $ -notasjon, beskriver den begrensende atferden til en funksjon når dens argument har en tendens til uendelig, dvs. dens veksthastighet.

Selve funksjonen, f.eks. antall sammenligninger og / eller bytter, kan være forskjellig for to algoritmer med samme asymptotiske kostnad, forutsatt at de vokser med samme hastighet.

Mer spesifikt krever boblesortering i gjennomsnitt $ n / 4 $ bytter per oppføring (hver oppføring flyttes elementvis fra sin opprinnelige posisjon til sin endelige posisjon, og hver bytte involverer to oppføringer), mens utvalgssortering bare krever $ 1 $ (når minimum / maksimum er funnet, byttes det ut en gang til slutten av matrisen).

Når det gjelder antall sammenligninger, krever boblesortering $ k \ ganger n $ sammenligninger, hvor $ k $ er den maksimale avstanden mellom oppføringens utgangsposisjon og sin endelige posisjon, som vanligvis er større enn $ n / 2 $ for jevnt fordelte startverdier. Valgsortering krever imidlertid alltid $ (n-1) \ ganger (n-2) / 2 $ sammenligninger.

Oppsummert gir den asymptotiske grensen deg en god følelse av hvordan kostnadene til en algoritme vokser med hensyn til inngangsstørrelsen, men sier ingenting om den relative ytelsen til forskjellige algoritmer innenfor samme sett.

Kommentarer

• dette er til og med veldig godt svar
• hvilken bok du foretrekker?
• @GrijeshChauhan: Bøker er et spørsmål om smak, så ta enhver anbefaling med saltkorn. Jeg liker personlig Cormen, Leiserson og Rivest ‘ s » Introduksjon til algoritmer «, som gir god oversikt over en rekke emner, og Knuth ‘ s » Kunsten å programmere datamaskinen » -serien hvis du trenger mer / alle detaljer om et bestemt emne. Det kan være lurt å sjekke om spørsmålet om bøker har blitt stilt her før, eller legge ut det spørsmålet hvis det ikke har ‘ t.
• For meg tredje paragraf i svaret ditt er det faktiske svaret. Ikke grafene for store innganger, gitt i annet svar.

Bubble sort bruker flere byttetider, mens utvalgssortering unngår dette.

Når du bruker sortering, bytter den n ganger. men når du bruker boblesortering, bytter den nesten n*(n-1). Og tydeligvis er lesetiden mindre enn skrivetiden selv i hukommelsen. Sammenligningstiden og annen kjøretid kan ignoreres. Så byttetider er den kritiske flaskehalsen på problemet.

Kommentarer

• Jeg tror det andre svaret fra Bartek er rimeligere, men jeg kan ‘ t stemme eller kommentar … BTW Jeg tror fortsatt at skrivetiden påvirker større og håper han kan ta hensyn til dette hvis han ser dette og er enig.
• Du kan ikke bare ignorere antall sammenligninger, da det er brukstilfeller der tid brukt på å sammenligne to elementer kan langt overstige tiden som brukes på å bytte to varer. Vurder en koblet liste over ekstremt lange strenger (si 100 000 tegn hver). Å lese i hver streng vil ta mye lengre tid enn å gjøre om pekeren på nytt.
• @IrvinLim Jeg tror du kan ha rett, men jeg må kanskje se statistikkdataene før jeg ombestemmer meg.