Bästa och sämre ingångar för sortering av hög och snabb sortering?

heap- Eftersom det bästa och värsta fallet är samma spelar det ingen roll ingångsordningen? Antalet jämförelser och uppdrag kommer alltid att vara detsamma? Jag antar att det i en högsortering kan vara detsamma eftersom det verkliga arbetet görs i införandet, men sorteringen använder bara borttagningen av max / min hög? Är det därför?

Antalet jämförelser som faktiskt görs kan bero på i vilken ordning värdena ges. Det faktum att det bästa och värsta fallet var och en Θ (n log n) – förutsatt att alla element är åtskilda – betyder bara att asymptotiskt det inte är någon skillnad mellan de två, även om de kan skilja sig med en konstant faktor. Jag har inte några enkla exempel på detta ovanför mitt huvud, men jag tror att du kan konstruera ingångar där antalet jämförelser skiljer sig med en konstant faktor mellan två tillvägagångssätt. Eftersom stor-O-notering ignorerar konstanter återspeglas detta dock inte i bästa fall och värsta fall-analys.

snabb sortering – Den här Jag vet inte säkert. Jag är inte säker på vad som är fallet i bästa fall och i värsta fall för detta. Om det till exempel är en redan sorterad lista med tio strängar, behöver vi inte alltid välja samma mängd pivoter för att få den rekursiva algoritmen? Någon hjälp med den här förklaringen skulle verkligen hjälpa.

Antalet valda pivoter är verkligen detsamma oavsett algoritmens exekvering. Dock kan arbetet per pivot variera beroende på vilken typ av splittringar du får. I bästa fall hamnar pivoten som valts vid varje steg som det medianelementet i matrisen. När detta händer görs (ungefär) n jämförelser vid rekursions övre skikt, sedan (ungefär) n vid nästa lager eftersom det finns två underarrangemang av storlek n / 2, sedan finns det (ungefär) n vid nästa lager eftersom det finns fyra underarrangemang av storlek n / 4 osv. Eftersom det finns Θ (log n) lager och varje lager gör Θ (n) arbete, det totala arbetet är Θ (n log n). Å andra sidan, överväga att välja det absoluta minimumet för varje matris som en pivot. Sedan (ungefär) görs n jämförelser i det översta lagret, sedan (ungefär) n – 1 i nästa lager, sedan (ungefär) n – 2 i nästa osv. Summan 1 + 2 + 3 + … + n är Θ (n ² ), därav värsta fallet.

Hoppas det hjälper!

Kommentarer

• Sir, hur är det bästa fallet med heapsort nlogn? Om vi anser att alla element är identiska, skulle kostnaden bara gå igenom alla element i matrisen och ingen förskjutning upp till roten. Så det borde vara omega (n) enligt mig.
• Det är en bra poäng. Jag antog distinkta element, så jag uppdaterar det här svaret.

Eftersom ingen ”s riktigt adresserat heapSort ännu:

Om du antar att du använder en max heap representerad som en array och sätter in dina maxelement bakåt i din output array / i baksidan av din array om du gör det på plats , i värsta fall ingång för heapSort är vilken ingång som tvingar dig att ”bubbla ner” eller återupphöja varje gång du tar bort ett element. Detta händer varje gång du försöker sortera en uppsättning utan dubbletter. n), som templatetypedef sa.

Den här egenskapen antyder att heapSorts bästa fall är när alla element är lika (Θ (n), eftersom du inte behöver repetera efter varje borttagning, vilket tar log (n) tid sedan höjdens högsta höjd är log (n)). Det är dock ett eländigt / opraktiskt fall, varför det verkliga bästa fallet för heapsort är Θ (n log n).

Kommentarer

• Din poäng på det eländiga opraktiska fallet ställdes bara i min algoritmklass. (se upp för trickfrågor.) Naturligtvis är jag ’ fortfarande överens med din poäng. ( och fick mitt svar fel som ett resultat XD)

• Snabbsortering

  Värsta fallet: $ \ mathcal {O} (n ^ 2) $ . Låt oss anta att pivotelementet alltid är det rätta elementet: Ange ett redan sorterad lista med $ n $ -element. Så varje partitionering leder till en lista med $ n-1 $ -element och en lista med $ 0 $ -element. Även om du väljer pivotelementet slumpmässigt , du kan fortfarande ha otur och alltid välja det maximala värdet i listan.

  Låt $ T (n) $ vara antalet jämförelser quicksort kräver att du sorterar en lista med $ n $ -element. Värsta fall: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekursiv, $ n $ till partition)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Bästa fall: $ \ mathcal {O} (n \ log n) $ . Om pivotelementet väljs på ett sådant sätt, att det partitionerar listan jämnt:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 gånger $ \ frac {n} { 2} $ rekursivt, $ n $ till partition)} \\ \ i & \ mathcal {O} (n \ log n) & (\ text {masterteorem}) \ end {align}

• Heap Sort

  Det värsta fallet och bästa fallkomplexiteten för högsortering är båda $ \ mathcal {O} (n \ log n) $ . Därför behöver sortering $ \ mathcal {O} (n \ log n) $ jämförelser för alla inmatningsmatriser. Komplexitet av högsortering:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ text {logaritmkvotientregel}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ höger) \ slut {align }

Kommentarer

• Du har ’ svarade på alla OP ’ frågor, så jag svarar på en du saknade; heap sort använder inte ’ t alltid samma antal jämförelser för ett givet antal element. Det värsta fallet är $ a \, n \ log n $ och det bästa fallet är $ b \, n \ log n $, där $ a > b $.
• Observera också att trevägsvariant har linjär bästa fall för inmatning av enstaka element.