Ordigo Adiciante

fonte: http://tiagomadeira.com/2006/01/ordenacao-por-insercao/ 

Ankaŭ konata kiel Inserción Ordigi, Inserción Ordo de la IS por enmeti ero vektora jam bonorda elementoj. En ĉi tiu artikolo, mi donas al vi tiun simplan algoritmon por ordigi tabeloj.
La _pseudocode_ de inserción varo estas kiel sekvas:

  Unu. Por j   2 al vektora longo, fari
 2-a. Elemento   vektoro [j]
 3-a. Mi   j - 1
 4. Dum i> 0 kaj batalarangxis [i]> elemento, do
 5. Vektora [i +1]   tabelo [i]
 6-a. Mi   i - 1
 7. Weekend dum
 8. Array [i +1]   elemento
 9a. To-fino 

Klarigi Mi tion faros ion, kion mi ĉiam faras ripari mian algoritmoj, ŝajnigi mi estas la programo, kurante ĉiu paŝo permane (kompreneble mi kutime rapida ĉar mi ne bezonas skribi ĉion, kion mi faru). Ni komencu per la jena vektora v

v [1]	v [2]	v [3]	v [4]	v [5]	v [6]
5	3	7	8	2	5

Tiam sendu al mi la kodon por starti kun kaj persisti ĝis la longo de la vektoro (6). La unua ordo Li donas al mi estas stoki la elemento ( ) En la variablo elemento. Provizi ĉiujn ekspliko mi ĉiam pentras la griza kie mi estas (ĉi-kaze, la dua ero de la tabelo, 3) kaj la nigra vektoro ne ordema (elementoj ).

v [1]	v [2]	v [3]	v [4]	v [5]	v [6]
5	3	7	8	2	5

Tiam li diras al mi ke . Tiel, . Kaj nun li min iom (kio povus esti anstataŭita de por) kie mi devus iri mia malpliigi. Ni eniras en la buklo ...
Nu, mia estas pli granda ol 0. estas pli granda ol ? Jes, do ni eniri la korpon dum ... Tie li diras al mi fari , Kiu en ĉi tiu kazo estas fari .

v [1]	v [2]	v [3]	v [4]	v [5]	v [6]
5	5	7	8	2	5

Kaj nun mi subtrae de valoro. Tiel, . Li revenas al la momento, sed ne nun kontentigi la kondiĉo Tial ĝi lasis la tempon. Tiam li petas ( ). Sekve, la vektoro aspektas jene:

v [1]	v [2]	v [3]	v [4]	v [5]	v [6]
3	5	7	8	2	5

Kaj pliigo la j nun .

v [1]	v [2]	v [3]	v [4]	v [5]	v [6]
3	5	7	8	2	5

E ... ? Neniu! Do ne eniras la tempon.
(No ŝanĝi)
Kaj tie ni iru kaj daŭrigante ĝis ni ordo vektoro:

v [1]	v [2]	v [3]	v [4]	v [5]	v [6]
2	3	5	5	7	8

Kio estas la logiko?

Kiel mi diris en la enkonduko, sed sen tre klarigo, la Inserción Ordo de la vektora dividas en du. La unua (elementoj ) Enhavas ĉiujn ĝiajn valorojn ordo kaj dua (elementoj ) Enhavas la valoroj por esti enmetita en la unuan vektoro jam ordigis (tiel li nomis Inserción Algoritmo).
La ŝlosilo por la algoritmo okazos dum movo ĉiuj eroj por via enhavo dum la elemento estas pli mallonga ol ili (post la elemento meti kie cxesis).
La variablo elemento nur utilas por ne perdi la valoro de (Ĉar tiam ni kiam )
Mi kredas, ke sendube forlasis super. Preni alian rigardon kaj provu apliki la algoritmon. Se vi pli malfacile ĝin, metis debug mesaĝojn kompreni la strategia algoritmo. (Eg frua meti presi la valoro de j kaj la komenco de ĉiu loko kiel presi la valoroj elemento, i kaj v [i])

Kosti

Vi eble rimarkis ke ĉi tiu algoritmo havas fiksan kosto. Se la tuta vektoro estas ordigita, ĝi neniam bezonos ankaŭ persisti la kaj sekve kuros pli rapide ol se la tuta vektoro estas en descendanta ordo (kiel li ĉiam bezonas persisti ĝis la fino - 0). Do, en ĉi tiu artikolo, mi volas ilin prezenti la analizo de algoritmoj bazita sur kazoj. Por ĉi tiu programo, ni diras:

• Bona okazo estas kiam ĉiuj elementoj estas jam ordigis. Kosto:
• Plej malbona okazo estas kiam la elementoj estas en malsuprenira ordo. Kosto:

En iuj programoj la averaĝa okazo estas ankaŭ grava sed ne estas la kazo de inserción varon. Ni vidas, ke estas tre granda diferenco inter la kosto de la du kazoj. Do ni bezonas scii kie nia algoritmo estos implementado kaj kion la eblojn de li esti la plej bona aŭ malbona afero. En ĝenerala, la plej malbona kazo estas la plej komuna ... Sekve, ni diros, ke la kosto de ĉi tiu algoritmo estas .