Біріктіру сұрыптау алгоритмі

алгоритм, сортировка слиянием, Merge Sort Algorithm, сортировка

Біріктіру сұрыптауы – компьютерлік бағдарламалаудағы бөлу және жеңу алгоритмінің бір түрі. Бұл ең танымал сұрыптау алгоритмдерінің бірі және рекурсивті алгоритмдерді құруда сенімділікті арттырудың тамаша тәсілі.

Бөл және билей бер# стратегиясы

«Бөл және жең» әдісін қолдана отырып, біз мәселені ішкі тапсырмаларға бөлеміз. Әрбір ішкі мәселенің шешімі дайын болғанда, біз негізгі мәселені шешу үшін ішкі есептердегі нәтижелерді «біріктіреміз».

Бізге A массивін сұрыптау қажет болды делік. Ішкі тапсырма осы массивтің p индексінен басталып, A[p..r] ретінде белгіленген r индексімен аяқталатын ішкі бөлімін сұрыптау болады.

Бөліс

Егер q p және r арасындағы аралық нүкте болса, онда A[p..r] ішкі массивін екі A[p..q] және A[q + 1, r] массивтеріне бөлуге болады.

Меншігі

Жаулап алу қадамында біз A[p..q] және A[q + 1, r] ішкі массивтерін де сұрыптауға тырысамыз. Егер біз әлі негізгі жағдайға жетпесек, осы екі ішкі массивтерді қайта бөліп, оларды сұрыптауға тырысамыз.

Комбайн

Жаулап алушы қадам негізгі қадамға жеткенде және A[p..r] массиві үшін екі сұрыпталған ішкі массивтер A[p..q] және A[q + 1, r] алынғанда, біз A сұрыпталған массивін жасай отырып, нәтижелерді біріктіреміз. A[p..q] және A[q + 1, r] сұрыпталған екі ішкі массивтің [p. .r]

Сұрыптау алгоритмін біріктіру

MergeSort функциясы біз 1 өлшемді ішкі жиым бойынша MergeSort әрекетін орындауға тырысатын кезеңге жеткенше алапты қайта-қайта екі жартыға бөледі, яғни. p == r.
Осыдан кейін біріктіру функциясы іске қосылады, ол сұрыпталған массивтерді бүкіл массив біріктірілгенше үлкенірек массивтерге біріктіреді.

MergeSort(A, p, r)
    If p > r 
        return;
    q = (p+r)/2;
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

Бүкіл массивді сұрыптау үшін MergeSort(A, 0, length(A)-1) шақыру керек.
Төмендегі суретте көрсетілгендей, біріктіру сұрыптау алгоритмі 1 элементі бар массивтің негізгі регистріне жеткенше алапты рекурсивті түрде екі жартыға бөледі. Содан кейін біріктіру функциясы сұрыпталған ішкі массивтерді таңдайды және бүкіл массивті біртіндеп сұрыптау үшін оларды біріктіреді.

Біріктіру сұрыптау біріктіру қадамы

Әрбір рекурсивті алгоритм негізгі регистрге және негізгі регистрлердің нәтижелерін біріктіру мүмкіндігіне байланысты. біріктіру сұрыптауы ерекшелік емес. Алгоритмнің ең маңызды бөлігі – «біріктіру» қадамы.

Біріктіру қадамы бір үлкен сұрыпталған тізімді (массив) жасау үшін екі сұрыпталған тізімді (массивтерді) біріктірудің қарапайым мәселесінің шешімі болып табылады.

Алгоритм үш көрсеткішті қолдайды, біреуі екі массивтің әрқайсысы үшін және біреуі соңғы сұрыпталған массивтің ағымдағы индексін сақтау үшін.

Достигли ли мы конца какого-либо из массивов?
    Нет:
        Сравните текущие элементы обоих массивов
        Скопируйте меньший элемент в отсортированный массив
        Переместить указатель на элемент, содержащий меньший элемент
    Да:
        Скопировать все оставшиеся элементы непустого массива

Екінші массивте басқа элементтер қалмағандықтан және екі массив де іске қосу кезінде сұрыпталғанын білеміз, біз қалған элементтерді бірінші массивтен тікелей көшіре аламыз.

Біріктіру алгоритмі үшін код жазу

Жоғарыда сипатталған біріктіру қадамы мен біріктіру сұрыптауы үшін қолданатын қадам арасындағы елеулі айырмашылық біріктіру функциясы тек дәйекті ішкі массивтерде орындалады.

Сондықтан бізге тек массив, бірінші орын, бірінші ішкі жиымның соңғы индексі (екінші бағыныңқы жиымның бірінші индексін есептей аламыз) және екінші ішкі жиымның соңғы индексі қажет.

Біздің міндетіміз сұрыпталған A[p..r] массивін жасау үшін A[p..q] және A[q + 1..r] екі ішкі массивтерін біріктіру болып табылады. Осылайша, A, p, q және r функциясы үшін кіріс деректері

Біріктіру функциясы келесідей жұмыс істейді:

1. L ← A [p..q] және M ← A [q + 1..r] ішкі массивтерінің көшірмелерін жасаңыз.
2. i, j және k үш көрсеткішті жасаңыз
3. i 1-ден бастап ағымдағы L индексін сақтайды
4. j 1-ден басталатын M ағымдағы индексін сақтайды
5. k p бастап A [p..q] ағымдағы индексін сақтайды
6. L немесе M соңына жеткенше, L және M элементтерінің ішінен үлкенін таңдап, оларды A[p..q] ішіндегі дұрыс орынға орналастырыңыз.
7. L немесе M элементтеріндегі элементтер таусылғанда, қалған элементтерді алып, A [p..q] -ге қойыңыз.

Кодта ол келесідей болады:

void merge(int A[], int p, int q, int r)
{
    /* Создание L ← A[p..q] и M ← A[q+1..r] */
    int n1 = q - p + 1;
    int n2 =  r - q;

    int L[n1], M[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        M[j] = A[q + 1 + j];

    /* Поддержание текущего индекса вложенных массивов и основного массива */
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 


    /* Пока мы не достигнем конца L или M, выбираем большее из элементов L и M и помещаем их в правильное положение в точке A [p..r]*/
    while (i < n1 && j < n2)
    {
        if (L[i] <= M[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    /* Когда у нас кончаются элементы в L или M, возьмите оставшиеся элементы и поместите в A [p..r]*/
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Функцияны қадам бойынша біріктіру

Бұл функцияда көп әрекет бар, сондықтан оның қалай жұмыс істейтінін көру үшін мысалды қарастырайық.

A[0..8] массивінде A[1..5] және A[6..7] сұрыпталған екі ішкі массив бар. Біріктіру функциясы екі массивті қалай біріктіретінін көрейік.

void merge(int A[], int p = 1, int q = 4, int 6)
{

1-қадам. Сұрыптау үшін ішкі массивтердің көшірмелерін жасаңыз

 /* Создание L ← A[p..q] и M ← A[q+1..r] */
    n1 = 4 - 1 + 1 = 4;
    n2 =  6 - 4 = 2;

    int L[4], M[2];

    for (i = 0; i < 4; i++)
        L[i] = A[p + i];
    /* L[0,1,2,3] = A[1,2,3,4] = [1,5,10,12] */

    for (j = 0; j < 2; j++)
        M[j] = A[q + 1 + j];
    /* M[0,1,2,3] = A[5,6] = [6,9]

2-қадам: Ішкі массивтердің және негізгі массивтің ағымдағы индексін сақтау

 int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 

3-қадам: L немесе M соңына жеткенше, L және M элементтерінің ішінен үлкені таңдалады және A нүктесінде дұрыс орынға орналастырылады [p..r]

 while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            A[k] = L[i]; i++; 
        } 
        else { 
            A[k] = M[j]; 
            j++; 
        } 
        k++; 
    }

4-қадам: L немесе M элементтеріндегі элементтер таусылғанда, қалған элементтерді A ішіне орналастыру керек [p..r]

/* Мы вышли из предыдущего цикла, потому что j <n2 не выполняется */  
    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }

/* Мы вышли из предыдущего цикла, потому что i <n1 не выполняется */  

    while (j < n2)
    {
        A[k] = M[j];
        j++;
        k++;
    }
}

Бұл қадам M өлшемі L өлшемінен үлкен болған жағдайда қажет болады.
Біріктіру функциясының соңында A[p..r] ішкі массиві сұрыпталады.