Waarom is selectie sneller sorteren dan bellen sorteren?

Alle complexiteiten die je hebt opgegeven zijn waar, hoe ze ook worden gegeven in Big O-notatie , dus alle additieve waarden en constanten zijn weggelaten.

Om uw vraag te beantwoorden, hebben we d om zich te concentreren op een gedetailleerde analyse van die twee algoritmen. Deze analyse kan met de hand worden gedaan of in veel boeken worden gevonden. Ik gebruik de resultaten van Knuths Art of Computer Programming .

Gemiddeld aantal vergelijkingen:

• Bubble sort : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Invoegsortering : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Selectie sorteren : $ (N + 1) H_N – 2N $

Als je nu die functies plot, krijg je zoiets als dit:

Zoals u kunt zien, is het sorteren van bellen veel erger naarmate het aantal elementen toeneemt, ook al hebben beide sorteermethoden dezelfde asymptotische complexiteit.

Deze analyse is gebaseerd op de aanname dat de invoer willekeurig is – wat misschien niet altijd waar is. Voordat we echter beginnen met sorteren, kunnen we de invoervolgorde willekeurig permuteren (met behulp van een willekeurige methode) om het gemiddelde geval te verkrijgen.

Ik heb tijdcomplexiteitsanalyse weggelaten omdat deze afhankelijk is van de implementatie, maar vergelijkbare methoden kunnen worden gebruikt.

Opmerkingen

• Ik heb een probleem met ” we kunnen willekeurig de invoervolgorde wijzigen om een gemiddeld hoofdlettergebruik te verkrijgen “. Waarom kan dat sneller worden gedaan dan de tijd die nodig is om te sorteren?
• U kunt elke reeks getallen permuteren. Het kost $ N $ tijd waar $ N $ de reekslengte is. Het ‘ ligt voor de hand dat elk op vergelijking gebaseerd sorteeralgoritme ten minste $ \ mathcal O (N \ log N) $ complexiteit moet hebben, dus zelfs als je $ N $ eraan toevoegt ‘ s complexiteit zal ‘ niet zo veel veranderen. Hoe dan ook, we hebben het over vergelijking, niet over tijd, de tijdcomplexiteit hangt af van de implementatie en de draaiende machine, zoals ik in het antwoord al zei.
• Ik denk dat ik slaperig was, je hebt gelijk, de volgorde kan worden gewijzigd in lineaire tijd .
• Sinds $ H_N = \ Theta (log N) $, is uw vergelijking correct gebonden voor het sorteren van de selectie? Het lijkt erop dat u ‘ suggereert dat het gemiddeld O (n log n) -vergelijkingen maakt.
• Gamma = 0,577216 is Euler-Mascheroni ‘ s constante. Het relevante hoofdstuk is ” The Art of Programming ” vol 3 sectie 5.2.2 pag. 109 en 129. Hoe heb je het bubbelsorteergeval precies uitgezet, met name de O (sqrt (N)) term? Heb je het gewoon verwaarloosd?

De asymptotische kosten, of $ \ mathcal O $ -notatie, beschrijft het beperkende gedrag van een functie aangezien zijn argument naar oneindig neigt, dwz zijn groeisnelheid.

De functie zelf, bijv. het aantal vergelijkingen en / of swaps kan verschillen voor twee algoritmen met dezelfde asymptotische kosten, op voorwaarde dat ze met hetzelfde tempo groeien.

Meer specifiek vereist Bubble-sortering gemiddeld $ n / 4 $ swaps per item (elk item wordt element-gewijs verplaatst van de beginpositie naar zijn uiteindelijke positie, en elke ruil omvat twee items), terwijl Selection sort slechts $ 1 $ vereist (zodra het minimum / maximum is gevonden, wordt het eenmaal geruild aan het einde van de array).

In termen van het aantal vergelijkingen, vereist Bubble sort $ k \ times n $ vergelijkingen, waarbij $ k $ de maximale afstand is tussen de beginpositie van een item en zijn uiteindelijke positie, die gewoonlijk groter is dan $ n / 2 $ voor uniform verdeelde beginwaarden. Selectie sorteren vereist echter altijd $ (n-1) \ times (n-2) / 2 $ vergelijkingen.

Samenvattend geeft de asymptotische limiet u een goed idee van hoe de kosten van een algoritme groeien met betrekking tot de invoergrootte, maar zegt niets over de relatieve prestaties van verschillende algoritmen binnen dezelfde set.

Reacties

• dit is zelfs een heel goed antwoord
• welk boek heeft jouw voorkeur?
• @GrijeshChauhan: Boeken zijn een kwestie van smaak, dus neem elke aanbeveling met een korreltje zout. Persoonlijk vind ik Cormen, Leiserson en Rivest ‘ s ” Inleiding tot algoritmen “, die een goed overzicht geeft van een aantal onderwerpen, en Knuth ‘ s ” The Art of Computer Programming ” serie als je meer / alle details over een specifiek onderwerp nodig hebt. Misschien wil je controleren of de vraag over boeken hier eerder is gesteld, of die vraag posten als deze niet ‘ t heeft.
• Voor mij, derde alinea in uw antwoord is het daadwerkelijke antwoord. Niet de grafieken voor grote invoer, die in een ander antwoord worden gegeven.

Bij het sorteren van bellen worden meer wisseltijden gebruikt, terwijl selectie sorteren dit vermijdt.

Bij gebruik van sorteren wisselt het maximaal n keer. maar bij gebruik van bubble sort, wordt bijna n*(n-1) omgewisseld. En uiteraard is leestijd minder dan schrijftijd, zelfs in het geheugen. De vergelijktijd en andere looptijd kunnen worden genegeerd. Wisseltijden zijn dus het kritieke knelpunt van het probleem.

Reacties

• Ik denk dat het andere antwoord van Bartek redelijker is, maar ik kan ‘ niet stemmen of commentaar … Trouwens, ik denk nog steeds dat het schrijven van tijd een groter effect heeft en ik hoop dat hij hiermee rekening kan houden als hij dit ziet en ermee instemt.
• Je kunt het aantal vergelijkingen niet simpelweg negeren, aangezien er gebruiksscenarios zijn waarin tijd besteed aan het vergelijken van twee items kan veel meer zijn dan de tijd besteed aan het verwisselen van twee items. Overweeg een gekoppelde lijst met extreem lange tekenreeksen (bijvoorbeeld 100.000 tekens elk). Het inlezen van elke string zou veel langer duren dan het opnieuw toewijzen van de pointer.
• @IrvinLim Ik denk dat je gelijk hebt, maar het kan zijn dat ik de statistische gegevens moet zien voordat ik van gedachten verander.