Bóluröðun

Úr Wikipediu, frjálsa alfræðiritinu

Bóluröðun er einfalt röðunarreiknirit að stærðargráðu n², í sínu einfaldasta formi virkar það með því að fara n · 2 sinnum yfir fylki af stærð n og færa stök sem eru stærri en næsta stak á undan „upp“ í fylkinu, en röðunin dregur einmitt nafn sitt af því að stór stök „fljóta upp“ í fylkinu eins og loftbólur.

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

[breyta] Útfærsla

Þetta C99 fall raðar fylkinu num af stærð size með bóluröðun, gert er ráð fyrir að búið sé að skilgreina fallið swap, sem tekur tvö stök og gefur þeim gildi hvors annars:

void swap(int *a, int *b)
{       
        const int c = *a;
        *a = *b;
        *b = c;
}

Einfaldasta útgáfa bóluröðunar:

void bubblesort(int num[], int size)
{
        for (int i = 0; i < size; ++i) 
                for (int j = 0; j < size; ++j) 
                        if (num[j] > num[j + 1])
                                swap(&num[j], &num[j + 1]);
}

[breyta] Að hraða bóluröðun

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ð swap eins og áður:

#include <stdbool.h>

void bubblesort(int num[], int size)
{
        bool sorted;

        for (int i = 0; i < size; ++i) {
                sorted = true;

                for (int j = 0; j < size; ++j)
                        if (num[j] > num[j + 1]) {
                                swap(&num[j], &num[j + 1]);
                                sorted = false;
                        }

                if (sorted)
                        break;
        }
}

Eftir að búið er að fara yfir fylkið einusunni 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 bubblesort(int num[], int size)
{
        int size2 = size;

        for (int i = 0; i < size; ++i) {
                for (int j = 0; j < size2; ++j)
                        if (num[j] > num[j + 1])
                                swap(&num[j], &num[j + 1]);

                --size2;
        }
}

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

#include <stdbool.h>

void bubblesort(int num[], const int size)
{
        bool sorted;
        int size2 = size;

        for (int i = 0; i < size; ++i) {
                sorted = true;

                for (int j = 0; j < size2; ++j)
                        if (num[j] > num[j + 1]) {
                                swap(&num[j], &num[j + 1]);
                                sorted = false;
                        }

                if (sorted)
                        break;
                --size2;
        }
}