Urejanje z vstavljanjem

Iz MaFiRaWiki

V podčlanku /Navadno vstavljanje najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Urejanje z vstavljanjem (angl. insertion sort) je algoritem za urejanje podatkov v tabeli. Posebej učinkovito je za urejanje podatkov, ki so že skoraj urejeni.

Pri urejanju z vstavljanjem tabelo v mislih razdelimo na urejeni in neurejeni del. Na začetku je urejeni del prvi element, neurejeni del pa vsi ostali elementi. V vsakem koraku povečamo urejeni del za en element tako, da prvi element neurejenega dela vstavimo na pravo mesto v urejenem delu. To običajno naredimo tako, da ga večkrat zapored zamenjamo z njegovim neposrednim levim sosedom (ga zapeljemo skozi urejeni del).

Vsebina

Časovna zahtevnost

Časovna zahtevnost postopka je v najslabšem primeru O(n2). Najslabši primer je tabela, ki je urejena v obratnem vrstnem redu, saj moramo v tem primeru naslednji element vedno vstaviti na začetek urejenega dela, kar zahteva skupno 1 + 2 + \dots + (n-1) = n (n - 1)/2 korakov.

Če je tabela dolžine n "skoraj urejena", to pomeni, da je sestavljena iz n / k kosov dolžine k, tako da je vsak kos sicer neurejen, vendar na svojem pravem mestu, je časovna zahtevnost postopka O(k2n). Če je k konstanta, neodvisna od n, je v takem primeru časovna zahtevnost postopka linearna. Zaradi te lastnosti, je urejanje z vstavljanjem zadnji korak pri pospešenem hitrem urejanju.

Implementacija

Primer

Neurejena tabela na začetku:

  • 38, 27, 43, 3, 9, 82, 10


Prvo število je že v urejenem delu.

  • 38, 27, 43, 3, 9, 82, 10


Vzamemo drugo število (27), prvo iz neurejenega dela.

  • 38, 27, 43, 3, 9, 82, 10

Primerjamo ga s številom v urejenem delu (38) in ker je 27 manjše od 38, število 38 premaknemo za eno mesto naprej, 27 pa postavimo na prvo mesto.

  • 27, 38, 43, 3, 9, 82, 10


Vzamemo tretje število (43), ki je sedaj prvo v neurejenem delu.

  • 27, 38, 43, 3, 9, 82, 10

Ker število pred njim ni večje, ga pustimo na tistem mestu, kjer je. Sedaj je torej na koncu urejenega dela.

  • 27, 38, 43, 3, 9, 82, 10


Vzamemo četrto število (3), ki je sedaj prvo v neurejenem delu.

  • 27, 38, 43, 3, 9, 82, 10

Število 3 primerjamo s števili pred njim in le-ta prestavljamo, dokler so večja. Število 3 tako pristane na začetku tabele.

  • 3, 27, 38, 43, 9, 82, 10


Vzamemo peto število (9) iz začetka neurejenega dela.

  • 3, 27, 38, 43, 9, 82, 10

Števila pred njim prestavljamo, dokler so večja od 9. Število 9 tako vstavimo na drugo mesto.

  • 3, 9, 27, 38, 43, 82, 10


Vzamemo šesto število (82).

  • 3, 9, 27, 38, 43, 82, 10

Ker števila pred njim niso večja, ga pustimo na istem mestu.

  • 3, 9, 27, 38, 43, 82, 10


Vzamemo zadnje število, ki nam je še ostalo v neurejenem delu (10).

  • 3, 9, 27, 38, 43, 82, 10

Števila pred njim prestavljamo, dokler so večja od 10 in tako pridobimo ustrezno mesto, kamor vstavimo 10.

  • 3, 9, 10, 27, 38, 43, 82


Vsa števila so sedaj v urejenem delu. Tabela je urejena.

  • 3, 9, 10, 27, 38, 43, 82

Glej tudi

Osebna orodja