Sök…


parametrar

Parameter Beskrivning
Stabilitet En sorteringsalgoritm är stabil om den bevarar den relativa ordningen för lika element efter sortering.
På plats En sorteringsalgoritm är på plats om den sorterar med hjälp av endast O(1) hjälpminne (inte räknar den matris som behöver sorteras).
Bästa fall komplexitet En sorteringsalgoritm har en bästa falltidskomplexitet på O(T(n)) om dess driftstid är minst T(n) för alla möjliga ingångar.
Genomsnittlig fallkomplexitet En sorteringsalgoritm har en genomsnittlig falltidskomplexitet på O(T(n)) om dess körtid, i genomsnitt över alla möjliga ingångar , är T(n) .
Värsta fall komplexitet En sorteringsalgoritm har ett värsta fallskomplexitet på O(T(n)) om dess körtid är högst T(n) .

Stabilitet i sortering

Stabilitet vid sortering innebär om en sorteringsalgoritm upprätthåller den relativa ordningen för lika tangenterna för den ursprungliga ingången i resultatutgången.

Så en sortsalgoritm sägs vara stabil om två objekt med lika tangenter visas i samma ordning i sorterad utgång som de visas i den osorterade matchen.

Överväg en lista med par:

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

Nu kommer vi att sortera listan med det första elementet i varje par.

En stabil sortering av listan ger följande lista:

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

Eftersom (9, 3) visas efter (9, 7) i originallistan.

En instabil sortering ger nedanstående lista:

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

Instabil sortering kan generera samma utgång som den stabila sorteringen, men inte alltid.

Kända stabila sorter:

Välkända instabila sorter:



Modified text is an extract of the original Stack Overflow Documentation
Licensierat under CC BY-SA 3.0
Inte anslutet till Stack Overflow