Zoeken…


parameters

Parameter Beschrijving
Stabiliteit Een sorteeralgoritme is stabiel als het de relatieve volgorde van gelijke elementen na het sorteren behoudt.
In situ Sorteerinrichting algoritme is in plaats wanneer sorteert met slechts O(1) hulpgeheugen (nog afgezien van de array die moet worden gesorteerd).
Best case complexiteit Een sorteeralgoritme heeft een best case time complexiteit van O(T(n)) als de looptijd ten minste T(n) voor alle mogelijke ingangen.
Gemiddelde case complexiteit Een sorteeralgoritme heeft een gemiddelde case-time complexiteit van O(T(n)) als de looptijd, gemiddeld over alle mogelijke ingangen , T(n) .
De complexiteit van het ergste geval Een sorteeralgoritme heeft een worst case time complexiteit van O(T(n)) als de looptijd maximaal T(n) .

Stabiliteit bij het sorteren

Stabiliteit bij het sorteren betekent of een sorteeralgoritme de relatieve volgorde van de gelijk-sleutels van de oorspronkelijke invoer in de resultaatuitvoer handhaaft.

Er wordt dus gezegd dat een sorteeralgoritme stabiel is als twee objecten met gelijke sleutels in dezelfde volgorde in gesorteerde uitvoer verschijnen als in de niet-gesorteerde invoer.

Overweeg een lijst met paren:

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

Nu zullen we de lijst sorteren met behulp van het eerste element van elk paar.

Een stabiele sortering van deze lijst geeft de onderstaande lijst weer:

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

Omdat (9, 3) verschijnt na (9, 7) in de oorspronkelijke lijst.

Een onstabiel sorteren zal de onderstaande lijst uitvoeren:

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

Onstabiele sortering kan dezelfde uitvoer genereren als de stabiele sortering, maar niet altijd.

Bekende stabiele soorten:

Bekende onstabiele soorten:



Modified text is an extract of the original Stack Overflow Documentation
Licentie onder CC BY-SA 3.0
Niet aangesloten bij Stack Overflow