algorithm
sorteer-
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:
- Sorteer samenvoegen
- Soort invoeging
- Radix soort
- Tim sorteren
- Bubble Sort
Bekende onstabiele soorten:
