Jump to content

Мерге Сорт

From Ziyosfera

Мерге сорт — (Бирлаштириб саралаш) алгоритми асосий бешта саралаш алгоритмлари (Буббле сорт, Қуиcк сорт ва бошқалар) дан бири бўлиб, чизиқли саралаш алгоритмларидан фарқли равишда „бўлиб ташла ва ҳукмронлик қил“ типидаги алгоритм ҳисобланади. Бу турдаги алгоритмлар катта ҳажмдаги масалаларни нисбатан кичик бўлган ва осон ечиладиган қисмларга ажратган ҳолда бажаради. Бундай алгоритмлар масалаларни ечишда вақтдан ютиш имконини беради[1].

Мерге-сорт-эхампле-300пх

Мерге сорт алгоритми

  • Мерге Сорт функсиясига массив ва унинг бошланғич (энг чапдаги элемент) ва охирги нуқталари (энг ўнгдаги элемент) берилади.
  • Массивнинг ўртаси ҳисобланади: ўртаси = (чап + ўнг)/2. Бу нарса уни тенг иккига бўлиш учун керак бўлади.
  • Мерге сортни рекурсив ҳолда биринчи ва иккинчи қисмлар учун чақирилади.
  • 2- ва 3-қисмларда ҳосил бўлган массивлар бирлаштириб чиқилади.

Алгоритм ишлаш тезлиги О(н*лог(н)) бўлиб тезлиги О(н2) бўлган оддий Буббле сорт, Инсертион сорт, Селеcтион сортлардан анча тез ишлайди. Таққослаш асосида ишлайдиган алгортмларнинг энг тез ишлаш ҳолати О(н*лог(н)) бўлиши исботланган[2].

Мерге сорт алгоритҳм диаграм

Дастури

#include <iostream>
using namespace std;

void merge(int array[], int const left, int const mid, int const right)
{
    auto const subArrayOne = mid - left + 1;
    auto const subArrayTwo = right - mid;

    auto *leftArray = new int[subArrayOne],
         *rightArray = new int[subArrayTwo];

    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];
 
    auto indexOfSubArrayOne = 0,
        indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;
    while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
}
void mergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
        return; // Returns recursively
    auto mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}
void printArray(int A[], int size)
{
    for (auto i = 0; i < size; i++)
        cout << A[i] << " ";
}
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    auto arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Given array is \n";
    printArray(arr, arr_size);
    mergeSort(arr, 0, arr_size - 1);
    cout << "\nSorted array is \n";
    printArray(arr, arr_size);
    return 0;
}

[3].

Камчилиги

  • Кичикроқ вазифалар учун бошқа тартиблаш алгоритмларига нисбатан секинроқ.
  • Мерге сорт алгоритми вақтинчалик массив учун 0(н) қўшимча хотира майдонини талаб қилади.
  • Агар массив тартибланган бўлса ҳам, у бутун жараёндан ўтади.

Манбалар