Časová zložitosť triedenia vkladania

Zvážte nasledujúce čísla:

50 60 30 10 80 70 20 40

Ak je tento zoznam zoradený vzostupne, bude to:

10 20 30 40 50 60 70 80

Ak je zoradené v zostupnom poradí, bude to:

80 70 60 50 40 30 20 10

Zoradenie vloženia je triediaci algoritmus, ktorý sa používa na zoradenie zoznamu vo vzostupnom alebo zostupnom poradí. Tento článok sa zaoberá iba triedením vo vzostupnom poradí. Triedenie v zostupnom poradí sa riadi rovnakou logikou ako v tomto dokumente. Cieľom tohto článku je vysvetliť spôsob vkladania. Programovanie sa vykonáva v nasledujúcom príklade v C. Triedenie vkladania je tu vysvetlené pomocou jedného poľa.

Algoritmus na triedenie vloženia

Je uvedený nezoradený zoznam. Cieľom je zoradiť zoznam vo vzostupnom poradí pomocou rovnakého zoznamu. O triedení nezoradeného poľa pomocou rovnakého poľa sa hovorí, že ide o triedenie na mieste. Používa sa tu indexovanie založené na nule. Kroky sú nasledovné:

• • Zoznam sa skenuje od začiatku.
  • Zatiaľ čo skenovanie prebieha, akékoľvek číslo menšie ako u predchodcu sa vymení za predchodcu.
  • Toto zamieňanie pokračuje v zozname, až kým už nie je možné zamieňať.
  • Keď skenovanie dosiahne koniec, triedenie je dokončené.

Ilustrácia zoradenia vloženia

Pri riešení časovej zložitosti je to najhorší prípad, ktorý sa bežne berie do úvahy. Najhoršie usporiadanie pre predchádzajúci zoznam je:

80 70 60 50 40 30 20 10

Existuje osem prvkov s indexmi od nuly do 7.

Pri indexe nula sa skenovanie dostane na 80. Toto je jeden pohyb. Tento jeden pohyb je operácia. Celkovo je zatiaľ jedna operácia (jeden pohyb, žiadne porovnanie a žiadna výmena). Výsledkom je:

| 80 70 60 50 40 30 20 10

Pri indexe jedna dochádza k pohybu na 70. 70 sa porovnáva s 80. 70 a 80 sú vymenené. Jeden pohyb je jedna operácia. Jedno porovnanie je zároveň jedna operácia. Jedna výmena je tiež jedna operácia. Táto časť poskytuje tri operácie. Celkovo sú zatiaľ štyri operácie (1 + 3 = 4). Výsledok je nasledovný:

70 | 80 60 50 40 30 20 10

Na indexe dva dôjde k pohybu na 60. 60 sa porovná s 80, potom sa vymenia 60 a 80. 60 sa porovná so 70, potom sa 60 a 70 vymenia. Jeden pohyb je jedna operácia. Dve porovnania sú dve operácie. Dve výmeny sú dve operácie. Táto časť obsahuje päť operácií. Celkovo je zatiaľ deväť operácií (4 + 5 = 9). Výsledok je nasledovný:

60 70 | 80 50 40 30 20 10

Pri indexe tri dôjde k pohybu na 50. 50 sa porovná s 80, potom sa vymenia 50 a 80. 50 sa porovná so 70, potom sa 50 a 70 vymenia. 50 sa porovná so 60, potom sa 50 a 60 vymenia. Jeden pohyb je jedna operácia. Tri porovnania sú tri operácie. Tri swapy sú tri operácie. Táto časť obsahuje sedem operácií. Celkovo je zatiaľ 16 operácií (9 + 7 = 16). Výsledok je nasledovný:

50 60 70 | 80 40 30 20 10

Pri indexe štyri dôjde k pohybu na 40. 40 sa porovná s 80, potom sa vymenia 40 a 80. 40 sa porovná so 70, potom sa 40 a 70 vymenia. 40 sa porovná so 60, potom sa 40 a 60 vymenia. 40 sa porovná s 50, potom sa 40 a 50 vymenia. Jeden pohyb je jedna operácia. Štyri porovnania sú štyri operácie. Štyri swapy sú štyri operácie. Táto časť obsahuje deväť operácií. Celkovo je to zatiaľ dvadsaťpäť operácií (16 + 9 = 25). Výsledok je nasledovný:

40 50 60 70 80 | 30 20 10

Pri indexe päť dôjde k pohybu na 30. 30 sa porovná s 80, potom sa vymenia 30 a 80. 30 sa porovná so 70, potom sa 30 a 70 vymenia. 30 sa porovná so 60, potom sa vymenia 30 a 60. 30 sa porovná s 50, potom sa 30 a 50 vymenia. 30 sa porovná so 40, potom sa vymenia 30 a 40. Jeden pohyb je jedna operácia. Päť porovnaní je päť operácií. Päť swapov je päť operácií. Táto časť obsahuje jedenásť operácií. Spolu je to zatiaľ tridsaťšesť operácií (25 + 11 = 36). Výsledok je nasledovný:

30 40 50 60 70 80 | 20 10

Na indexe 6 dôjde k pohybu na 20. 20 sa porovná s 80, potom sa vymenia 20 a 80. 20 sa porovná so 70, potom sa 20 a 70 vymenia. 20 sa porovná so 60, potom sa 20 a 60 vymenia. 20 sa porovná s 50, potom sa 20 a 50 vymenia. 20 sa porovná so 40, potom sa 20 a 40 vymenia. 20 sa porovná s 30, potom sa 20 a 30 vymenia. Jeden pohyb je jedna operácia. Šesť porovnaní je šesť operácií. Šesť swapov je šesť operácií. Táto časť obsahuje trinásť operácií. Celkovo je zatiaľ 49 prevádzok (36 + 13 = 49). Výsledok je nasledovný:

20 30 40 50 60 70 80 | 10

Pri indexe sedem dôjde k pohybu k 10. 10 sa porovná s 80, potom sa vymenia 10 a 80. 10 sa porovná so 70, potom sa 10 a 70 vymenia. 10 sa porovná so 60, potom sa 10 a 60 vymenia. 10 sa porovná s 50, potom sa 10 a 50 vymenia. 10 sa porovná s 30, potom sa 10 a 40 vymenia. 10 sa porovná s 30, potom sa 10 a 30 vymenia. 10 sa porovná s 20, potom sa 10 a 20 vymenia. Jeden pohyb je jedna operácia. Sedem porovnaní je sedem operácií. Sedem swapov je sedem operácií. Táto časť poskytuje pätnásť operácií. Spolu je to zatiaľ šesťdesiatštyri prevádzok (49 + 15 = 64). Výsledok je nasledovný:

10 20 30 40 50 60 70 80 10 |

Práca je hotová! Zapojených bolo 64 operácií.

64 = 8 x 8 = 8 ^dva

Časová zložitosť pre triedenie vloženia

Ak existuje n prvkov na triedenie pomocou triedenia vložením, maximálny počet možných operácií by bol n2, ako bolo uvedené vyššie. Zložitosť času zoradenia vloženia je:

O(n ^dva )

Toto používa zápis Big-O. Zápis Big-O začína písmenom O veľkým písmenom, za ktorým nasledujú zátvorky. Vo vnútri zátvoriek je výraz pre maximálny možný počet operácií.

Kódovanie v C

Na samom začiatku skenovania nemôže prvý prvok zmeniť svoju polohu. Program je v podstate nasledovný:

Definícia funkcie insertionSort() používa popísaný algoritmus. Všimnite si podmienky pre slučku while. Vhodná hlavná funkcia C pre tento program je:

Záver

Časová zložitosť pre triedenie vloženia je daná takto:

O(n ^dva )

Čitateľ mohol počuť o časovej zložitosti v horšom prípade, priemernej časovej zložitosti a časovej zložitosti v najlepšom prípade. Tieto variácie časovej zložitosti zoradenia vloženia sú uvedené v ďalšom článku na našej webovej stránke.