Beszúró rendezés elemzése

A minimumkiválasztásos rendezéshez hasonlóan a beszúró rendezés is ciklusban halad végig a tömbindexeken. Meghívja az insert-et az $1,2,3,\dots ,n-1$‍ indexekre. Ahogy az indexOfMinimum minden egyes meghívása a rendezett résztömb méretétől függően valamennyi időt vesz igénybe, ez az insert hívásaira is igaz. Tulajdonképpen az előző mondatban a „vesz” szó helyett a „vehet” szót kellene használni, mindjárt látni fogjuk, miért.

Vegyük azt a helyzetet, amikor az insert hívásakor a beszúrandó érték a résztömb minden eleménél kisebb. Például ha 0-t szúrunk be a [2, 3, 5, 7, 11] résztömbbe, akkor a résztömb minden egyes elemét eggyel jobbra kell csúsztatni. Általánosságban, ha egy $k$‍ elemű résztömbbe szúrunk be egy értéket, akkor előfordulhat, hogy az összes $k$‍ elemet arrébb kell csúsztatni eggyel. Ahelyett, hogy pontosan kiszámolnánk, hány programsorra van szükségünk egy elem kulccsal való összevetéséhez és az elem csúsztatásához, maradjunk annyiban, hogy ehhez konstans idő kell, amit jelöljünk $c$‍-vel. Úgyhogy maximum $c\cdot k$‍ sor végrehajtására van szükség egy $k$‍ hosszúságú résztömbbe való beszúráshoz.

Tegyük fel, hogy az insert minden egyes hívásakor a beszúrandó érték kisebb a tőle balra található résztömb minden egyes eleménél. Amikor először hívjuk meg az insert-et, $k=1$‍. Második alkalommal $k=2$‍. A harmadik alkalommal $k=3$‍. És így tovább, egészen az utolsóig, amikor $k=n-1$‍. Ezért a rendezett résztömbbe való beillesztés összideje így alakul:

$c\cdot 1+c\cdot 2+c\cdot 3+\cdots c\cdot (n-1)=c\cdot (1+2+3+\cdots +(n-1))$‍ .

Ez az összeg számtani sorozatot alkot, ami $n-1$‍-ig megy $n$‍ helyett. Használjuk a számtani sorozatra vonatkozó képletet, ez alapján a rendezett résztömbbe való beszúrás összideje:

$c\cdot (n-1+1)((n-1)/2)=c{n}^2/2-cn/2$‍ .

Θ-jelölést alkalmazva elhagyjuk az alacsonyabb rendű $cn/2$‍ tagot és a konstans tényezőket ($c$‍ és 1/2), így azt kapjuk, hogy a beszúró rendezés futási ideje ebben az esetben $\mathrm{\Theta }(n^2)$‍.

Lefuthat a beszúró keresés $\mathrm{\Theta }(n^2)$‍-nél rövidebb idő alatt? A válasz igen. Tegyük fel, hogy ez a kiinduló tömbünk: [2, 3, 5, 7, 11], ahol a rendezett résztömb az első négy elem, és a beszúrandó érték 11. Az első vizsgálatnál azt találjuk, hogy 11 nagyobb, mint 7, úgyhogy a résztömb egy elemét se kell jobbra csúsztatni. Akkor az insert adott hívása csak konstans ideig tart. Tegyük fel, hogy az insert minden egyes hívása csak konstans időt vesz igénybe. Lévén, hogy az insert-et $n-1$‍-szer hívjuk meg, ha minden híváshoz $c$‍ konstans idő kell, akkor a beszúró rendezéshez szükséges teljes idő $c\cdot (n-1)$‍ lesz, ami $\mathrm{\Theta }(n)$‍, nem $\mathrm{\Theta }(n^2)$‍.

Előfordulhatnak ezek az esetek? Elképzelhető, hogy az insert minden egyes hívásakor a résztömb minden elemét jobbra kell csúsztatni? Lehet olyan eset, amikor az insert hívásakor egyetlen elemet se kell elcsúsztatni? Mindkét kérdésre a válasz igen. Az insert hívásakor abban az esetben kell minden elemet jobbra csúsztatni, ha a beillesztendő kulcs kisebb a tőle balra eső összes elemnél. Ha minden elem kisebb az összes, tőle balra található elemnél, akkor a beszúró rendezés futási ideje $\mathrm{\Theta }(n^2)$‍. Mit jelent az, hogy egy elem kisebb a tőle balra levő minden elemnél? A kiinduló tömb visszafelé rendezett sorrendben van, például [11, 7, 5, 3, 2]. Ebből következik, hogy a beszúró rendezés esetében a visszafelé rendezett tömb a legrosszabb eset.

Mi a helyzet az ellenkező esettel? Az insert hívásakor akkor nem kell egyetlen elemet se elcsúsztatni, ha a beillesztendő kulcs nagyobb vagy egyenlő a tőle balra található összes elemnél. Azaz ha minden elem nagyobb vagy egyenlő a tőle balra található összes elemnél, akkor a beszúró rendezés futási ideje $\mathrm{\Theta }(n)$‍. Ez a helyzet akkor fordul elő, ha a kiinduló tömb már rendezett, úgyhogy a beszúró rendezés esetén a legjobb eset, ha a kiinduló tömb már rendezett sorrendben van.

Mit mondhatunk még a beszúró rendezés futási idejéről? Tegyük fel, hogy a kiinduló tömb sorrendje véletlenszerű. Akkor átlagban azt várjuk, hogy minden elem a tőle balra levő elemek felénél lesz kisebb. Ebben az esetben átlagosan az insert egy hívása egy $k$‍ elemet tartalmazó résztömb esetén $k/2$‍ elemet csúsztat el. A futási idő a legrosszabb idő fele lesz. De az aszimptotikus jelölésnél, ahol a konstans együttható nem számít, az átlagos eset futási ideje továbbra is $\mathrm{\Theta }(n^2)$‍ lesz, ugyanúgy, mint a legrosszabb esetben.

Mi van abban az esetben, amikor a kiinduló tömb már „majdnem rendezett”: amikor minden elem maximum egy előre megadott konstans távolságra van (mondjuk 17) a rendezett tömbben elfoglalt helyétől? Akkor az insert minden hívása maximum 17 elemet fog arrébb csúsztatni, így az insert egy hívásához egy $k$‍ elemű résztömb esetében maximum $17\cdot c$‍ idő szükséges. Ez összesen az insert $n-1$‍ hívását jelenti $17\cdot c\cdot (n-1)$‍ futási idővel, ami $\mathrm{\Theta }(n)$‍, és ez megegyezik a legjobb esethez szükséges idővel. Ebből következik, hogy a beszúró rendezés a majdnem rendezett tömb esetében gyors lesz.

Összességében a beszúró rendezés futási ideje:

Ha minden esetre kiterjedően általánosan meg kell határoznunk a beszúró rendezés futási idejét, akkor csak annyit mondhatunk, hogy az $O(n^2)$‍ idő alatt fut le. Nem mondhatod azt, hogy minden esetben $\mathrm{\Theta }(n^2)$‍ a futási idő, mivel a legjobb esetben $\mathrm{\Theta }(n)$‍ a futási idő, és azt sem mondhatod, hogy minden esetben $\mathrm{\Theta }(n)$‍ alatt fut le, mert a legrosszabb esetben $\mathrm{\Theta }(n^2)$‍ a futási idő.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.