[MUZIKO Ludante] 

DOUG LLOYD: Do inserción varo estas alia algoritmo ni povas uzi por ordigi tabelo. La ideo malantaŭ ĉi tiu algoritmo estas konstrui vian ordo tabelo en lokon, movanta elementoj el la maniero kiel vi iros, por fari lokon. Jen iomete malsama el selektado varo aŭ bobelo speco, ekzemple, kie ni modifu la lokoj, kie ni fari svopoj. 

En tiu kazo, kion ni vere faras estas glitante elementoj super, de la vojo. Kiel funkcias tiu algoritmo labori en _pseudocode_? Nu ni nur arbitre diras ke la unua elemento de la tabelo estas ordigita. Ni konstruis ĝin en loko. 

Ni gonna iri unu elementon je fojo kaj konstrui ĝin, kaj tiel ni unue vidu Estas unu elemento tabelo. Kaj per difino, unu elemento tabelo estas ordigita. 

Tiam ni ripetas ĉi procezo until-- ni ripetas la sekva procezo ĝis ĉiuj de la elementoj estas ordo. Rigardu la sekva unsorted elemento kaj enmeti ĝin en la ordo parton, per sxangxigxantaj la postulata nombro de elementoj de la vojo. Espereble ĉi videbligo helpos vin vidi ekzakte kio estas daŭriganta kun inserción varon. 

Do denove, jen nia tuta unsorted tabelo, ĉiuj elementoj indikitaj en ruĝa. Kaj ni sekvas la paŝojn de niaj _pseudocode_. La unua aĵo kiun ni faras, estas ni nomas la unua ero de la tabelo, ordigitaj. Do ni estas nur gonna diru kvin, vi nun ordo. 

Tiam ni rigardas la sekva unsorted elemento de la tabelo kaj ni volas enmeti ke en la ordo parton, per sxangxigxantaj elementoj super. Do du estas la sekva unsorted elemento de la tabelo. Klare ĝi apartenas antaŭ la kvin, do kio ni estas gonna do estas ia teni du flanken por dua, ŝanĝi kvin super, kaj tiam enmeti du antaŭ kvin, kie devus iri. Kaj nun ni povas diri ke du estas ordo. 

Do kiel vi povas vidi, ni nur ĝis nun rigardis du elementoj de la tabelo. Ni ne rigardis la ripozi tute, sed ni got tiuj du elementoj ordo laŭ vojo de la movanta mekanismo. 

Do ni ripeti la procezon denove. Rigardu la sekva unsorted elemento, tio estas unu. Ni tenu kiu apartigas por dua, ŝanĝi ĉiu, de li unu kie devus iri. 

Denove, ankoraŭ, ni nur iam rigardis unu, du kaj kvin. Ni ne scias kion alian Venas sed ni ordigitaj tiuj tri elementoj. 

Sekva unsorted elemento estas tri, do ni starigis ĝin flanken. Ni movi sur kion ni bezonas kiu, ĉi tiu fojo ne ĉiu kiel en la antaŭa du kazoj, estas nur kvin. Kaj poste ni algluita tri en, inter la du kaj kvin. 

Ses estas la sekva unsorted elemento al la tabelo. Kaj fakte ses estas pli granda ol kvin, do ni eĉ ne bezonas fari neniun swapping. Ni povas nur najlu ses rekte al la fino de la ordo parton. 

Finfine, kvar estas la lasta unsorted elemento. Do ni starigis ĝin flanken, movi super la elementoj ni bezonas movi super, kaj tiam metis kvar kie apartenas. Kaj nun rigardu, ni ia de ĉiuj elementoj. Rimarku kun inserción varon, ni ne havis iri tien kaj reen sur la tabelo. Ni nur iris trans la tabelo unu fojon, kaj ni ŝanĝiĝis aferoj ke ni estus jam renkontis, por por fari lokon por la novaj elementoj. 

Do kio estas la plej malbona kazo scenaro kun inserción varo? En la plej malbona kazo, la tabelo estas en inversa ordo. Vi devas ŝanĝi ĉiun de la n elementoj ĝis n pozicioj, ĉiu ununura tempo ni fari inserción. Ke estas multa ŝanĝado. 

En la plej bona kazo, la tabelo estas perfekte ordigita. Kaj ia kiel kio okazis kun kvin kaj ses en la ekzemplo, kie ni povus simple najlu gxin sur sen devi fari ajnan vagantaj ni estus esence fari tion. 

Se vi imagas, ke nia tabelo estis unu tra ses, ni volas dividi per deklarante unu estas ordo. Du venas post unu do ni povas nur diri, OK, bone unu kaj du estas ordo. Tri venas post du tiel, okej, unu kaj du kaj tri estas ordo. 

Ni ne farante ajnan svopoj, ni estas nur movanta ĉi arbitra linio inter ordo kaj unsorted kiel ni iru. Kiel efike kiel ni faris en la ekzemplo, turnante elementoj blua, kiel ni procedas. Do kio estas la plej malbona kazo tempo de ekzekuto, tiam? Memoru, se ni devas deloki ĉiu el la n elementoj eble n pozicioj, espereble ke donas vin ideon, ke la plej malbona kazo ekzekuto estas Granda a de n kvadratoj. 

Se la tabelo estas perfekte ordo, ĉiuj ni devas fari estas rigardi ĉiu ununura ero fojon, kaj poste ni faris. Do en la plej bona kazo, ĝi estas omega de n. 

Mi Doug Lloyd. Jen CS50.