Сложеност времена сортирања уметања

Размотрите следеће бројеве:

50 60 30 10 80 70 20 40

Ако је ова листа сортирана у растућем редоследу, то би било:

10 20 30 40 50 60 70 80

Ако се сортира у опадајућем редоследу, то би било:

80 70 60 50 40 30 20 10

Сортирање уметањем је алгоритам за сортирање који се користи за сортирање листе у растућем или опадајућем редоследу. Овај чланак се бави само сортирањем у растућем редоследу. Сортирање у опадајућем редоследу следи исту логику дату у овом документу. Циљ овог чланка је да објасни сортирање уметањем. Програмирање је урађено у следећем примеру у Ц. Овде је објашњено сортирање уметањем помоћу једног низа.

Алгоритам за сортирање уметањем

Даје се несређена листа. Циљ је сортирати листу у растућем редоследу користећи исту листу. За сортирање несортираног низа помоћу истог низа каже се да је сортирање на месту. Овде се користи индексирање засновано на нули. Кораци су следећи:

• • Листа се скенира од почетка.
  • Док је скенирање у току, сваки број мањи од претходника се замењује са претходним.
  • Ова замена се наставља дуж листе, све док више није могуће заменити.
  • Када скенирање дође до краја, сортирање је завршено.

Илустрација сортирања уметањем

Када се ради о временској сложености, то је најгори случај који се обично узима у обзир. Најгори аранжман за претходну листу је:

80 70 60 50 40 30 20 10

Постоји осам елемената са индексима од нула до 7.

На индексу нула, скенирање иде на 80. Ово је један покрет. Овај покрет је операција. До сада је извршена укупно једна операција (један покрет, без поређења и без замене). резултат је:

| 80 70 60 50 40 30 20 10

На индексу један, постоји померање на 70. 70 се упоређује са 80. 70 и 80 се замењују. Један покрет је једна операција. Једно поређење је и једна операција. Једна замена је такође једна операција. Овај одељак пружа три операције. До сада има укупно четири операције (1 + 3 = 4). Резултат је следећи:

70 | 80 60 50 40 30 20 10

Код индекса два долази до померања на 60. 60 се пореди са 80, а затим се 60 и 80 замењују. 60 се пореди са 70, а затим се 60 и 70 замењују. Један покрет је једна операција. Два поређења су две операције. Две замене су две операције. Овај одељак пружа пет операција. До сада је било укупно девет операција (4 + 5 = 9). Резултат је следећи:

60 70 | 80 50 40 30 20 10

Код индекса три долази до померања на 50. 50 се пореди са 80, а затим се 50 и 80 замењују. 50 се пореди са 70, а затим се 50 и 70 замењују. 50 се пореди са 60, а затим се 50 и 60 замењују. Један покрет је једна операција. Три поређења су три операције. Три замене су три операције. Овај одељак пружа седам операција. До сада је било укупно шеснаест операција (9 + 7 = 16). Резултат је следећи:

50 60 70 | 80 40 30 20 10

Код индекса четири долази до померања на 40. 40 се пореди са 80, а затим се 40 и 80 замењују. 40 се пореди са 70, а затим се 40 и 70 замењују. 40 се пореди са 60, а затим се 40 и 60 замењују. 40 се пореди са 50, а затим се 40 и 50 замењују. Један покрет је једна операција. Четири поређења су четири операције. Четири замене су четири операције. Овај одељак пружа девет операција. До сада има укупно двадесет пет операција (16 + 9 = 25). Резултат је следећи:

40 50 60 70 80 | 30 20 10

Код индекса пет долази до померања на 30. 30 се пореди са 80, затим се 30 и 80 замењују. 30 се пореди са 70, а затим се 30 и 70 замењују. 30 се пореди са 60, а затим се 30 и 60 замењују. 30 се пореди са 50, а затим се 30 и 50 замењују. 30 се пореди са 40, а затим се 30 и 40 замењују. Један покрет је једна операција. Пет поређења су пет операција. Пет замена су пет операција. Овај одељак пружа једанаест операција. До сада је било укупно тридесет и шест операција (25 + 11 = 36). Резултат је следећи:

30 40 50 60 70 80 | 20 10

Код индекса шест долази до померања на 20. 20 се пореди са 80, а затим се 20 и 80 замењују. 20 се пореди са 70, а затим се 20 и 70 замењују. 20 се пореди са 60, а затим се 20 и 60 замењују. 20 се пореди са 50, а затим се 20 и 50 замењују. 20 се пореди са 40, а затим се 20 и 40 замењују. 20 се пореди са 30, а затим се 20 и 30 замењују. Један покрет је једна операција. Шест поређења су шест операција. Шест замена је шест операција. Овај одељак пружа тринаест операција. До сада је било укупно четрдесет девет операција (36 + 13 = 49). Резултат је следећи:

20 30 40 50 60 70 80 | 10

Код индекса седам долази до померања на 10. 10 се пореди са 80, а затим се 10 и 80 замењују. 10 се пореди са 70, а затим се 10 и 70 замењују. 10 се пореди са 60, а затим се 10 и 60 замењују. 10 се пореди са 50, а затим се 10 и 50 замењују. 10 се пореди са 30, а затим се 10 и 40 замењују. 10 се пореди са 30, а затим се 10 и 30 замењују. 10 се пореди са 20, а затим се 10 и 20 замењују. Један покрет је једна операција. Седам поређења су седам операција. Седам замена су седам операција. Овај одељак пружа петнаест операција. До сада има укупно шездесет четири операције (49 + 15 = 64). Резултат је следећи:

10 20 30 40 50 60 70 80 10 |

Посао је готов! Укључене су 64 операције.

64 = 8 к 8 = 8 ^два

Временска сложеност за сортирање уметањем

Ако постоји н елемената за сортирање помоћу сортирања уметањем, максимални број могућих операција би био н2, као што је претходно показано. Сложеност времена сортирања уметањем је:

На ^два )

Ово користи Биг-О нотацију. Биг-О нотација почиње са О великим словима, након чега следе заграде. Унутар заграда је израз за највећи могући број операција.

Кодирање у Ц

На самом почетку скенирања, први елемент не може да промени своју позицију. Програм је у суштини следећи:

Дефиниција функције инсертионСорт() користи алгоритам како је описано. Обратите пажњу на услове за вхиле-петљу. Прикладна Ц главна функција за овај програм је:

Закључак

Временска сложеност за сортирање уметањем је дата као:

На ^два )

Читалац је можда чуо за временску сложеност у најгорем случају, временску сложеност просечног случаја и временску сложеност у најбољем случају. Ове варијације сложености времена сортирања уметањем разматрају се у следећем чланку на нашој веб страници.