Sortiranje umetanjem

Sortiranje umetanjem (engl. Insertion sort) je jednostavan algoritam za sortiranje, koji gradi završni sortirani niz jednu po jednu stavku. Mnogo je manje efikasan na većim listama od mnogo složenijih algoritama kao što su quicksort, heapsort ili mergesort. Međutim sortiranje umetanjem ima svoje prednosti:

Jednostavna primena
Efikasan na malim skupovima podataka
Prilagodljiviji za skupove podataka koji su vec značajno sortirani: Vreme kompleksnosti je O( n+d ), gde je d broj inverzija
Efikasniji u praksi od većine drugih kvadratnih ( tj. O ( n² )) algoritama, kao što su selection sort ili bubble sort
Stabilan tj. ne menja relativni redosled elemenata sa jednakim vrednostima
U mestu (tj. zahteva samo konstantan iznos O ( 1 ) dodatnog memorijskog prostora)
Trenutan (online, može da sortira listu, odmah pri primanju)

Kada ljudi sortiraju nešto (špil karata za igru) većina koristi metod sličan sortiranju umetanjem.

Algoritmi

Sortiranje umetanjem uzima jedan ulazni element pri svakom prolasku i povećava sortiranu izlaznu listu. Pri prolasku, sortiranje umetanjem uklanja jedan element iz ulaznih podataka, pronalazi mesto gde pripada taj element u sortiranoj listi i stavlja ga tamo. Ponavlja prolaske sve dok ne ostane nijedan ulazni element.

Sortiranje se obično obavlja u mestu, prolazeći kroz niz, povećavanjem sortirane liste. Na svakom prolasku kroz niz, proverava vrednost ulaznog podatka, upoređujući ga sa najvećom vrednošću niza u poslednjoj proveri. Ako je veći ostavlja element na mestu i prelazi na sledeći, ako je manji nađe odgovarajuću poziciju u nizu, pomera sve veće vrednosti da napravi prostor i ubacuje element na ispravno mesto.

Rezultujući niz nakon k iteracija predstavlja sortirane prvih k+1 („+1“ zato što se prvi unos preskače) ulaznih elemenata. U svakoj iteraciji, prvi preostali unos iz ulaznih podataka je uklonjen i ubačen u rezultujući niz na ispravno mesto, čime produžava rezultat.

Najčešće varijante sortiranja umetanjem, koji radi sa nizovima, može se opisati kao:

Pretpostavimo da postoji funkcija Insert koja ubacuje vrednost u sortiranu sekvencu na početku niza. Počinje rad sa kraja sekvence i pomera elemente jedno mesto udesno, dok ne nađe odgovarajuće mesto za novi element. Propratna pojava ove funkcije je uništavanje prvog sledećeg člana iz nesortiranih ulaznih elemenata.
Da bi se izvršilo sortiranje umetanjem, potrebno je uzimati „najlevlji“ elemenat ulaznog niza i pozivati funkciju Insert. Ovim je obezbeđeno da funkcija uvek upisuje preko „najlevljeg elementa“ što je u stvari element koji se sortira.

Najbolji, najgori i prosečan slučaj

Najbolji slučaj je kada je unos već sortiran niz, u ovom slučaju sortiranje umetanjem ima linearno vreme rada (tj. O(n)). Tokom svake iteracije, prvi preostali element ulaznog niza se samo upoređuje sa zadnjim elementom sortiranog niza.

Najjednostavniji najgori slučaj je kada je niz u obrnutom redosledu. Skup svih najgorih slučajeva ulaza sastoji se od nizova gde je svaki element najmanji ili drugi najmanji od elemenata pre njega. U ovim slučajevima svaka iteracija unutrašnje petlje će proći kroz svaki sortirani element i pomeriti ga, pre nego što ubaci sledeći element. To daje sortiranju umetanjem kvadratno vreme izvršavanja (O ( n² )).

Prosečan slučaj ima takođe kvadratno vreme izvršavanja, što čini sortiranje umetanjem nepraktičnim za sortiranje većih nizova. Međutim, sortiranje umetanjem je jedan od najbržih algoritama za sortiranje vrlo malih nizova, čak brži od quicksort-a. Dobre verzije kviksorta koriste sortiranje umetanjem za nizove manje od određenog praga.

Primer: Sledeća tabela prikazuje korake za sortiranje niza (3, 7, 4, 9, 5, 2, 6, 1). U svakom koraku, element u razmatranju je podvučen. Deo koji je pomeren (ili ostavljen na mestu zato što je najveći dotad razmatrani) u prethodnom koraku biće podebljan.

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

Poređenje sa drugim algoritmima sortiranja

Sortiranje umetanjem je vrlo sličan selection sort-u. Posle k prolaza kroz niz, obe metode sortiraju prvih k elemenata. Kod selection sort-a ovo je k najmanjih elemenata, dok kod sortiranja umetanjem ovo predstavlja prvih k elemenata nesortiranog niza. Prednost sortiranja umetanjem je što učitava onoliko elemenata koliko mu je potrebno da odredi poziciju k+1 elementa, dok selection sort mora proći do kraja niza da bi našao najmanji element.

Broj poređenja koja izvrši sortiranje umetanjem je obično oko dva puta manji od broja poređenja koja izvršava selection sort. Pretpostavljajući proizvoljni rang k+1 elementa, sortiranje umetanjem će izvršiti prosečno pomeranje polovine od prethodnih k elemenata, dok selection sort mora da prođe kroz sve nesortirane elemente niza. Ako je ulazni niz već sortiran sortiranje umetanjem izvršava samo n-1 poređenja. Ova osobina ga čini vrlo efikasnom alatkom kada su ulazni nizovi sortirani ili “približno sortirani”.

Iako sortiranje umetanjem pravi manje poređenja od selection sort-a, ipak izvršava veći broj upisa, jer unutrašnje petlje mogu zahtevati pomeranje većih delova već sortiranih elemenata niza. Uopšteno uzevši, sortiranje umetanjem će upisivati u niz O(n²) puta, dok će selection sort to činiti O(n) puta. Iz ovog razloga selection sort je bolji izbor kada je upisivanje u memoriju značajnije od čitanja iz memorije.(kod npr. EEPROM ili fleš memorije).

Neki podeli pa vladaj algoritmi, kao sto su quicksort i mergesort vrše sortiranje tako što rekurzivno dele liste u manje podliste, koje se onda sortiraju. Upotreba sortiranja umetanjem za sortiranje podlista se pokazalo kao korisna optimizacija u praksi. Ovde sortiranje umetanjem pokazuje bolje performanse od drugih kompleksnijih algoritama. Veličina listi kod kojih je sortiranje umetanjem u prednosti u zavisnosti od okruženja i primene varira, ali je obično između osam i dvanaest elemenata.

Varijante

D. L. Shell je napravio značajna unapređenja algoritma. Unapređena verzija se zove Shell sort. Ovaj algoritam poredi elemente na rastojanju koje se povećava sa svakim novim prolazom. Shell sort je primetno poboljšao vremena izvršavanja, sa dve jednostavne varijante koje zahtevaju O(n^3/2) i O (n^4/3) vremena za izvršavanje.

Ukoliko troškovi poređenja premašuju troškove zamene, kao što je slučaj sa stringovima sačuvanim po referenci ili kada je potrebna ljudska interakcija, onda primena binarnog sortiranja umetanjem može dati bolje rezultate. Binarno sortiranje umetanjem upotrebljava binarnu pretragu da odredi lokaciju za ubacivanje novog elementa i zbog toga izvršava O ⌈log₂(n)⌉ poređenja, u najgorem slučaju O(n log(n)). Celi algoritam i dalje ima prosečno O(n²) vreme izvršavanja, jer su serije zamena neophodne za svako pojedinačno ubacivanje.

Broj zamena može biti smanjen i računanjem pozicija više elemenata pre njihovog pomeranja. Npr. ako se pozicija dva elementa proračuna pre pomeranja, broj zamena može biti smanjen do 25% za proizvoljne podatke. U ekstremnim slučajevima ova varijanta radi slično kao mergesort.

Da bi se izbeglo pravljenje serija zamena, ulazni podaci mogu da budu tipa ulančane liste, što bi omogućilo elementima da budu spojeni u listu u konstantnom vremenu, kada je pozicija liste poznata. Ipak, pretraga uvezane liste zahteva praćenje veza do tražene pozicije, pa se ne mogu koristiti metode poput binarne pretrage. Zbog toga vreme potrebno za pretragu je O (n) i O (n²) za sortiranje. Pri upotrebi sofisticiranijih struktura podataka (npr. heap (gomila) - ili binarna stabla), vreme potrebno za pretragu i ubacivanje može biti značajno smanjeno. Ovo predstavlja osnovu heap sort –a i binary tree sort – a.

Dvehiljadečetvrte Bender, Farah-Colton i Mosteiro objavljuju novu varijantu sortiranja umetanjem nazvanu library sort. Ova metoda ostavlja mali broj nekorisćenih mesta kroz čitav niz. Ovim se postiže da se pri umetanju elementi pomeraju samo do praznine. To omogućuje da vreme izvršenja bude O (n log n) sa velikom verovatnoćom.

Pri upotrebi uvezanih listi vreme umetanja je svedeno na O(log n), i zamene nisu potrebne. Konačno vreme za čitav algoritam je O (n log n).

Sortiranje umetanjem liste je varijanta sortiranja umetanjem koja smanjuje broj poteza u algoritmu.

Kod sortiranja umetanjem liste u programskom jeziku C

Ako su podaci sačuvani u ulančanim listama, onda lista može biti sortirana sa samo jednim dodatnim mestom. Algoritam kreće od prazne liste (samim tim trivijalno sortirane). Ulazni podaci se uzimaju iz liste jedan po jedan, a zatim stavljaju na odgovarajuće mesto u sortiranoj listi. Kada je ulazna lista prazna, sortirana lista je formirana.
Algoritam ispod koristi „zaostajući pokazivač“ – trailing pointer u sortiranu listu. Jednostavnija rekurzivna metoda ponovo pravi listu svaki put.

 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;
 }

Reference

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

Spoljašnje veze