Ako by ste zoradili prepojený zoznam?

Triedenie prepojeného zoznamu je možné vykonať pomocou rôznych algoritmov, jedným z bežných prístupov je použitie zlučovacieho triedenia. Zoradenie zlučovania sa riadi stratégiou rozdeľuj a panuj:

1. Rozdeľte zoznam:

- Ak zoznam obsahuje jeden alebo nula uzlov, považuje sa za už zoradený.

- V opačnom prípade rozdeľte zoznam na dve približne rovnaké polovice.

2. Podmaniť si (zoradiť podzoznamy):

- Rekurzívne aplikujte triediaci algoritmus zlúčenia na obe polovice zoznamu a efektívne ich zoraďte.

3. Zlúčte zoradené podzoznamy:

- Začnite s dvoma ukazovateľmi, pričom jeden ukazuje na začiatok každého zoradeného podzoznamu.

- Porovnajte údaje v uzloch označených týmito ukazovateľmi, aby ste určili, ktorý prvok je v zoradenom poradí prvý.

- Pridajte menší prvok do vytváraného nového zoznamu.

- Presuňte príslušný ukazovateľ na ďalší uzol v podzozname.

4. Zopakujte krok 3:

- Pokračujte v porovnávaní a spájaní prvkov z oboch podzoznamov a posúvajte ukazovatele podľa potreby.

- Tento postup opakujte, kým sa všetky prvky z oboch podzoznamov nezlúčia do nového zoznamu.

5. Vráťte zlúčený zoradený zoznam:

- Po zlúčení všetkých prvkov bude výsledný nový zoznam predstavovať zoradený prepojený zoznam. Vráťte tento zoradený zoznam ako konečnú odpoveď.

Systematickým rozdelením zoznamu na menšie časti, ich triedením a opätovným zlúčením, zlučovacie triedenie efektívne triedi celý prepojený zoznam vo vzostupnom poradí. Časová zložitosť tohto prístupu je O(n log n), kde n je počet uzlov v prepojenom zozname.

• Predchádzajúca strana: Ako pridáte tlačidlo darovania Paypal na stránku Google? 
• Ďalšia strana: Čo robí Alt plus FA?