Víxlunarröðun

Víxlunarröðun eða bóluröðun^{[heimild vantar]} er einfalt röðunarreiknirit að stærðargráðu n², í sínu einfaldasta formi virkar það með því að fara $n\times 2$ sinnum yfir fylki af stærð n og víxla stök sem eru stærri en næsta stak á undan, en röðunin dregur einmitt nafn sitt af „víxluninni“.

Breyti Víxlunarröðun breytt lit

Vegna einfaldleika reikniritsins er það oft fyrsta reikniritið sem kennt er í tölvunarfræði.

Gagnsemi

Víxlunarröðun er afar einfalt reiknirit en nær gagnslaust sökum flækjustigs af stærðargráðu O(n²).

Útfærsla

Þetta C99 fall raðar fylkinu tolur af stærð staerd með víxlunarröðun, gert er ráð fyrir að búið sé að skilgreina fallið vixla, sem tekur tvö stök og gefur þeim gildi hvors annars:

void vixla(int *tala1, int *tala2)
{       
    const int timabundin_tala = *tala1;
    *tala1 = *tala2;
    *tala2 = timabundin_tala;
}

Einfaldasta útgáfa víxlunarröðunar:

void bubblesort(int tolur[], int staerd)
{
    for (int i = 0; i < staerd; ++i) 
        for (int j = 0; j < staerd; ++j) 
            if (tolur[j] > tolur[j + 1])
                vixla(&tolur[j], &tolur[j + 1]);
}

Víxlunarröðunin betrumbætt

Ef farið er yfir fylkið og ekki þarf að skipta út neinum stökum er það tryggt að ekki þarf að fara yfir það aftur þar sem það er þegar raðað, í besta tilfelli þarf þá að gera n samanburði fyrir fylki af stærð n (ef fylkið er þegar raðað), gert er ráð fyrir að búið sé að skilgreina fallið vixla eins og áður:

#include <stdbool.h>

void vixlunarrodun(int tolur[], int staerd)
{
    bool radad;
    for (int i = 0; i < staerd; ++i) {
        radad = true;
        for (int j = 0; j < staerd; ++j)
            if (tolur[j] > tolur[j + 1]) {
                vixla(&tolur[j], &tolur[j + 1]);
                radad = false;
            }
        if (radad) break;
    }
}

Eftir að búið er að fara yfir fylkið einu sinni er tryggt að stærsta stak þess er komið aftast í fylkið, þegar búið er að fara yfir það tvisvar er tryggt að tvö efstu stökin eru komin efst í það o.s.f., þar með er hægt að flýta reikniritinu með því að sleppa því að bera saman þau stök sem vitað er að eru þegar röðuð:

void vixlunarrodun(int tolur[], int staerd)
{
    int staerd2 = staerd;

    for (int i = 0; i < staerd; ++i) {
        for (int j = 0; j < staerd2; ++j)
            if (tolur[j] > tolur[j + 1])
                vixla(&tolur[j], &tolur[j + 1]);

        --staerd2;
    }
}

að lokum er svo hægt að sameina þessar tvær aðferðir:

#include <stdbool.h>

void vixlunarrodun(int tolur[], const int staerd)
{
    bool radad;
    int staerd2 = staerd;

    for (int i = 0; i < staerd; ++i) {
        radad = true;

        for (int j = 0; j < staerd2; ++j)
            if (tolur[j] > tolur[j + 1]) {
                vixla(&tolur[j], &tolur[j + 1]);
                radad = false;
            }
        if (radad) break;
        --size2;
    }
}