Rapida ordigo

En angla kaj en kelkaj lingvoj Quicksort kaj esperante „rapida ordigo“ estas unu el la plej rapidaj kutimaj ordigaj algoritmoj bazitaj sur komparado de elementoj. Ĝia averaĝa tempa komplekseco estas la plej bona por algoritmoj de la grupo (O(N log N)), en la plej malbona kazo (kiun eblas kutime eviti) estas ĝia tempa komplekseco O(N²). Plia avantaĝo de la algoritmo estas ĝia simpleco.

Quicksort aplikata al kelkaj hazardaj numeroj. Horizontalaj valoroj estas pivotoj.

Siro Charles Antony Richard Hoare malkovris ĝin en 1961.

La algoritmo

Algoritmo aplikata al kelkaj hazardaj numeroj. Markitaj valoroj estas pivotoj, la bluaj estas malpli- aŭ samvaloraj kaj la ruĝaj estas plivaloraj.

La baza ideo de Quicksort estas divido de ordigata vico de numeroj al du proksimume samaj partoj (Quicksort apartenas al algoritmoj de tipo "dividu kaj regu"). En unu parto estas numeroj pli- kaj en la dua malplivaloraj ol iu elektita valoro (nomata kiel pivoto). Se tiu ĉi valoro estas bone elektita, la du partoj estas proksimume same grandaj. Se estos ambaŭ partoj memstare ordigitaj, ankaŭ la tuta tabelo estas ordigita. La du partoj poste estas rikure ordigataj per la sama procedo, kio ne signifas, ke realigo devas ankaŭ uzi rikuron.

Elekto de pivoto

La plej granda problemo de la tuta algoritmo estas elekto de pivoto. Se oni sucesas elekti numeron proksime al mediano de ordigata parto de tabelo, la algoritmo estas vere tre rapida. En mala kazo la tempo de funkciado plilongiĝas kaj en ekstrema kazo tempa komplekseco estas O(N²). Natura metodo por ekhavi pivoton estas elekto de mediano. Serĉado de mediano (kaj ĝenerale k-a elemento) en vico funkcias en lineara tempo rilate al nombro de elementoj. Tiel oni ekhavos komplesecon de Quicksort O(N log N) en plej malbona kazo. Tamen tiu ĉi realigo ne estas tro rapida pro grandaj konstantoj kaŝitaj en la O-notacio. Pro tio ekzistas granda nombro de alternativaj manieroj, kiuj strebas pri efektiva elekto de pivoto plej proksime al mediano kiel eblas. Jene estas listo de kelkaj tiaj metodoj:

• Unua elemento – eventuale ajna alia fiksa pozicio. (Fiksa elekto de la unua elemento estas ege neefika en parte ordigitaj aroj.)
• Hazarda elemento – ofte uzata metodo. Averaĝo super ĉiuj datumoj estas O(N log N), ĉi tie la averaĝo fariĝas trans ĉiuj eblaj elektoj de pivotoj (distribuita kontinue). La plej malbona kazo restas O(N²), ĉar por ĉiuj datumoj povas hazardo aŭ Ege Inteligenta Kontraŭulo elekti sisteme nebona pivoto, ekz. dua plej granda numero. Praktike plej ofte ne atingeblas generilo de vere hazardaj numeroj, pro tio oni uzas pseŭdohazardan elekton.
• Metodo de mediano de tri – aŭ kvin aŭ alia nombro de elementoj. Per pseŭdohazarda algoritmo (oni ankaŭ uzas fiksan pozicion, tipe la unua, meza aŭ la lasta) oni elektas kelkajn elementojn el la aro, el kiuj oni elektas medianon kaj tiu estas uzita kiel pivoto.

Se estus garantiata, ke pivoton oni elektas ĉiam el 98 % elementoj meze kaj ne el 1 % en iu flanko, la algoritmo devus havi la plej malbonan asimptotian kompleksecon O(N log N), kvankam kun iom pli granda konstanto en O-notacio.

Praktikaj spertoj kaj testoj montras, ke super pseŭdohazardaj aŭ realaj datumoj Quicksort estas plej rapida el ĉiuj ĝeneralaj ordigaj algoritmoj (do ankaŭ pli rapidaj ol Heapsort kaj Mergesort, kiuj estas formale pli rapidaj). Rapideco de Quicksort ne estas garantiata por ĉiuj enigoj. Maksimuma tempa komplekseco O(N²) diskvalifikas Quicksort-on por kritikaj aplikoj.

Kodo de la algoritmo en Paskalo

procedure quicksort(l, r: integer);
var
    i, j, pivot, pom: integer;
begin
    i := l; j := r;
    pivot := akt[(l + r) div 2];
    repeat
        while (i < r) and (akt[i] < pivot) do i := i + 1;
        while (j > l) and (pivot < akt[j]) do j := j - 1;
        if i <= j then
        begin
            pom := akt[i];
            akt[i] := akt[j];
            akt[j] := pom;
            i := i + 1;
            j := j - 1;
       end;
    until i > j;
    if j > l then quicksort(l, j);
    if i < r then quicksort(i, r)
end;

Kodo de la algoritmo en programlingvo C

void quicksort(int array[], int left_begin, int right_begin)
{
    int pivot = array[(left_begin + right_begin) / 2];
    int left_index, right_index, pom;
    left_index = left_begin;
    right_index = right_begin;
    do {
        while (array[left_index] < pivot && left_index < right_begin)
            left_index++;
        while (array[right_index] > pivot && right_index > left_begin)
            right_index--;

        if (left_index <= right_index) {
            pom = array[left_index];
            array[left_index++] = array[right_index];
            array[right_index--] = pom;
        }
    } while (left_index < right_index);

    if (right_index > left_begin) quicksort(array, left_begin, right_index);
    if (left_index < right_begin) quicksort(array, left_index, right_begin);
}

Referencoj

En tiu ĉi artikolo estas uzita traduko de teksto el la artikolo Quicksort en la ĉeĥa Vikipedio.

Literaturo

Wirth, N.: Algoritmy a štruktúry údajov, Alfa, Bratislava, 1989

Vidu ankaŭ

• Ordiga algoritmo