Magyarázott algoritmusok rendezése

A rendezési algoritmusok olyan utasítások, amelyek tömböt vagy listát vesznek bemenetként, és az elemeket egy adott sorrendbe rendezik.

A rendezések leggyakrabban numerikus vagy ábécésorrendben (úgynevezett lexikográfiai) vannak, és lehetnek növekvő (AZ, 0-9) vagy csökkenő (ZA, 9-0) sorrendben.

Miért fontos az algoritmusok rendezése?

Mivel a rendezés gyakran csökkentheti a probléma összetettségét, fontos algoritmus a számítástechnikában. Ezeknek az algoritmusoknak közvetlen alkalmazásuk van algoritmusok keresésében, adatbázis-algoritmusokban, osztási és meghódítási módszerekben, adatszerkezeti algoritmusokban és még sok másban.

Néhány általános rendezési algoritmus

A leggyakoribb rendezési algoritmusok közül néhány:

• Válogatás rendezése
• Bubble Sort
• Beszúrás rendezése
• Egyesítés rendezés
• Gyors rendezés
• Halom rendezés
• Számolás rendezés
• Radix Sort
• Vödör rendezése

Rendezési algoritmus osztályozása

A rendezési algoritmusok a következő paraméterek alapján kategorizálhatók:

1. Cserék vagy inverziók száma alapján Ez az ahányszor az algoritmus felcseréli az elemeket a bemenet rendezéséhez. Selection Sortminimális számú csereügyletet igényel.
2. Összehasonlítások száma alapján Ez az ahányszor az algoritmus összehasonlítja az elemeket a bemenet rendezéséhez. A Big-O jelölés használatával a fent felsorolt ​​rendezési algoritmusok példái legalább O(nlogn)a legjobb esetben összehasonlítást igényelnek O(n^2), a legrosszabb esetben pedig az összehasonlításokat a legtöbb kimenethez.
3. Rekurzió vagy nem rekurzió alapján Egyes rendezési algoritmusok, például Quick Sortrekurzív technikákkal rendezik a bemenetet. Más rendezési algoritmusok, például Selection Sortvagy Insertion Sort, nem rekurzív technikákat alkalmaznak. Végül néhány rendezési algoritmus, például a Merge Sortrekurzív és a nem rekurzív technikákat is felhasználja a bemenet rendezéséhez.
4. A stabilitás alapján a rendezési algoritmusokról azt mondják, hogy stableha az algoritmus egyenlő kulcsokkal tartja fenn az elemek relatív sorrendjét. Más szavakkal, két ekvivalens elem ugyanabban a sorrendben marad a rendezett kimenetben, mint a bemenetben.
5. Insertion sort, Merge Sortés Bubble Sortstabilak
6. Heap Sortés Quick Sortnem stabilak
7. Extra helyigény alapján a rendezési algoritmusokról azt mondják, hogy in placeha O(1)a rendezéshez állandó többletterületre van szükségük .
8. Insertion sortés Quick-sorta in placesort, ahogy haladunk az elemeket a pivot és valójában nem használ külön tömböt, ami nem ez a helyzet az egyesítés sort, ahol a bemenet mérete kell felosztani előzetesen tárolja a kimenetet a sort.
9. Merge Sortegy példa a out placerendezésre, mivel a műveleteihez több memória szükséges.

A lehető legjobb időbeli bonyolultság bármilyen összehasonlításon alapuló rendezéshez

Bármely összehasonlításon alapuló rendezési algoritmusnak legalább nLog2n összehasonlítást kell végeznie a bemeneti tömb rendezéséhez, a Heapsort és az egyesítés rendezés pedig aszimptotikusan optimális összehasonlítási sorrend. Ezt a döntési fa diagramjának megrajzolásával könnyen be lehet bizonyítani.