Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Vloženie triedenia je jednoduchý triediaci algoritmus, ktorý funguje tak, že každý prvok poľa sa vloží na správnu pozíciu v poli. Začína s prázdnym triedeným poľom a potom prechádza cez vstupné pole, pričom každý prvok vkladá na správnu pozíciu v triedenom poli. Tento proces sa opakuje, kým nie je zoradené celé vstupné pole.
Tu je krok za krokom algoritmus na triedenie vkladania:
1. Začnite s prázdnym triedeným poľom.
2. Iterujte cez vstupné pole.
3. Pre každý prvok vo vstupnom poli ho vložte na správnu pozíciu v zoradenom poli.
4. Ak chcete vložiť prvok, porovnajte ho s každým prvkom zoradeného poľa, počnúc prvým prvkom.
5. Ak je prvok menší ako aktuálny prvok v zoradenom poli, vložte ho pred aktuálny prvok.
6. Ak je prvok väčší ako aktuálny prvok v zoradenom poli, pokračujte v porovnávaní s ďalším prvkom v zoradenom poli.
7. Opakujte kroky 4-6, kým prvok nevložíte na správnu pozíciu v triedenom poli.
8. Opakujte kroky 2-7 pre každý prvok vo vstupnom poli.
Zoberme si nasledujúce vstupné pole:
```
[5, 2, 8, 3, 1]
```
Nasledujúce kroky ukazujú, ako by algoritmus zoradenia vloženia zoradil toto pole:
1. Začnite s prázdnym triedeným poľom.
```
[]
```
2. Iterujte cez vstupné pole.
```
[5]
```
3. Pre každý prvok vo vstupnom poli ho vložte na správnu pozíciu v zoradenom poli.
```
[5]
```
4. Ak chcete vložiť prvok 2, porovnajte ho s každým prvkom v triedenom poli, počnúc prvým prvkom.
```
[5, 2]
```
5. Keďže 2 je menšie ako 5, vložte ho pred aktuálny prvok.
```
[2, 5]
```
6. Iterujte cez vstupné pole.
```
[2, 5, 8]
```
7. Pre každý prvok vo vstupnom poli ho vložte na správnu pozíciu v zoradenom poli.
```
[2, 5, 8]
```
8. Ak chcete vložiť prvok 3, porovnajte ho s každým prvkom v zoradenom poli, počnúc prvým prvkom.
```
[2, 3, 5, 8]
```
9. Keďže 3 je menšie ako 5, vložte ho pred aktuálny prvok.
```
[2, 3, 5, 8]
```
10. Iterujte cez vstupné pole.
```
[2, 3, 5, 8, 1]
```
11. Pre každý prvok vo vstupnom poli ho vložte na správnu pozíciu v zoradenom poli.
```
[1, 2, 3, 5, 8]
```
12. Ak chcete vložiť prvok 1, porovnajte ho s každým prvkom v triedenom poli, počnúc prvým prvkom.
```
[1, 2, 3, 5, 8]
```
13. Keďže 1 je menšie ako 2, vložte ho pred aktuálny prvok.
```
[1, 2, 3, 5, 8]
```
14. Zoradené pole je teraz dokončené.
```
[1, 2, 3, 5, 8]
```
Časová zložitosť triedenia vloženia je O(n^2), kde n je dĺžka vstupného poľa. To znamená, že čas chodu triedenia vkladania sa zvyšuje kvadraticky so zvyšovaním veľkosti vstupného poľa. Zoradenie vložením funguje najlepšie, keď je vstupné pole už takmer zoradené, v takom prípade je jeho časová zložitosť O(n).
Triedenie pri vkladaní vyžaduje pomocný priestor O(1), pretože okrem vstupného poľa potrebuje uložiť iba jednu premennú (aktuálny vkladaný prvok).
Vkladanie má niekoľko výhod a nevýhod:
Výhody:
* Jednoduchá implementácia
* Efektívne pre malé polia alebo takmer zoradené polia
* Stabilný algoritmus triedenia (zachováva relatívne poradie rovnakých prvkov)
Nevýhody:
* Nie je efektívne pre veľké polia
* Kvadratická časová zložitosť (O(n^2))
* Nejde o algoritmus triedenia na mieste (vyžaduje dodatočný priestor)
Vloženie triedenia je jednoduchý a efektívny triediaci algoritmus, ktorý funguje dobre pre malé polia alebo takmer zoradené polia. Jeho jednoduchosť a stabilita z neho robí užitočný algoritmus pre vzdelávacie účely a pre špecializované aplikácie. Nie je to však najefektívnejší triediaci algoritmus pre veľké polia, kde by sa mali používať efektívnejšie algoritmy ako quicksort alebo merge sort.