Приказ рада алгоритама сортирања¶

Одлуке у вези са концептом апликације¶

Да би рад појединих алгоритама сортирања могао да се испрати погледом и разуме, важно је да се алгоритми не извршавају сувише брзо. Идеално, алгоритми треба да застану после сваке размене елемената низа и да сачекају да се прикаже ново стање. Ово застајкивање алгоритама може да се постигне помоћу метода Thread.Sleep, али ако се апликација извршава у једној нити, то није најбоље решење. Наиме, док апликација чека задати број милисекунди, она не може да реагује на акције корисника, па је мање одзивна и оставља утисак да нешто није у реду са програмом. Употреба више нити би отклонила овај проблем, али такво решење је непотребно сложено за оно што желимо да постигнемо у овом примеру. Једноставнија идеја је да на догађај тајмера извршимо по један корак сваког од изабраних алгоритама сортирања и освежимо приказ. Тиме апликација између узастопних догађаја тајмера остаје спремна да по потреби реагује на остале догађаје.

Постоје различити начини да се за све изабране алгоритме сортирања изврши по један корак. Један начин је да се алгоритми сортирања напишу на специфичан начин, тако да се при једном позиву одређеног метода извршава само један корак алгоритма. Узмимо за пример познати алгоритам Bubble Sort, који као целина изгледа овако:

for (iSortedFrom = a.Length - 1; iSortedFrom > 0; iSortedFrom--)
    for (iBubble = 0; iBubble < iSortedFrom; iBubble++)
        if (a[iBubble] > a[iBubble + 1])
            Swap(iBubble, iBubble + 1);

За овај алгоритам сортирања би могао да се напише метод који извршава само један корак тог алгоритма, односно једну итерацију унутрашње петље. У том случају, бројачке променљиве петљи би морале да постану поља класе, како би метод при следећем позиву могао да настави поступак тамо где је стао. У случају овакве организације, метод би могао да изгледа овако:

private int iSortedFrom;
private int iBubble;
private bool finished;

public void DoSortingStep()
{
    if (finished)
        return;

    if (iBubble == iSortedFrom - 1)
    {
        iBubble = 0;
        iSortedFrom--;
        if (iSortedFrom <= 1)
        {
            finished = true;
            return;
        }
    }

    if (a[iBubble] > a[iBubble + 1])
    {
        Swap(iBubble, iBubble + 1);
    }
    iBubble++;
}

Видимо да се чак и код овако једноставног алгоритма поступак прилично закомпликовао. Можемо да претпоставимо да би код сложенијих алгоритама, а поготово код оних рекурзивних, издвајање једног корака у посебан метод било знатно сложеније.

На срећу, постоји једноставно решење које нам омогућава да алгоритме записане на уобичајени начин ипак извршавамо корак по корак, враћајући контролу апликацији после сваког корака, како би она могла да одговори на евентуалне догађаје. Довољно је да метод напишемо тако да не враћа void него нпр. IEnumerable<int>. При томе нам уопште нису битне враћене вредности које чине колекцију, већ само чињеница да после сваке враћене вредности можемо да паузирамо извршавање метода враћајући контролу, а да касније наставимо извршавање метода тачно тамо где је заустављен. Семантика наредбе yield нам омогућава управо такво извршавање метода DoSortingStep(). Како је сама колекција коју враћа метод небитна, можемо као елементе колекције да враћамо нпр. нуле, јер се сама колекција и не користи на страни која позива метод DoSortingStep. Ево како би метод могао да се напише по овој идеји:

public IEnumerable<int> DoSortingStep()
{
    for (iSortedFrom = a.Length - 1; iSortedFrom > 0; iSortedFrom--)
        for (iBubble = 0; iBubble < iSortedFrom; iBubble++)
            if (a[iBubble] > a[iBubble + 1])
            {
                Swap(iBubble, iBubble + 1);
                yield return 0;
            }

    finished = true;
}

Организација класа¶

Метод DoSortingStep ће за сваки алгоритам сортирања да изгледа другачије, па је природно да уведемо заједничку базну апстрактну класу Algorithm, у којој ће овај метод да буде апстрактан. Програм би могао да се напише и тако да ово буде једини апстрактан метод, јер тренутно стање низа код сваког алгоритма може да се прикаже истим методом (различити су само подаци, попут вредности у низу, боје стубића, назива алгоритма и слично). Ми смо у приказ додали и исцртавање хоризонталних црних правоугаоника испод графикона који представља низ. Ови правоугаоници су различити за сваки алгоритам и помажу да се боље разуме и прати рад алгоритма.

Ови црни правоугаоници сами по себи не захтевају да се приказивање реализује као нови апстрактан метод. Могуће је, на пример, да се у базној класи дефинише заштићена листа правоугаоника, или података који дефинишу те правоугаонике, а да се у методу DoSortingStep листа ажурира на начин који одговара конкретном алгоритму. За такво решење се нисмо одлучили јер се њиме „прља” алгоритам сортирања, који би онда радио и нешто што нема везе са сортирањем (него само са приказом), а то цео програм чини мање јасним.

У нашем решењу, све наредбе за исцртавање су смештене у заштићени метод базне класе, али је остављен и апстрактан јавни метод Display. Тиме је омогућено да се из сваке од изведених класа које представљају конкретне алгоритме, позове заједнички метод за приказ са другачијом листом правоугаоника.

Ево како изгледа базна класа Algorithm.

Класе изведене из класе Algorithm су све веома кратке и међусобно сличне. На пример, класа BubbleSort изгледа овако:

Остале класе које представљају конкретне алгоритме можете да видите кликом на одговарајуће дугме.

Поред класа које представљају алгоритме сортирања, потребна је још и класа форме. У овом примеру, ни она није нарочито сложена – сви методи за обраду догађаја су веома кратки.

Ако желите да испробате апликацију, потребно је да урадите следеће:

• креирајте нови пројекат типа Windows Forms App и назовите га SortingAlgorithms,

• додајте у пројекат фајлове са класама које представљају алгоритме сортирања (базна и шест изведених класа) и копирајте у њих кôд који је дат горе,

• прегазите кôд фајла Form1.cs кодом датим непосредно изнад,

• прегазите кôд фајла Form1.Designer.cs кодом датим у наставку.