Сортирање уметањем

Сортирање уметањем (енгл. Insertion sort) је једноставан алгоритам за сортирање, који гради завршни сортирани низ једну по једну ставку. Много је мање ефикасан на већим листама од много сложенијих алгоритама као што су qуицксорт, хеапсорт или мергесорт. Међутим сортирање уметањем има своје предности:

Једноставна примена
Ефикасан на малим скуповима података
Прилагодљивији за скупове података који су вец значајно сортирани: Време комплексности је О( н+д ), где је д број инверзија
Ефикаснији у пракси од већине других квадратних ( тј. О ( н² )) алгоритама, као што су селецтион сорт или буббле сорт
Стабилан тј. не мења релативни редослед елемената са једнаким вредностима
У месту (тј. захтева само константан износ О ( 1 ) додатног меморијског простора)
Тренутан (онлине, може да сортира листу, одмах при примању)

Када људи сортирају нешто (шпил карата за игру) већина користи метод сличан сортирању уметањем.

Алгоритми

Сортирање уметањем узима један улазни елемент при сваком проласку и повећава сортирану излазну листу. При проласку, сортирање уметањем уклања један елемент из улазних података, проналази место где припада тај елемент у сортираној листи и ставља га тамо. Понавља проласке све док не остане ниједан улазни елемент.

Сортирање се обично обавља у месту, пролазећи кроз низ, повећавањем сортиране листе. На сваком проласку кроз низ, проверава вредност улазног податка, упоређујући га са највећом вредношћу низа у последњој провери. Ако је већи оставља елемент на месту и прелази на следећи, ако је мањи нађе одговарајућу позицију у низу, помера све веће вредности да направи простор и убацује елемент на исправно место.

Резултујући низ након к итерација представља сортиране првих к+1 („+1“ зато што се први унос прескаче) улазних елемената. У свакој итерацији, први преостали унос из улазних података је уклоњен и убачен у резултујући низ на исправно место, чиме продужава резултат.

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

Претпоставимо да постоји функција Инсерт која убацује вредност у сортирану секвенцу на почетку низа. Почиње рад са краја секвенце и помера елементе једно место удесно, док не нађе одговарајуће место за нови елемент. Пропратна појава ове функције је уништавање првог следећег члана из несортираних улазних елемената.
Да би се извршило сортирање уметањем, потребно је узимати „најлевљи“ елеменат улазног низа и позивати функцију Инсерт. Овим је обезбеђено да функција увек уписује преко „најлевљег елемента“ што је у ствари елемент који се сортира.

Најбољи, најгори и просечан случај

Најбољи случај је када је унос већ сортиран низ, у овом случају сортирање уметањем има линеарно време рада (тј. О(н)). Током сваке итерације, први преостали елемент улазног низа се само упоређује са задњим елементом сортираног низа.

Најједноставнији најгори случај је када је низ у обрнутом редоследу. Скуп свих најгорих случајева улаза састоји се од низова где је сваки елемент најмањи или други најмањи од елемената пре њега. У овим случајевима свака итерација унутрашње петље ће проћи кроз сваки сортирани елемент и померити га, пре него што убаци следећи елемент. То даје сортирању уметањем квадратно време извршавања (О ( н² )).

Просечан случај има такође квадратно време извршавања, што чини сортирање уметањем непрактичним за сортирање већих низова. Међутим, сортирање уметањем је један од најбржих алгоритама за сортирање врло малих низова, чак бржи од qуицксорт-а. Добре верзије квиксорта користе сортирање уметањем за низове мање од одређеног прага.

Пример: Следећа табела приказује кораке за сортирање низа (3, 7, 4, 9, 5, 2, 6, 1). У сваком кораку, елемент у разматрању је подвучен. Део који је померен (или остављен на месту зато што је највећи дотад разматрани) у претходном кораку биће подебљан.

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

Поређење са другим алгоритмима сортирања

Сортирање уметањем је врло сличан селецтион сорт-у. После к пролаза кроз низ, обе методе сортирају првих к елемената. Код селецтион сорт-а ово је к најмањих елемената, док код сортирања уметањем ово представља првих к елемената несортираног низа. Предност сортирања уметањем је што учитава онолико елемената колико му је потребно да одреди позицију к+1 елемента, док селецтион сорт мора проћи до краја низа да би нашао најмањи елемент.

Број поређења која изврши сортирање уметањем је обично око два пута мањи од броја поређења која извршава селецтион сорт. Претпостављајући произвољни ранг к+1 елемента, сортирање уметањем ће извршити просечно померање половине од претходних к елемената, док селецтион сорт мора да прође кроз све несортиране елементе низа. Ако је улазни низ већ сортиран сортирање уметањем извршава само н-1 поређења. Ова особина га чини врло ефикасном алатком када су улазни низови сортирани или “приближно сортирани”.

Иако сортирање уметањем прави мање поређења од селецтион сорт-а, ипак извршава већи број уписа, јер унутрашње петље могу захтевати померање већих делова већ сортираних елемената низа. Уопштено узевши, сортирање уметањем ће уписивати у низ О(н²) пута, док ће селецтион сорт то чинити О(н) пута. Из овог разлога селецтион сорт је бољи избор када је уписивање у меморију значајније од читања из меморије.(код нпр. ЕЕПРОМ или флеш меморије).

Неки подели па владај алгоритми, као сто су qуицксорт и мергесорт врше сортирање тако што рекурзивно деле листе у мање подлисте, које се онда сортирају. Употреба сортирања уметањем за сортирање подлиста се показало као корисна оптимизација у пракси. Овде сортирање уметањем показује боље перформансе од других комплекснијих алгоритама. Величина листи код којих је сортирање уметањем у предности у зависности од окружења и примене варира, али је обично између осам и дванаест елемената.

Варијанте

D. L. Схелл је направио значајна унапређења алгоритма. Унапређена верзија се зове Схелл сорт. Овај алгоритам пореди елементе на растојању које се повећава са сваким новим пролазом. Схелл сорт је приметно побољшао времена извршавања, са две једноставне варијанте које захтевају О(н^3/2) и О (н^4/3) времена за извршавање.

Уколико трошкови поређења премашују трошкове замене, као што је случај са стринговима сачуваним по референци или када је потребна људска интеракција, онда примена бинарног сортирања уметањем може дати боље резултате. Бинарно сортирање уметањем употребљава бинарну претрагу да одреди локацију за убацивање новог елемента и због тога извршава О ⌈лог₂(н)⌉ поређења, у најгорем случају О(н лог(н)). Цели алгоритам и даље има просечно О(н²) време извршавања, јер су серије замена неопходне за свако појединачно убацивање.

Број замена може бити смањен и рачунањем позиција више елемената пре њиховог померања. Нпр. ако се позиција два елемента прорачуна пре померања, број замена може бити смањен до 25% за произвољне податке. У екстремним случајевима ова варијанта ради слично као мергесорт.

Да би се избегло прављење серија замена, улазни подаци могу да буду типа уланчане листе, што би омогућило елементима да буду спојени у листу у константном времену, када је позиција листе позната. Ипак, претрага увезане листе захтева праћење веза до тражене позиције, па се не могу користити методе попут бинарне претраге. Због тога време потребно за претрагу је О (н) и О (н²) за сортирање. При употреби софистициранијих структура података (нпр. хеап (гомила) - или бинарна стабла), време потребно за претрагу и убацивање може бити значајно смањено. Ово представља основу хеап сорт –а и бинарy трее сорт – а.

Двехиљадечетврте Бендер, Фарах-Цолтон и Мостеиро објављују нову варијанту сортирања уметањем названу либрарy сорт. Ова метода оставља мали број некорисћених места кроз читав низ. Овим се постиже да се при уметању елементи померају само до празнине. То омогућује да време извршења буде О (н лог н) са великом вероватноћом.

При употреби увезаних листи време уметања је сведено на О(лог н), и замене нису потребне. Коначно време за читав алгоритам је О (н лог н).

Сортирање уметањем листе је варијанта сортирања уметањем која смањује број потеза у алгоритму.

Код сортирања уметањем листе у програмском језику C

Ако су подаци сачувани у уланчаним листама, онда листа може бити сортирана са само једним додатним местом. Алгоритам креће од празне листе (самим тим тривијално сортиране). Улазни подаци се узимају из листе један по један, а затим стављају на одговарајуће место у сортираној листи. Када је улазна листа празна, сортирана листа је формирана.
Алгоритам испод користи „заостајући показивач“ – траилинг поинтер у сортирану листу. Једноставнија рекурзивна метода поново прави листу сваки пут.

 struct LIST
 {
   struct LIST * pNext;
   int           iValue;
 };
 
 struct LIST * SortList(struct LIST * pList)
 {
  /* stvara sortirani niz od prazne liste */
  struct LIST * pSorted = NULL;
 
  /* uzima jedan po jedan podatak iz ulazne liste, dok ne postane prazna */
  while (pList != NULL)
    {
      /* pamti glavu */
      struct LIST *   pHead  = pList;
      /* pokazivac sa efikasno povezivanje */
      struct LIST ** ppTrail = &pSorted;
 
      pList = pList->pNext;
 
      /* trazi pravo mesto za glavu u sortiranom nizu*/
      while (TRUE)
        {
          /* da li glava pripada ovde? */
          if (*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)
            {
              /* da */
              pHead->pNext = *ppTrail;
              *ppTrail = pHead;
              break;
            }
          else
            {
              /* ne nastavi dalje sa listom */
              ppTrail = & (*ppTrail)->pNext;
            }
        }
    }
 
  return pSorted;
 }

Референце

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "2.1: Insertion sort", Introduction to Algorithms (drugo izd.), MIT Press and McGraw-Hill, str. 15–21, ISBN 0-262-03293-7