logo

TechCodeview

Algoritmy triedenia

A Algoritmus triedenia sa používa na preusporiadanie daného poľa alebo zoznamu prvkov podľa porovnávacieho operátora na prvkoch. Operátor porovnávania sa používa na rozhodnutie o novom poradí prvkov v príslušnej dátovej štruktúre.

Napríklad: Nižšie uvedený zoznam znakov je zoradený vo vzostupnom poradí podľa ich hodnôt ASCII. To znamená, že znak s nižšou hodnotou ASCII bude umiestnený ako prvý ako znak s vyššou hodnotou ASCII.



Obsah

Čo je triedenie?

Triedenie sa týka preskupenia daného poľa alebo zoznamu prvkov podľa porovnávacieho operátora na prvkoch. Operátor porovnávania sa používa na rozhodnutie o novom poradí prvkov v príslušnej dátovej štruktúre. Triedenie znamená zmenu poradia všetkých prvkov vo vzostupnom alebo zostupnom poradí.

typy počítačov

Terminológia triedenia:

  • Triedenie na mieste: Používa sa algoritmus triedenia na mieste konštantný priestor na vytvorenie výstupu (upraví len dané pole). Zoradí zoznam iba úpravou poradia prvkov v zozname. Príklady: triedenie výberu, triedenie podľa bubliny triedenie vloženia a triedenie haldy.
  • Interné triedenie: Interné triedenie je, keď sú všetky údaje umiestnené v Hlavná pamäť alebo vnútorná pamäť . Pri internom triedení problém nemôže presiahnuť jeho veľkosť. Príklad: triedenie haldy, triedenie podľa bubliny, triedenie výberu, rýchle triedenie, triedenie shell, triedenie vkladania.
  • Externé triedenie: Externé triedenie je, keď všetky údaje, ktoré je potrebné triediť, nie je možné umiestniť do pamäte naraz, triedenie sa nazýva externé triedenie. Externé triedenie sa používa pre veľké množstvo údajov. Príklady: Zlúčiť triedenie, Tag sort, Polyphase sort, Four tape sort, External radix sort, atď.
  • Stabilné triedenie: Keď sa objavia dva rovnaké údaje v rovnaký objednať v triedených dátach bez zmeny ich pozície sa nazýva stabilné triedenie. Príklady: Zlúčiť triedenie, vkladanie triedenie, bublinové triedenie.
  • Nestabilné triedenie: Keď sa objavia dva rovnaké údaje v rôzne objednať v triedených údajoch sa nazýva nestabilné triedenie. Príklady: rýchle triedenie, triedenie haldy, triedenie shellu .

Charakteristiky triediacich algoritmov:

  • Časová zložitosť: Časová zložitosť, miera toho, ako dlho trvá spustenie algoritmu, sa používa na kategorizáciu triediacich algoritmov. Najhorší prípad, priemerný prípad a najlepší výkon triediaceho algoritmu možno použiť na kvantifikáciu časovej zložitosti procesu.
  • Priestorová zložitosť: Algoritmy triedenia majú tiež priestorovú zložitosť, čo je množstvo pamäte potrebnej na vykonanie algoritmu.
  • Stabilita: Algoritmus triedenia sa považuje za stabilný, ak sa po zoradení zachová relatívne poradie rovnakých prvkov. To je dôležité v určitých aplikáciách, kde sa musí zachovať pôvodné poradie rovnakých prvkov.
  • Triedenie na mieste: Algoritmus triedenia na mieste je taký, ktorý nevyžaduje dodatočnú pamäť na triedenie údajov. Je to dôležité, keď je dostupná pamäť obmedzená alebo keď sa údaje nedajú presunúť.
  • Prispôsobivosť: Algoritmus adaptívneho triedenia je taký, ktorý využíva už existujúce poradie v údajoch na zlepšenie výkonu.

Aplikácie triediacich algoritmov:

  • Algoritmy vyhľadávania: Triedenie je často kľúčovým krokom vo vyhľadávacích algoritmoch, ako je binárne vyhľadávanie, Ternárne vyhľadávanie, kde je potrebné pred vyhľadaním konkrétneho prvku zoradiť údaje.
  • Správa údajov: Triedenie údajov uľahčuje vyhľadávanie, získavanie a analýzu.
  • Optimalizácia databázy: Triedenie údajov v databázach zlepšuje výkon dotazov.
  • Strojové učenie: Triedenie sa používa na prípravu údajov na trénovanie modelov strojového učenia.
  • Analýza dát: Triedenie pomáha pri identifikácii vzorov, trendov a odľahlých hodnôt v súboroch údajov. Hrá zásadnú úlohu v štatistickej analýze, finančnom modelovaní a iných oblastiach založených na údajoch.
  • Operačné systémy: Algoritmy triedenia sa používajú v operačných systémoch na úlohy, ako je plánovanie úloh, správa pamäte a organizácia súborového systému.

Základy triediacich algoritmov:

  • Úvod do techník triedenia – Štruktúra údajov a návody na algoritmy
  • Aplikácie, výhody a nevýhody triediaceho algoritmu
  • Aký je skutočný príklad triedenia?
  • Čo je triedenie v DSA | Význam triedenia

Algoritmy triedenia:

Implementácie knižnice:

Jednoduché problémy s triedením:

  • Zoraďte prvky podľa frekvencie
  • Zoraďte pole 0s, 1s a 2s
  • Zoraďte čísla uložené na rôznych strojoch
  • Zoraďte pole vo forme vlny
  • Skontrolujte, či sa niektoré dva intervaly neprekrývajú medzi danou sadou intervalov
  • Ako triediť pole dátumov v C/C++?
  • Triedenie reťazcov pomocou Bubble Sort
  • Nájdite chýbajúce prvky rozsahu
  • Zoradiť pole podľa počtu nastavených bitov
  • Zoraďte párne umiestnené prvky v rastúcom a nepárne v zostupnom poradí
  • Zoradiť pole, keď sú zoradené dve polovice
  • Triedenie veľkých celých čísel
  • Zoraďte prepojený zoznam 0, 1 a 2

Stredné problémy s triedením:

  • Počet inverzií v poli pomocou Merge Sort
  • Nájdite Minimálnu dĺžku nezoradeného podpolia, triedením, ktoré zoradí celé pole
  • Zoradiť takmer zoradené (alebo K zoradené) pole
  • Zoraďte n čísel v rozsahu od 0 do n^2 – 1 v lineárnom čase
  • Zoradiť pole podľa poradia definovaného iným poľom
  • Nájdite bod, kde sa maximálne intervaly prekrývajú
  • Nájdite permutáciu, ktorá spôsobí najhorší prípad Merge Sort
  • Zoraďte vektor párov vo vzostupnom poradí v C++
  • Minimálne swapy, aby boli dve polia identické
  • Problém distribúcie čokolády
  • Permutujte dve polia tak, aby súčet každého páru bol väčší alebo rovný K
  • Bucket Sort na triedenie poľa so zápornými číslami
  • Zoraďte Matrix vo všetkých smeroch so zvyšujúcim sa poradím
  • Preveďte pole do zmenšenej formy pomocou Vector of pairs
  • Najmenší rozdiel Triplet z troch polí
  • Skontrolujte, či je možné triediť pole s povolenou podmienenou zámenou susedných

Ťažké problémy s triedením:

  • Nájdite počet prevyšujúcich každého prvku v poli
  • Jednotlivé výskyty počítajte ako podsekvenciu
  • Spočítajte minimálny počet podmnožín (alebo podsekvencií) s po sebe idúcimi číslami
  • Vyberte k prvkov poľa tak, aby sa minimalizoval rozdiel medzi maximom a minimom
  • Minimálny swap potrebný na konverziu binárneho stromu na binárny vyhľadávací strom
  • K-tý najmenší prvok po odstránení niektorých celých čísel z prirodzených čísel
  • Maximálny rozdiel medzi frekvenciou dvoch prvkov, takže prvok s vyššou frekvenciou je tiež väčší
  • Minimálne swapy na dosiahnutie permutovaného poľa s povolenými swapmi najviac na 2 pozíciách
  • Zistite, či je možné vytvoriť rovnaké prvky poľa pomocou jedného externého čísla
  • Po použití danej rovnice zoraďte pole
  • Vytlačte pole reťazcov v zoradenom poradí bez kopírovania jedného reťazca do druhého

Rýchle odkazy:

  • „Problémy precvičovania“ pri triedení
  • „Kvízy“ o triedení

Odporúčané:

  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA