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, \ldots, n-1$1, comma, 2, comma, 3, comma, dots, comma, n, minus, 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$k elemű résztömbbe szúrunk be egy értéket, akkor előfordulhat, hogy az összes $k$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$c-vel. Úgyhogy maximum $c \cdot k$c, dot, k sor végrehajtására van szükség egy $k$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$k, equals, 1. Második alkalommal $k=2$k, equals, 2. A harmadik alkalommal $k=3$k, equals, 3. És így tovább, egészen az utolsóig, amikor $k = n-1$k, equals, n, minus, 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))$c, dot, 1, plus, c, dot, 2, plus, c, dot, 3, plus, \@cdots, c, dot, left parenthesis, n, minus, 1, right parenthesis, equals, c, dot, left parenthesis, 1, plus, 2, plus, 3, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, right parenthesis .

Ez az összeg számtani sorozatot alkot, ami $n-1$n, minus, 1-ig megy $n$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) = cn^2/2 - cn/2$c, dot, left parenthesis, n, minus, 1, plus, 1, right parenthesis, left parenthesis, left parenthesis, n, minus, 1, right parenthesis, slash, 2, right parenthesis, equals, c, n, squared, slash, 2, minus, c, n, slash, 2 .

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

Lefuthat a beszúró keresés $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis-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$n, minus, 1-szer hívjuk meg, ha minden híváshoz $c$c konstans idő kell, akkor a beszúró rendezéshez szükséges teljes idő $c \cdot (n-1)$c, dot, left parenthesis, n, minus, 1, right parenthesis lesz, ami $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, nem $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

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 $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. 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 $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. 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$k elemet tartalmazó résztömb esetén $k/2$k, slash, 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 $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis 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$k elemű résztömb esetében maximum $17 \cdot c$17, dot, c idő szükséges. Ez összesen az insert $n-1$n, minus, 1 hívását jelenti $17 \cdot c \cdot (n-1)$17, dot, c, dot, left parenthesis, n, minus, 1, right parenthesis futási idővel, ami $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, é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)$O, left parenthesis, n, squared, right parenthesis idő alatt fut le. Nem mondhatod azt, hogy minden esetben $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis a futási idő, mivel a legjobb esetben $\Theta(n)$\Theta, left parenthesis, n, right parenthesis a futási idő, és azt sem mondhatod, hogy minden esetben $\Theta(n)$\Theta, left parenthesis, n, right parenthesis alatt fut le, mert a legrosszabb esetben $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis 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.