Ordiga algoritmo

El Vikipedio, la libera enciklopedio

fonto: http://en.wikipedia.org/wiki/Sorting_algorithm

En komputika scienco, la ordiga algoritmo estas algoritmo kiu metas erojn de listo en certa ordo. La plej uzataj ordoj estas nombra ordo kaj letera ordo. Efika ordigado estas grava por optimumi la uzon da aliaj algoritmoj (kiel serĉaj kaj mergaj algoritmoj) kiu postulas ordi lertojn por funkcii ĝuste, ĝi estas ankaŭ ofte utila por canonicalizing datumoj kaj por produkti facile legeblan eligon. Pli formale, la eligo devas kontentigi du kondiĉoj:

La eligo estas en ne-malgrandiĝita ordo (ĉiu ero estas pli malgranda ol la antaŭa elemento laŭ la dezirata tuteca ordo);
La eligo estas permuta de la enigo.

Ekde la komputika tagiĝo, la ordiga problemo altiris multan esploradon, eble pro la komplekseco de solvi ĝin efike malgraŭ lia simpla, familiara komunikaĵo. Ekzemple, bobela speco estis analizita kiel frua kiel 1956. ^[1] Kvankam multaj konsideras ke ĝi solvas problemon, utili novajn ordigajn algoritmojn ankoraŭ estas inventita (ekzemple, biblioteka speco estis unue eldonita en 2006). Ordigaj algoritmoj estas ofta en enkondukaj komputikaj klasoj, kie la abundo da algoritmoj por la problemo provizas mildan enkondukon al vario de kernaj algoritmaj konceptoj, kiel granda skribmaniero O, dividi kaj venki algoritmojn, datumstrukturojn, hazardigitajn algoritmojn, pli bona, plej malbona kaj duonaj analizo, spactempa tradeoffs kaj supraj kaj subaj baroj.

Klasifiko

Ordigaj algoritmoj uzataj en komputika scienco estas ofte klasifikita laŭ:

Komputa komplikeco (plej malbona, averaĝa kaj bona konduto) de elementaj komparoj en terminoj de la grandeco de la listo (n). Por tipaj ordigadoj algoritmoj bona konduto estas O(n logo n) kaj malbona konduto estas O(n ²). (Vidu Granda a skribmaniero) Ideala konduto di varo O(n), sed ĉi tio ne estas ebla en la averaĝa okazo. Komparo bazita ordigadaj algoritmoj, kiuj taksas la elementojn de la listo per abstrakta ŝlosilo kompara operacio, bezonas en almenaŭ O(n log n) komparojn por plej enigoj.
Komputa komplikeco de svopoj (por "en lokaj" algoritmoj).
Memoro uzita (kaj uzo de aliaj komputilaj rimedoj). Aparte, iuj ordigi algoritmojn estas " anstataŭ". Strikte, oni loke specas bezoni nur O(1) memoro preter la erojn esti ordo; foje O(log (n)) plia memoro konsideras "loke".
Rekursio. Iuj algoritmoj estas ĉu rekursie aŭ ne-rekursie, dum aliaj povas esti ambaŭ (ekzemple kunfandi varon).
Stabileco: stabilaj ordigaj algoritmoj subtenas la relativan ordon de registroj kun egalaj ŝlosiloj (tio estas, valoroj).
Kio estas kompara speco. Kompara speco analizas la datumojn nur komparante du elementoj kun kompara operatoro.
Ĝenerala metodo: adicio, interŝanĝo, selektado, kunfando, ktp. interŝanĝaj varoj inkludas bobelan varon kaj quicksort. Selektadaj varoj inkludas cocteleran varon kaj heapsort.
Adaptableco: Ĉu aŭ ne la presortedness de la enigo tuŝas la rulan tempon. Algoritmoj kiuj prenas ĉitia konsidero estas sciata kiel adapta.

Stabileco

Stabilaj ordigaj algoritmoj subtenas la relativan ordon de registroj kun egalaj klavoj. (Ŝlosilo estas tiu parto de la libreto, kiu estas la bazo por la varo; ĝi povas aŭ ne inkluzivas ĉiujn rekordojn.) Se ĉiuj klavoj estas malsamaj tiam tiu distingo ne estas necesa. Sed se estas egalaj klavoj, tiam ordiga algoritmo estas stabila se kiam ajn estas du registroj (diru R kaj S) kun la sama tonalo, kaj R aperas antaŭ S en la originala listo, tiam R ĉiam aperas antaŭ S en la orda listo. Kiam egalaj elementoj estas nedistingebla, kiel kun entjeroj, aŭ pli ĝenerale, ajna datumoj kie la tuta elemento estas la ŝlosilo, stabileco ne estas problemo. Tamen, supozu, ke la sekvaj paroj de nombroj devas esti ordata laŭ iliaj unua komponanto:

 (4, 2) (3, 7) (3, 1) (5, 6)

En ĉi tiu kazo, du malsamajn rezultojn estas eblaj, unu kiu subtenas la relativa ordo de registroj kun egalaj ŝlosiloj, kaj unu kiu ne:

 (3, 7) (3, 1) (4, 2) (5, 6) (ordono subtenis)
 (3, 1) (3, 7) (4, 2) (5, 6) (ordono ŝanĝita)

Malstabilaj ordigadaj algoritmoj povas ŝanĝi la relativan ordon da registroj kun egalaj klavoj, sed stabilaj ordigaj algoritmoj neniam fari tion. Malstabila ordigado algoritmoj povas esti speciale implementado esti stabila. Unu maniero fari tion estas artefarite etendi la ŝlosilan komparon, por ke komparoj inter du celoj kun alimaniere egalaj ŝlosiloj estas decidita per la ordono de la elementoj en la originalaj datumoj ordo kiel egaleco-breaker. Memorante ĉi tiu ordo, tamen, ofte engaĝas plia komputan koston.
Ordigo bazita sur primara, duaranga, terciaraj, ktp speco de ŝlosilo povas fari ajnan ordigan metodon, prenante ĉiuj specaj klavoj en rakontas en komparoj (alivorte, uzante sola komponigita speca klavo). Se ordiga metodo estas stabila, ĝi estas ankaŭ ebla por ordigi multnombrajn okazojn, ĉiufoje per unu speca ŝlosilo. En tiu kazo la klavoj bezonas esti aplikita orde de kreskanta prioritato.
Ekzemplo: ordigi parojn da nombroj kiel pli supre per dua, tiam unua komponanto:

 (4, 2) (3, 7) (3, 1) (5, 6) (originala)

 (3, 1) (4, 2) (5, 6) (3, 7) (post klarigo de dua komponanto)
 (3, 1) (3, 7) (4, 2) (5, 6) (post klarigo de unua komponanto)

Aliflanke:

 (3, 7) (3, 1) (4, 2) (5, 6) (post klarigo de unua komponanto)
 (3, 1) (4, 2) (5, 6) (3, 7) (post klarigo de dua komponanto, 
                                 ordon per unua komponanto estas perturbita).

Komparo de algoritmoj

En ĉi tiu tablo, n estas la nombro da rekordoj ordita. La kolumnoj "Average" kaj "malbona" donas la tempan kompleksecon en ĉiu kazo, sub la supozo, ke la longo de ĉiu klavo estas konstanta, kaj ke sekve ĉiuj komparoj, svopoj, kaj aliaj bezonataj operacioj povas procedi en konstanta tempo. "Memoro" signifas la kvanton helpaj stokado bezonis preter tiu uzata de la listo mem, sub la sama supozo. Ĉi tiuj estas ĉiuj komparaj specoj. La ekzekuta tempo kaj la algoritma memoro povus esti mezurita uzante diversaj skribmanieroj kiel theta, omega, Granda-O, malgrandaj-o, ktp La memoro kaj la sinsekvaj fojoj sube estas aplikebla por ĉiuj 5 notacioj.

Komparo specoj
Nomo	Bona	Averaĝa	Plej	Memoro	Stabila	Metodo	Aliaj notoj
Quicksort	$\ Mathcal {} n \ log n$	$\ Mathcal {} n \ log n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} \ log n$	Dependas	Dispartiganta	Quicksort estas kutime farita en placo kun O (log (n)) pilo spaco. ^{[ citaĵo bezonata ]} Plej implementaciones estas malstabila, tiel stabila en-loko particionado estas pli kompleksa. Naïve variantoj uzi O (n) spaco tabelo por stoki la dispartigo . ^{[ citaĵo bezonata ]}
Kunfandi speco	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	Depends; plej malbona kazo estas $\ Mathcal {} n$	Jes	Kunfandi	Tre _parallelizable_ (ĝis O (log (n))) por procesi grandaj kvantoj de datumoj.
En-loko Merge speco	$\ Mathcal {} -$	$\ Mathcal {} -$	$\ Mathcal {} {n \ left (\ log n \ right) ^ 2}$	$\ Mathcal {} {1}$	Jes	Kunfandi	Implementado en Norma Ŝablona Biblioteko (STL); ^[2] povas esti realigita kiel stabila speco bazita sur stabila en-loko kunfandi. ^[3]
Heapsort	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {1}$	Neniu	Selektado
Inserción speco	$\ Mathcal {} n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Jes	Inserción	O (n + d), kie d estas la nombro de inversigoj
Introsort	$\ Mathcal {} n \ log n$	$\ Mathcal {} n \ log n$	$\ Mathcal {} n \ log n$	$\ Mathcal {} \ log n$	Neniu	Particionado & Elekto	Uzata en pluraj STL implementaciones
Selektado speco	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Neniu	Selektado	Stabila kun O (n) ekstra spaco, ekzemple uzante listojn. ^[4] Uzita por ordigi ĉi tablo en Safari aŭ aliaj Webkit retumilo. ^[5]
Timsort	$\ Mathcal {} {n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} n$	Jes	Inserción & kunfandi	$\ Mathcal {} {n}$ komparoj kiam la datumoj jam ordo aŭ reversa ordo.
Konko speco	$\ Mathcal {} n$	$\ Mathcal {} n (\ log n) ^ 2$ aŭ $\ Mathcal {} n ^ {3/2}$	Dependas breĉo vico; plej konata estas $\ Mathcal {} n (\ log n) ^ 2$	$\ Mathcal {} 1$	Neniu	Inserción
Bobelo speco	$\ Mathcal {} n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Jes	Interŝanĝi	Tiny kodo grandeco
Duuma arbo speco	$\ Mathcal {} n$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} n$	Jes	Inserción	Kiam uzanta mem-balancadon duuma serĉarbo
Ciklo speco	-	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Neniu	Inserción	En-placo kun teorie optimuma nombro de skribas
Biblioteko speco	-	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n$	Jes	Inserción
Pacienco ordigado	-	-	$\ Mathcal {} n \ log n$	$\ Mathcal {} n$	Neniu	Inserción & Elekto	Trovas ĉiujn plej longa kreskanta subvicoj, subvicas ene O (n logo n)
Smoothsort	$\ Mathcal {} {n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {1}$	Neniu	Selektado	An adapta speco - $\ Mathcal {} {n}$ komparoj kiam la datumoj jam ordo, kaj 0 svopoj.
Strand speco	$\ Mathcal {} n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n$	Jes	Selektado
Turniro speco	-	$\ Mathcal {} n \ log n$	$\ Mathcal {} n \ log n$			Selektado
Cocktail speco	$\ Mathcal {} n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Jes	Interŝanĝi
Kombilon speco	$\ Mathcal {} n$	$\ Mathcal {} n \ log n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Neniu	Interŝanĝi	Malgrandaj kodo grandeco
Gnome speco	$\ Mathcal {} n$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} n ^ 2$	$\ Mathcal {} {1}$	Jes	Interŝanĝi	Tiny kodo grandeco
Bogosort	$\ Mathcal {} n$	$\ Mathcal {} n \ cdot n!$	$\ Mathcal {} {n \ cdot n! \ To \ infty}$	$\ Mathcal {} {1}$	Neniu	Sorto	Hazarde permute la tabelo kaj kontrolu ĉu ordo.
^[6]	$\ Mathcal {} -$	$\ Mathcal {} n \ log n$	$\ Mathcal {} {n \ log n}$	$\ Mathcal {} {1}$	Jes

La sekva tabelo priskribas entjerajn ordigadajn algoritmojn kaj aliaj ordigaj algoritmojn kiuj ne estas komparaj specoj. Kiel tia, ne estas limigita per $\ Omega \ left ({n \ log n} \ right)$ malsupreniri baron. Komplekseco sube estas en terminoj de n, la nombro de artikoloj por esti ordo, k, la grandeco de ĉiu klavo, kaj d, la cifera grandeco uzata de la efektivigo. Multaj el ili estas bazitaj sur la supozo, ke la ŝlosila grandeco estas sufiĉe granda, ke ĉiuj elementoj havas solan ŝlosilon valoroj, kaj do ke n << 2^k, kie << signifas "multe malpli ol".

Ne-komparo specoj
Nomo	Bona	Averaĝa	Plej	Memoro	Stabila	n << 2 ^k	Notoj
Faka speco	-	$\; N + 2 ^ k$	$\; N + 2 ^ k$	$\; 2 ^ k$	Jes	Jes
Sitelo speco (uniforma klavoj)	-	$\; N + k$	$\; N ^ 2 \ cdot k$	$\; N \ cdot k$	Jes	Neniu	Supozas uniforma distribuo de eroj de la domajno en la tabelo. ^[7]
Sitelo speco (entjera klavoj)	-	$\; N + r$	$\; N + r$	$\; N + r$	Jes	Jes	r estas la limigo de nombroj esti ordo. Se r = $\ Mathcal {O} \ left ({n} \ right)$ tiam AVG RT = $\ Mathcal {O} \ left ({n} \ right)$ ^[8]
Counting speco	-	$\; N + r$	$\; N + r$	$\; N + r$	Jes	Jes	r estas la limigo de nombroj esti ordo. Se r = $\ Mathcal {O} \ left ({n} \ right)$ tiam AVG RT = $\ Mathcal {O} \ left ({n} \ right)$ ^[7]
LSD radix Ordigi	-	$\; N \ cdot \ frac {k} {d}$	$\; N \ cdot \ frac {k} {d}$	$\ Mathcal {} n$	Jes	Neniu	^[7] ^[8]
MSD radix Ordigi	-	$\; N \ cdot \ frac {k} {d}$	$\; N \ cdot \ frac {k} {d}$	$\ Mathcal {} n + \ frac {k} {d} \ cdot 2 ^ d$	Jes	Neniu	Stabila versio uzas eksteran tabelo de amplekso n teni ĉiuj la ujojn
MSD radix Ordigi	-	$\; N \ cdot \ frac {k} {d}$	$\; N \ cdot \ frac {k} {d}$	$\ Frac {k} {d} \ cdot 2 ^ d$	Neniu	Neniu	En-Placo. k / d rekursio niveloj, 2 ^d por grafo tabelo
Spreadsort	-	$\; N \ cdot \ frac {k} {d}$	$\; N \ cdot \ left ({\ frac {k} {s} + d} \ right)$	$\; \ Frac {k} {d} \ cdot 2 ^ d$	Neniu	Neniu	_asymptotics_ Baziĝas sur la supozo ke n << 2 ^k, sed la algoritmo ne postulas tion.

La sekva tabelo priskribas iujn ordigi algoritmoj kiuj estas nepraktika por reala vivo uzo pro ekstreme malriĉa agado aŭ postulo por specialigitaj aparataro.

Nomo	Bona	Averaĝa	Plej	Memoro	Stabila	Komparo	Aliaj notoj
Bido speco	-	N / A	N / A	-	N / A	Neniu	Postulas specialigitaj aparataro
Simpla pancake speco	-	$\ Mathcal {} n$	$\ Mathcal {} n$	$\ Mathcal {} {\ log n}$	Neniu	Jes	Grafo estas nombro de klakas.
Spaghetti (Poll) speco	$\ Mathcal {} n$	$\ Mathcal {} n$	$\ Mathcal {} n$	$\ Mathcal {} n ^ 2$	Jes	Polling	Ĉi Lineara tempo, analoga algoritmo por ordigo vico de eroj, postulante O (n) pilo spaco, kaj la varo estas stabila. Tio necesigas $n$ paralela procesoroj. Spaghetti speco # Analizo
Ordigo retoj	-	$\ Mathcal {} {\ log n}$	$\ Mathcal {} {\ log n}$	$\ Mathcal {} {n \ cdot \ log (n)}$	Jes	Neniu	Postulas kutimo cirkvito de grandeco $\ Mathcal {O} \ left (n \ cdot \ log (n) \ right)$

Aldone, teoria komputilaj sciencistoj detalas aliajn ordigadajn algoritmojn kiuj havigas pli bonan ol $\ Mathcal {O} \ left ({n \ log n} \ right)$ tempa komplekseco kun aldonaj limigoj, inkluzive de:

Han-algoritmo, determina algoritmo kiu ordigas domajnajn klavojn de finia amplekso, prenante $\ Mathcal {O} \ left ({n \ log \ log n} \ right)$ tempo kaj $\ Mathcal {O} \ left ({n} \ right)$ spaco. ^[9]
Thorup-algoritmo, oni hazardigita algoritmo por ordigi ŝlosilojn da domajno de finia amplekso, prenante $\ Mathcal {O} \ left ({n \ log \ log n} \ right)$ tempo kaj $\ Mathcal {O} \ left ({n} \ right)$ spaco. ^[10]
Entjera ordigada algoritmo prenas $\ Mathcal {O} \ left ({n \ sqrt {\ log \ log n}} \ right)$ atendi tempon kaj $\ Mathcal {O} \ left ({n} \ right)$ spaco. ^[11]

Algoritmoj ankoraŭ ne komparis supre estas:

Resumoj de populara ordigado algoritmoj

Bobelo speco

Bobela varo, ordiga algoritmo kiu senĉese paŝas tra listo, interŝanĝante erojn ĝis ili aperas en la ĝusta ordo.

Ĉefa artikolo: Bobela speco

Bobela varo estas simpla ordigada algoritmo. La algoritmo startas komence de la datumaro. Ĝi komparas la du unuaj elementoj, kaj se la unua estas pli granda ol la dua, svopas ilin. Ĝi daŭre faras tion por ĉiu paro de najbaraj elementoj al la fino de la datuma aro. Ĝi tiam komencas denove kun la du unuaj elementoj, ripetante ĝis neniu svopoj okazis en la lasta paŝo. Ĉi tiu algoritmo estas mezumo kaj plej malbona kazo agado estas O (n²) do ĝi estas malofte uzata por ordigi grandajn, neordigitajn, datumajn arojn. Bobela varo povas esti uzata por ordigi malgrandan nombron da eroj (kie lia asimptota ne-efika por alta puno). Bobela varo povas ankaŭ uzi efike sur listo de ajna longo kiu preskaŭ ordo (tio estas, la elementoj ne estas signife maloportune). Ekzemple, se iu nombro da eroj estas maloportune por nur unu pozicio (ekzemple, 0123546789 kaj 1032547698), bobela speco de interŝanĝo ricevos ilin sur la unua paŝo, la dua paŝo trovos ĉiujn elementojn en ordo, tiel la vara volo preni nur 2n tempon.

Elekta speco

Ĉefa artikolo: Elekta speco

Selektada speco estas en-loko kompare speco. Ĝi havas ho (n ²) komplekseco, farante ĝin senutila sur grandaj lertaj, kaj ĝenerale plenumas malbonan ol la similaj adicia speco. Selektada varo konata pro ĝia simpleco, kaj ĝi ankaŭ havas agadajn avantaĝojn super pli komplikaj algoritmoj en certaj situacioj.
La algoritmo trovas la minimuman valoron, svopas ĝin kun la valoro en la unua pozicio, kaj ripetas tiujn paŝojn por la resto de la listo. Ĝi ne faras pli ol n svopoj, kaj tiel estas utilaj kie interŝanĝi estas tre multekosta.

Adicia speco

Ĉefa artikolo: Adicia speco

Adicia varo estas simpla ordigada algoritmo kiu estas relative efika por malgrandaj lertaj kaj precipe ordas lerte, kaj ofte estas uzata kiel parto de pli kompleksaj algoritmoj. Ĝi funkcias prenante elementoj el la listo unu post la alia kaj enmetante ilin en ilia ĝusta pozicio en nova orda listo. En tabeloj, la nova listo kaj la ceteraj elementoj povas dividi la tabelon la spaco, sed adicio estas peniga, postulanta ŝanĝiĝantaj ĉiuj sekvaj elementoj super la alia. Shell-speco (vidu sube) estas varianto de adicia varo kiu estas pli efika por pli grandaj listoj.

Shell-speco

Al Shell varo, malsama de bobela varo en kiu movas elementojn multnombrajn postenojn interŝanĝas

Ĉefa artikolo: Shell speco

Konka varo estis elpensita de Donald Shell en 1959. Ĝi plibonigas sur bobela varo kaj adicia varo por movi paneaj elementoj pli ol unu pozicio je tempo. Unu apliko povas esti priskribita kiel ripari la datumajn vicojn en du-dimensia tabelo kaj poste ordigi la kolumnojn de la tabelo uzante adicia varo.

Kombila speco

Ĉefa artikolo: Kombila speco

Kombila varo estas relative simpla algoritma ordigo origine desegnita de Włodzimierz Dobosiewicz en 1980. Poste estis retrovita kaj popularigita de Stephen Lacey kaj Richard Box kun artikolo ĉe Bajta Revuo publikigita en aprilo 1991. Kombila speco plibonigas la bobelan specon, kaj rivalaj algoritmoj kiel quicksort. La baza ideo estas forigi testudojn, aŭ malgrandaj valoroj proksime de la fino de la listo, kiel en bobela speco tiuj malrapida la ordiga malsupren terure. (Kunikloj, grandaj valoroj ĉirkaŭ la komenco de la listo, ne metas problemon en bobela varo)

Merge (kunfanda) speco

Ĉefa artikolo: Merge (kunfanda) speco

Kunfanda speco utiligas la facilecon de fandado jam ordo lertaj en nova ordo listo. Ĝi komenciĝas per komparo ĉiu du eroj (ekzemple, 1 kun 2, tiam 3 kun 4 ...) kaj interŝanĝas ilin se la unua venas post la dua. Ĝi tiam kunfandas ĉiujn ĉe la rezultantaj listoj due en listoj kvare, tiam kunfandas tiujn listojn kvare, kaj tiel plu; ĝis fine du listoj estas kunfanditaj en la fina orda listo. La algoritmoj priskribita ĉi tie, ĉi tiu estas la unua kiu grimpas bone al tre grandaj listoj, ĉar lia plej kurada tempo de malbona-kazo estas O (n log n). Kunfandi varon vidis relative freŝaj ondegoj en populareco pro praktikaj realigoj, estante uzita por la norma speca rutino en la programlingvoj kiel Perl, ^[12] Python (kiel timsort ^[13] ), kaj Javo (ankaŭ uzas timsort ekde JDK7 ^{[14 ]} ), inter aliaj. Kunfanda varo estis uzita en Java almenaŭ ekde 2000 en JDK1.3. ^[15] ^[16]

Heapsort

Ĉefa artikolo: Heapsort

Heapsort estas multe pli efika versio de selektada speco. Ĝi funkcias ankaŭ la determini la plej grandan (aŭ malgrandan) eron da listo, metante ke fine (aŭ komenco) de la listo, tiam daŭrigi kun la resto de la listo, sed plenumas tiun taskon efike uzante datumstrukturo nomata amaso, speciala tipo da duuma arbo. Iam la datumaj listoj estis portita al la amaso, la radika vertico estas garantiita al esti la plej granda (aŭ malgranda) ero. Kiam estas forigitaj kaj metis la finon de la listo, la havaĵo estas rearanĝitaj do la plej grandaj ceteraj eroj movas la radikon. Uzante la amaso, trovante la venonta plej granda ero prenas O (log n) tempo, anstataŭ O (n) por lineara scano kiel en simpla elekta varo. Ĉi tiu permesas Heapsort kuri en O (n log n) tempo, kaj tia estas ankaŭ la plej malbona kaza komplekseco.

quicksort

Ĉefa artikolo: quicksort

Quicksort estas dividu kaj regu algoritmon kiu fidas sur subdiska operacio: al subdiska tabelero nomas pivoton estas selektita. Ĉiuj elementoj pli malgranda ol la pivoto estas movita antaŭ ĝi kaj ĉiuj pli grandaj elementoj estas movita post tio. Ĉi tiu povas esti farita kompetente en lineara tempo kaj loke. La malpli grandan kaj pli granda Alsublistige estas poste rekursie ordo. Efika skribado de quicksort (kun loka particio) estas tipe malstabilaj varoj kaj iom kompleksa, sed estas inter la plej rapidaj klarigaj algoritmoj en praktiko. Kune kun lia modesta O (log n) spaca uzado, quicksort estas unu el la plej popularaj ordigadaj algoritmoj kaj estas disponebla en multaj normo bibliotekoj de programado. La plej kompleksa afero en quicksort elektas bonan pivoteron; konsekvence malriĉaj elektoj de pivotoj povas rezulti draste malrapida O(n ²) agado, se en ĉiu paŝo la mezo estas elektita kiel la pivoto tiam la algoritmo laboras en O (n log n). Trovi la mezalan tamen, estas O (n) operacias sur ne-ordaj lertaj kaj sekve exacts sian propran punon kun ordigi.

Rakonta speco

Ĉefa artikolo: rakonta speco

Rakonta varo estas aplikebla kiam ĉiu enigo estas sciata al aparteni apartan aron, S, eble. La algoritmo funkcias en O (|S| + n) tempo kaj O(|S |) memoro kie n estas la eniga longo. Ĝi funkcias per la kreado de entjera tabelo de amplekso |S| kaj uzante la i-a bin kalkuli la spritaĵoj de la i-a S-membro da enigo. Ĉiu enigo estas poste rakontis pliigante la valoron de lia responda bin. Poste, la kalkula tabelo ripetas tra aranĝi ĉiujn ordaj enigoj. Ĉi ordiga algoritmo ne povas ofte esti uzita ĉar S bezonas esti prudente malgranda por ke ĝi estu efika, sed la algoritmo estas ege rapidaj kaj pruvas grandan asimptotan konduton kiel n pliigas. Ĝi ankaŭ povas esti modifita havigas stabilan konduton.

Bucket-speco

Ĉefa artikolo: Bucket speco

Sitela speco estas dividu kaj regu ordigan algoritmon kiu ĝeneraligas rakonta speco de dispartiganta tabelo en finia nombro de siteloj. Ĉiu rubujo estas tiam ordo individue, ĉu uzante malsama ordiga algoritmo, aŭ rekursie aplikas la rubujan ordigadan algoritmon. Variado de ĉi metodo nomata sola buffered grafa varo estas pli rapida ol quicksort.^{[ citaĵo bezonata ]}
Pro la fakto ke balde speco devas uzi limigitan numeron da siteloj estas bone taŭga por esti uzata en datumaroj de limigita amplekso. Sitela speco estus neuzebla por datumoj kiuj havas multan variadon, kiel sociaj sekurecaj nombroj.

radiksa speco

Ĉefa artikolo: radiksa speco

Radiksa varo estas algoritmo kiu specas nombrojn per procesante individuaj ciferoj. N nombroj konsistas de k ciferoj ĉiu estas ordigitaj en O(n·k) tempo. Radiksa varo povas procesi ciferojn da ĉiu numero ĉu ekde la malplej signifa cifero (LSD) aŭ ekde la plej signifaj ciferoj (MSD). La LSD algoritmo unue specas la liston de la malplej signifa cifero konservante sian relativan ordon uzante stabila varo. Tiam specoj ilin per la sekvanta cifero, kaj tiel plu, de la malgrandaj signifas a plej signifajn, fini kun orda listo. Dum la LSD radiksa speco postulas la uzon de stabila varo, la MSD-radiksa speca algoritmo ne (krom stabila ordigado estas dezirata). Loke MSD radiksa varo estas ne stabila. Ĝi estas komuna por la algoritmo de kalkula speco por esti uzita interne el la baza varo. Hibrida ordigado alproksimiĝas, ekzemple uzante adicia speco por malgrandaj ujojn plibonigas rendimenton de radiksa speco signife.

Distribuada speco

Dissenda speco raportas ajnan ordigan algoritmon kie datumoj disdonas siajn enigojn al multnombraj interaj strukturoj kiuj estas tiam reprenitaj kaj metis sur la eligo. Ekzemple, ambaŭ rubuja speco kaj flashsort estas distribuo kiu bazas sur ordigaj algoritmoj.

Timsort

Ĉefa artikolo: Timsort

Timsort trovas kuras en la datumoj, kreas runs kun adicias specon se necese, kaj tiam uzas kunfandi specon krei la finan ordon liston. Ĝi havas la samajn kompleksecojn (O (n log n)) en la mezumo kaj plej malbonaj kazoj, sed kun antaŭ-ordaj datumoj iras malsupren al O(n).

Memoraj uzadaj ŝablonoj kaj indicaj ordigadoj

Kiam la grandeco de la tabelo esti ordo enfokusigas aŭ superas la disponeblan primaran memoron, tiel ke (multe pli malrapida) disko aŭ interŝanĝa spaco devas esti uzita, la memora uzada mastro de ordiga algoritmo igas gravan, kaj algoritmo kiu povus esti sufiĉe efika kiam la tabelo persvadis facile en RAM fariĝas nepraktikan. En ĉi tiu scenaro, la suma nombro de komparoj iĝas (relative) malpli grava, kaj la nombro da fojaj sekcioj de memoro devas esti kopiita aŭ interŝanĝis al kaj de la disko povas regi la funkciadon karakterizaĵoj de algoritmo. Tiel, la kvanto de paŝoj kaj la lokaligo de komparoj povas esti pli grava ol la kruda numero de komparoj, ekde komparoj de proksimaj elementoj unu al la alia okazos je rapido de sistema busa (aŭ, kun caching, eĉ je CPU-rapido), kiu, kompare al diska rapido, estas virtuale samtempe.
Ekzemple, la populara rekursie quicksort algoritmo provizas sufiĉe racian agadon kun adekvata RAM, sed pro la rekursie maniero kiu kopias partojn de la tabelo ĝi iĝas multe malpli oportunaj kiam la tabelo ne havas RAM-memoron, ĉar ĝi povas kaŭzi kelkajn malrapidajn kopiojn aŭ movadajn operaciojna al kaj el disko. En tiu scenaro, alia algoritmo povas esti preferinda eĉ se ĝi postulas pli tutecaj komparoj.
Unu maniero labori ĉirkaŭ ĉi problemo, kiu bone funkcias kiam kompleksaj registroj (kiel en rilata datumbazo) estas ordo de relative malgranda ŝlosila kampo, estas krei indekson en la tabelo kaj poste ordigi la indekson, anstataŭ la tuta tabelo. (orda versio de la tuta tabelo povas tiam esti produktita per unu paŝo, legante indekso, sed ofte eĉ tio estas nenecesa, kiel havanta la orda indico estas adekvata.) Pro la indekso estas multe pli malgranda ol la tuta tabelo, ĝi eble konformas bone en la memoro kie la tuta tabelo ne, efektive forigi la disko-interŝanĝanta problemo. Ĉi tiu proceduro estas iam nomita "etikeda speco". ^[17]
Alia tekniko por superi la memoro-grandecan problemon estas kombini du algoritmojn maniere kiu prenas avantaĝojn de la forto de ĉiu plibonigi entutan rendimenton. Ekzemple, la tabelo povus esti subdividita enen pecoj da grandeco kiu persvadis facile en RAM (diru, kelkaj mil eroj), la pecaj ordoj uzante kompetenta algoritmo (kiel quicksort aŭ heapsort ), kaj la rezultoj kunfandis kiel po mergesort. Tio estas malpli efika ol simple fari mergesort en la unua loko, sed ĝi postulas malpli fizika RAM (esti praktika) ol plena quicksort sur la tuta tabelo.
Teknikoj povas ankaŭ esti kombinita. Por ordigi tre grandaj aroj da datumoj kiuj ege superas sisteman memoron, eĉ la indekso eble bezonas esti ordo uzante algoritmon aŭ kombino de algoritmoj desegnitaj por plenumi prudente kun virtuala memoro, kio estas, redukti la kvanton de interŝanĝo bezonata.
Iuj aliaj ordigadah algoritmoj ankaŭ, tio estas, novaj amikaj specah algoritmoj, relativa disigo aŭ konkateneca speco, ktp

ne-efikeca/humura specoj

Iuj algoritmoj estas ekstreme malrapida kompare al tiuj diskutitaj supre, kiel la Bogosort $O (n \ cdot n!)$ kaj la Stooge speco $O (n ^ {2,7})$ .

Vidu ankaŭ

Referencoj

Ĉi tiu artikolo inkludas listo da referencoj, sed liaj fontoj restas neklara ĉar ĝi havas nesufiĉan inlinia citoj. Bonvolu helpu al plibonigi ĉi tiun artikolon per enkonduki pli preciza citas. (septembro 2009)

^ Demuth, H. Elektronika Datumoj Granulometría. PhD tezo, Universitato Stanford, 1956.
^ http://www.sgi.com/tech/stl/stable_sort.html
^ http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381
^ http://www.algolist.net/Algorithms/Sorting/Selection_sort
^ http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp
^ http://www.springerlink.com/content/d7348168624070v7/
^ ^{a b c} Cormen-a, Thomas H. ; _Leiserson_, Karlo E. , _Rivest_, _Ronald_ L. , Stein, Clifford (2001) [1990]. Enkonduko al Algoritmoj (2nd ed.). _MIT_ Premi kaj _McGraw_-Monteto. ISBN 0-262-03293-7 .
^ ^{a b} Goodrich, Michael T. ; Tamassia, Roberto (2002). "4,5 Bucket-Varo kaj radix-Ordigi". Algoritmo Dezajno: Fundamentoj, Analitiko, kaj Interreto Ekzemploj. John Wiley & Sons. pp 241-243.
^ Y. Han. Determina ordigado en $\ Mathcal {O} \ left ({n \ log \ log n} \ right)$ tempo kaj lineara spaco. Paperoj de la tridek-kvara jara _ACM_ simpozio sur Teorio de komputanta, Montrealo, Kebekio, Kanado, 2002, p.602-608.
^ ro Thorup . Hazardigita Granulometría en $\ Mathcal {O} \ left ({n \ log \ log n} \ right)$ Tempo kaj Spaco Linearaj Uzanta Aldono, Shift kaj Bito-saĝa Bulea Operacioj. Ĵurnalo de Algoritmoj, Volumo 42, Numero 2, februaro 2002, pp 205-230 (26)
^ han, Y. kaj Thorup, M. 2002. Entjero Granulometría en $\ Mathcal {O} \ left ({n \ sqrt {\ log \ log n}} \ right)$ Atendis Tempo kaj Linearaj Spaco. En Aktoj de la 43-simpozio Fundamentoj de Komputila Scienco (Novembro 16-19, 2002). FOCS. IEEE Computer Socio, Vaŝingtono, DC, 135-144.
^ Perl speco dokumentado
^ Tim Peters originala priskribo de timsort
^ http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79
^ Kunfandi varo en Java 1.3 , Suno.
^ Java 1.3 vivas ekde 2000
^ Difino de "etikedo speco" laŭ PC Magazine

DE Knuth , La Arto de Komputila Programado , Volumeno 3: Ordigo kaj Serĉado.

Datumaj Struturoj

terça-feira, 27 de novembro de 2012