Hvorfor sorteres markering hurtigere end boblesortering?

Alle kompleksiteter, du har angivet, er sande, men de er givet i Stor O-notation , så alle additive værdier og konstanter er udeladt.

For at besvare dit spørgsmål, vi har brug for d at fokusere på en detaljeret analyse af disse to algoritmer. Denne analyse kan udføres manuelt eller findes i mange bøger. Jeg bruger resultater fra Knuths Art of Computer Programming .

Gennemsnitligt antal sammenligninger:

• Boblesortering : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Insertion sort : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Valg af sortering : $ (N + 1) H_N – 2N $

Nu, hvis du plotter disse funktioner, får du noget som dette:

Som du kan se, er boblesortering meget dårligere, da antallet af elementer øges, selvom begge sorteringsmetoder har den samme asymptotiske kompleksitet.

Denne analyse er baseret på den antagelse, at input er tilfældigt – hvilket muligvis ikke er sandt hele tiden. Men inden vi begynder at sortere, kan vi tilfældigt tillade indgangssekvensen (ved hjælp af en hvilken som helst metode) for at opnå det gennemsnitlige tilfælde.

Jeg har udeladt tidskompleksitetsanalyse, fordi det afhænger af implementering, men lignende metoder kan bruges.

Kommentarer

• Jeg har et problem med ” vi kan tilfældigt tillade indgangssekvens for at opnå gennemsnitlig sag “. Hvorfor kan det gøres hurtigere end den tid, der kræves til at sortere?
• Du kan tillade enhver række af tal, det vil tage $ N $ tid, hvor $ N $ er sekvenslængde. ‘ er indlysende, at enhver sammenligningsbaseret sorteringsalgoritme skal have mindst $ \ mathcal O (N \ log N) $ kompleksitet, så selvom du tilføjer $ N $ til den ‘ s kompleksitet vandt ‘ t ændres så meget. Alligevel taler vi om sammenligning ikke om tid, tidskompleksitet afhænger af implementering og kørende maskine, som jeg nævnte i svaret.
• Jeg tror jeg var søvnig, du har ret, sekvensen kan permuteres i lineær tid .
• Er din sammenligning bundet korrekt, da $ H_N = \ Theta (log N) $? Det ser ud til, at du ‘ antyder, at det i gennemsnit sammenligner O (n log n).
• Gamma = 0.577216 er Euler-Mascheroni ‘ s konstant. Det relevante kapitel er ” Kunsten at programmere ” vol 3 afsnit 5.2.2 s. 109 og 129. Hvordan plottede du boblesorteringssagen, især O (sqrt (N)) udtrykket? Forsømte du det bare?

Den asymptotiske pris eller $ \ mathcal O $ -notation, beskriver en funktions begrænsende opførsel, da dens argument har tendens til uendelig, dvs. dens vækstrate.

Selve funktionen, f.eks. antallet af sammenligninger og / eller swaps kan være forskelligt for to algoritmer med samme asymptotiske pris, forudsat at de vokser med den samme hastighed.

Mere specifikt kræver boblesortering i gennemsnit $ n / 4 $ swaps pr. post (hver post flyttes elementært fra sin oprindelige position til sin endelige position, og hver swap involverer to poster), mens valg af sortering kun kræver $ 1 $ (når minimum / maksimum er fundet, byttes det en gang til slutningen af arrayet).

Med hensyn til antallet af sammenligninger kræver Bubble sortering $ k \ gange n $ sammenligninger, hvor $ k $ er den maksimale afstand mellem en indgangs startposition og dens endelige position, som normalt er større end $ n / 2 $ for ensartet fordelte startværdier. Valg af sortering kræver dog altid $ (n-1) \ gange (n-2) / 2 $ sammenligninger.

Sammenfattende giver den asymptotiske grænse dig en god fornemmelse for, hvordan omkostningerne ved en algoritme vokser i forhold til inputstørrelsen, men siger intet om den relative ydeevne for forskellige algoritmer inden for det samme sæt.

Kommentarer

• dette er endda meget godt svar
• hvilken bog du foretrækker?
• @GrijeshChauhan: Bøger er et spørgsmål om smag, så tag enhver anbefaling med et saltkorn. Jeg kan godt lide Cormen, Leiserson og Rivest ‘ s ” Introduktion til algoritmer “, hvilket giver et godt overblik over en række emner, og Knuth ‘ s ” Kunsten ved computerprogrammering ” -serie, hvis du har brug for flere / alle detaljer om et bestemt emne. Det kan være en god idé at kontrollere, om spørgsmålet om bøger er blevet stillet her før, eller sende det spørgsmål, hvis det ikke har ‘ t.
• For mig tredje afsnit i dit svar er det egentlige svar. Ikke graferne for store input, givet i andet svar.

Boblesortering bruger flere byttetider, mens valgsortering undgår dette.

Når du vælger sort, byttes det højst n gange. men når du bruger boblesortering, bytter den næsten n*(n-1). Og selvfølgelig er læsetiden mindre end skrivetiden, selv i hukommelsen. Sammenligningstiden og anden køretid kan ignoreres. Så byttetider er den kritiske flaskehals i problemet.

Kommentarer

• Jeg synes, det andet svar fra Bartek er mere rimeligt, men jeg kan ‘ t stemme eller kommentar … BTW Jeg synes stadig, at skrivetid påvirker større og håber, at han kan tage dette i betragtning, hvis han ser dette og er enig.
• Du kan ikke bare ignorere antallet af sammenligninger, da der er brugstilfælde, hvor tid brugt til at sammenligne to emner kan langt overstige den tid, der er brugt på at bytte to emner. Overvej en sammenkædet liste med ekstremt lange strenge (sig 100k tegn hver). At læse i hver streng vil tage meget længere tid end at foretage en omfordeling af markøren.
• @IrvinLim Jeg tror, du måske har ret, men jeg bliver muligvis nødt til at se statistikdataene, før jeg ombestemmer mig. ul>