Varför sorteras urval snabbare än bubblasortering?

Alla komplexiteter du angav är sanna, men de ges i Stor O-notering , så alla additiva värden och konstanter utelämnas.

För att svara på din fråga behöver vi d att fokusera på en detaljerad analys av dessa två algoritmer. Denna analys kan göras för hand eller hittas i många böcker. Jag kommer att använda resultat från Knuths Art of Computer Programming .

Genomsnittligt antal jämförelser:

• Bubbelsortering : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Insättningssort : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Val av sortering : $ (N + 1) H_N – 2N $

Om du ritar upp dessa funktioner får du något så här:

Som du kan se är bubblasortering mycket sämre eftersom antalet element ökar, även om båda sorteringsmetoderna har samma asymptotiska komplexitet.

Denna analys baseras på antagandet att ingången är slumpmässig – vilket kanske inte är sant hela tiden. Innan vi börjar sortera kan vi dock slumpmässigt tillåta inmatningssekvensen (med vilken metod som helst) för att få det genomsnittliga fallet.

Jag utelämnade tidskomplexitetsanalys eftersom det beror på implementering, men liknande metoder kan användas.

Kommentarer

• Jag har problem med ” vi kan slumpmässigt tillåta ingångssekvens för att få genomsnittlig fall ”. Varför kan det göras snabbare än den tid som krävs för att sortera?
• Du kan tillåta valfri talföljd det tar $ N $ tid där $ N $ är sekvenslängd. Det ’ är uppenbart att alla jämförelsesbaserade sorteringsalgoritmer måste ha minst $ \ mathcal O (N \ log N) $ komplexitet så även om du lägger till $ N $ till den ’ s komplexitet vann ’ t ändras så mycket. Hur som helst pratar vi om jämförelse inte om tid, tidskomplexitet beror på implementering och maskin som körs, som jag nämnde i svaret.
• Jag antar att jag var sömnig, du har rätt, sekvensen kan permuteras i linjär tid .
• Eftersom $ H_N = \ Theta (log N) $, är din jämförelse bunden för valssortering? Det ser ut som att du ’ antyder att det gör O (n log n) jämförelser i genomsnitt.
• Gamma = 0.577216 är Euler-Mascheroni ’ s konstant. Det relevanta kapitlet är ” Konsten att programmera ” vol 3 avsnitt 5.2.2 sid. 109 och 129. Hur ritade du bubblasorteringsfallen exakt O (sqrt (N)) termen? Försummade du det bara?

Den asymptotiska kostnaden, eller $ \ mathcal O $ -notering, beskriver en funktions begränsande beteende då dess argument tenderar till oändlighet, dvs dess tillväxthastighet.

Själva funktionen, t.ex. antalet jämförelser och / eller byten kan vara olika för två algoritmer med samma asymptotiska kostnad, förutsatt att de växer med samma hastighet.

Mer specifikt kräver bubblasortering i genomsnitt $ n / 4 $ swappar per post (varje post flyttas elementvis från sin ursprungliga position till sin slutposition, och varje swap involverar två poster), medan urvalssortering endast kräver $ 1 $ (när minimum / maximum har hittats byts det en gång till slutet av matrisen).

När det gäller antalet jämförelser kräver Bubblesortering $ k \ gånger n $ -jämförelser, där $ k $ är det maximala avståndet mellan en ingångs initialposition och dess slutliga position, som vanligtvis är större än $ n / 2 $ för jämnt fördelade initialvärden. Val av sortering kräver dock alltid jämförelser mellan $ (n-1) \ gånger (n-2) / 2 $.

Sammanfattningsvis ger den asymptotiska gränsen en bra känsla för hur kostnaden för en algoritm växer med avseende på ingångsstorleken, men säger ingenting om den relativa prestandan för olika algoritmer inom samma uppsättning.

Kommentarer

• det här är till och med ett mycket bra svar
• vilken bok du föredrar?
• @GrijeshChauhan: Böcker är en smakfråga, så ta alla rekommendationer med ett saltkorn. Jag gillar personligen Cormen, Leiserson och Rivest ’ s ” Introduktion till algoritmer ”, vilket ger en bra överblick över ett antal ämnen och Knuth ’ s ” Konsten att datorprogrammering ” -serier om du behöver mer / all information om något specifikt ämne. Du kanske vill kontrollera om frågan om böcker har ställts här tidigare, eller posta den frågan om den inte har ’ t.
• För mig tredje stycket i ditt svar är det faktiska svaret. Inte graferna för stora ingångar, som ges i annat svar.

Bubblesortering använder fler byttider, medan urvalssortering undviker detta.

När du väljer sort byter den n högst. men när du använder bubblasortering byter den nästan n*(n-1). Och uppenbarligen är läsetiden mindre än skrivtiden även i minnet. Jämförelsestiden och annan körtid kan ignoreras. Så bytestider är den kritiska flaskhalsen i problemet.

Kommentarer

• Jag tycker att det andra svaret från Bartek är mer rimligt men jag kan ’ t rösta eller kommentera … BTW Jag tror fortfarande att skrivtiden påverkar större och hoppas att han kan ta hänsyn till detta om han ser detta och håller med.
• Du kan inte bara ignorera antalet jämförelser, eftersom det finns användningsfall där tid spenderas för att jämföra två artiklar kan långt överstiga tiden för att byta två objekt. Tänk på en länkad lista med extremt långa strängar (säg 100 000 tecken vardera). Att läsa i varje sträng skulle ta mycket längre tid än att göra om pekaren tilldelning.
• @IrvinLim Jag tror att du kanske har rätt men jag kan behöva se statistikdata innan jag ändrar mig.