Birləşdirməli nizamlama

Birləşdirməli nizamlama(ing. merge sort, ru. сортировка слиянием) -bir neçə çeşidlənən (giriş) siyahının bir (çıxış) siyahıda birləşdirilməsindən ibarət çeşidləmə üsulu. Birinci siyahının ilk elementi götürülür və ikinci siyahının birinci elementi ilə müqayisə olunur; seçim edildikdən sonra elementin seçildiyi siyahının başlanğıcının göstəricisi növbəti elementə keçir və beləliklə, siyahılardan birinin sonunadək hərəkət edilir. Bu metod bir neçə siyahıya tətbiq edilə bilər. Maraqlıdır ki, iş yalnız siyahıların birinci elementləri ilə aparılır. Birləşdirməli çeşidləmə alqoritmi 1945-ci ildə Con fon Neyman tərəfindən icad olunub.

Birləşdirməklə nizamlama alqoritmi Con fon Neyman tərəfindən 1945 -ci ildə ixtira edilmiş, parçala və idarə etmə mexanizminə əsaslanan nizamlama alqoritmidir. Alqoritm ən pis, ən yaxşı və orta halda eyni sayda əməliyyat yerinə yetirir, O(n log n). Ən pis halda tutduğu yer isə O(n).

Alqoritm

Birləşdirməklə nizamlama alqoritminin animasiyası. Sıralanacaq elementlər nöqtələrlə təsvir olunub.

Bir qayda olaraq birləşdirməklə nizamlama alqoritmi aşağıdakı kimi işləyir:

1. Sıralanmamış siyahını hər birində bir element olmaqla n alt-siyahıya böl. (1 elementdən ibarət olan siyahı nizamlanmış hesab edilir).
2. Bir alt-siyahı qalanadək təkrar olaraq alt-siyahıları sıralanmış qaydada birləşdir. Bu nizamlanmış siyahı olacaq. 

Yuxarıdan-aşağı implementasiya

Nümunə C kodu birləşdirməklə nizamlama alqoritminin yuxarıdan-aşağı implementasiyanı istifadə etməklə siyahını alt-siyahılara bölür (alt-siyahının ölçüsü 1 olanadək), sonra bu alt-siyahıları nizamlanmış siyahı yaratmaq üçün birləşdirir.

// Massiv A[] nizamlanmalıdır; massiv B[] işçi massivdir.
TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // A[] massivini B[]massivinə kopyala
    TopDownSplitMerge(B, 0, n, A);   // elementləri B[] massivindən A[] massivinə nizamla
}

// iBegin massivə daxildir; iEnd isə daxil deyil (A[iEnd] çoxluğa daxil deyil).
TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if(iEnd - iBegin < 2)                       // əgər size == 1
        return;                                 // bunu nizamlanmış fərz et
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = orta nöqtə
    // rekursiv olaraq hər iki siyahını A[] massivindən B[] massivinə nizamla
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sol siyahını nizamla
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sağ siyahını nizamla
    // nəticədə alınan siyahıları B[]massivindən A[] massivinə birləşdir
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Sol siyahı A[ iBegin:iMiddle-1].
// Sağ siyahı A[iMiddle:iEnd-1   ].
// Nəticə B[ iBegin:iEnd-1   ].
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
    
    // Sol və ya sağ siyahılarda element olduqca...
    for (k = iBegin; k < iEnd; k++) {
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

CopyArray(A[], iBegin, iEnd, B[])
{
    for(k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

Aşağıdan-yuxarı implementasiya

Nümunə C kodu birləşdirməklə nizamlama alqoritminin aşağıdan-yuxarı implementasiyanı istifadə etməklə siyahını nizamlayır:

// massiv A[] nizamlanmalıdır, massiv B[] işçi massivdir.
void BottomUpMergeSort(A[], B[], n)
{
    for (width = 1; width < n; width = 2 * width)
    {
        for (i = 0; i < n; i = i + 2 * width)
        {
            // İki siyahını birləşdir: 
            //A[i:i+width-1] və A[i+width:i+2*width-1]: B[] massivinə
            // və ya A[i:n-1]-i B[] massivinə kopyala  ( if(i+width >= n) )

            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // B massivi uzunluğu 2*width olan siyahılardan ibarətdir 
        // Növbəti iterasiya üçün B massivini A massivinə kopyala.
        // Daha səmərəli implementasiya A və B massivlərinin rolunu dəyişmək olar 
        CopyArray(B, A, n);
        // indi A massivi uzunluğu 2*width olan siyahılarldan ibarədir  
    }
}

// Sol siyahı A[iLeft :iRight-1].
// Sağ siyahı A[iRight:iEnd-1  ].
BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // Sol və ya sağ siyahılarda element olduqca...
    for (k = iLeft; k < iEnd; k++) {
       
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for(i = 0; i < n; i++)
        A[i] = B[i];
}

Analiz

Rekursiv birləşdirməklə nizamlama alqoritmi 7 tam ədəddən ibarət olan massivi nizamlamaq üçün istifadə olunmuşdur. (yuxarıdan-aşağı implementasiya)

Ən pis halda (worst case) birləşdirməklə nizamlama alqoritmi sürətli nizamlama alqoritminin ortalama halından (average case) 39% az müqayisə əməliyyatı yerinə yetirir. Birləşdirməklə nizamlama alqoritminin ən pis hal üçün mürəkkəbliyi: O(n log n) - bu sürətli nizamlama alqoritminin ən yaxşı (best case) hal üçün mürəkkəbliyinə bərabərdir.

Ədəbiyyat

• İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.