Merge Sort

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

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

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

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

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

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

Дастури

#инcлуде <иостреам>
усинг намеспаcе стд;

воид мерге(инт аррай[], инт cонст лефт, инт cонст мид, инт cонст ригҳт)
{
    ауто cонст субАррайОне = мид - лефт + 1;
    ауто cонст субАррайТwо = ригҳт - мид;

    ауто *лефтАррай = неw инт[субАррайОне],
         *ригҳтАррай = неw инт[субАррайТwо];

    фор (ауто и = 0; и < субАррайОне; и++)
        лефтАррай[и] = аррай[лефт + и];
    фор (ауто ж = 0; ж < субАррайТwо; ж++)
        ригҳтАррай[ж] = аррай[мид + 1 + ж];
 
    ауто индехОфСубАррайОне = 0,
        индехОфСубАррайТwо = 0;
    инт индехОфМергедАррай = лефт;
    wҳиле (индехОфСубАррайОне < субАррайОне && индехОфСубАррайТwо < субАррайТwо) {
        иф (лефтАррай[индехОфСубАррайОне] <= ригҳтАррай[индехОфСубАррайТwо]) {
            аррай[индехОфМергедАррай] = лефтАррай[индехОфСубАррайОне];
            индехОфСубАррайОне++;
        }
        элсе {
            аррай[индехОфМергедАррай] = ригҳтАррай[индехОфСубАррайТwо];
            индехОфСубАррайТwо++;
        }
        индехОфМергедАррай++;
    }
    wҳиле (индехОфСубАррайОне < субАррайОне) {
        аррай[индехОфМергедАррай] = лефтАррай[индехОфСубАррайОне];
        индехОфСубАррайОне++;
        индехОфМергедАррай++;
    }
    wҳиле (индехОфСубАррайТwо < субАррайТwо) {
        аррай[индехОфМергедАррай] = ригҳтАррай[индехОфСубАррайТwо];
        индехОфСубАррайТwо++;
        индехОфМергедАррай++;
    }
}
воид мергеСорт(инт аррай[], инт cонст бегин, инт cонст энд)
{
    иф (бегин >= энд)
        ретурн; // Ретурнс реcурсивелй
    ауто мид = бегин + (энд - бегин) / 2;
    мергеСорт(аррай, бегин, мид);
    мергеСорт(аррай, мид + 1, энд);
    мерге(аррай, бегин, мид, энд);
}
воид принтАррай(инт А[], инт сизе)
{
    фор (ауто и = 0; и < сизе; и++)
        cоут << А[и] << " ";
}
инт маин()
{
    инт арр[] = { 12, 11, 13, 5, 6, 7 };
    ауто арр_сизе = сизеоф(арр) / сизеоф(арр[0]);
    cоут << "Гивен аррай ис \н";
    принтАррай(арр, арр_сизе);
    мергеСорт(арр, 0, арр_сизе - 1);
    cоут << "\нСортед аррай ис \н";
    принтАррай(арр, арр_сизе);
    ретурн 0;
}

.

Камчилиги

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