Insertion sort

Инсертион сорт — (Жойлаб саралаш) ҳам тартибсиз массив элементларини саралаш учун мўлжалланган. Унинг ишлаш алгоритми худди қўлдаги картани саралашга ўхшаб кетади. Тартибсиз турган карталар ичидан бирини оласиз ва уни ўзи туриши керак бўлган жойга жойлаштириб қўясиз.

Инсертион сорт ҳам шу кўринишда ишлайди. Алгоритм олдин массив бошидаги иккита элементни саралаб олиб, массивнинг қолган элементларини шунга қараб ўз ўрнига жойлаштириб чиқади.

Дарк инвертед инсертион сортинг

Жойлаб саралашнинг хусусиятлари

Бу алгоритм оддий амалга оширилгани учун энг оддий алгоритмлардан биридир. Инсертион сорт кичик маълумотларни саралаш учун самарали. Жойлаб саралаш табиатан мослашувчан, яъни қисман сараланган маълумотлар тўпламлари учун мос келади.

Инсертион сорт ҳам Селеcтион сорт ва Буббле сорт каби О(н²) вақт мураккаблиги билан ишласа ҳам, лекин улардан кўра самаралироқ алгоритм ҳисобланади. Айнан, массив элементлари деярли сараланган ҳолатда Инсертион сорт алгоритми Мерге сорт ёки Қуиcк сорт алгоритмидан ҳам кўра тезроқ ишлайди.

Жойлаб саралаш алгоритмининг ишлаши

Мисолни кўриб чиқинг: арр[]: {12, 11, 13, 5, 6}

  12   	   11   	   13   	   5   	   6   

Биринчи ўтиш

Дастлаб, массивнинг дастлабки иккита элементи жойлаш тартибида таққосланади.

  12   	   11   	   13   	   5   	   6   

Бу ерда 12 11 дан катта, улар ўсиш тартибида эмас ва 12 ўзининг тўғри жойида эмас. Шундай қилиб, 11 ва 12 нинг ўрнини алмаштиринг. Шундай қилиб, ҳозирча 11 тартибланган пастки қаторда сақланади.

  11   	   12   	   13   	   5   	   6   

Иккинчи ўтиш

Энди кейинги иккита элементга ўтинг ва уларни солиштиринг

  11   	   12   	   13   	   5   	   6   

Бу ерда 13 12 дан катта, шунинг учун иккала элемент ҳам ўсиш тартибида турибди, алмаштириш содир бўлмайди. 12, шунингдек, 11 билан бирга тартибланган пастки қаторда сақланади

Учинчи ўтиш

Энди тартибланган кичик массивда иккита элемент мавжуд, улар 11 ва 12 Кейинги иккита элементга ўтиш: 13 ва 5

  11   	   12   	   13   	   5   	   6   

5 ва 13 иккаласи ҳам ўз жойида эмас, шунинг учун уларни алмаштиринг

  11   	   12   	   5   	   13   	   6   

Алмаштирилгандан сўнг, 12 ва 5 элементлар тартибланмади, шунинг учун яна алмаштирилади

  11   	   5   	   12   	   13   	   6   

Бу ерда яна 11 ва 5 тартибланмади, шунинг учун яна алмаштиринг

  5   	   11   	   12   	   13   	   6   

бу ерда у ўзининг тўғри ҳолатида

Тўртинчи ўтиш

Энди тартибланган кичик массивда мавжуд бўлган элементлар 5, 11 ва 12 Кейинги иккита элементга ўтиш: 13 ва 6

  5   	   11   	   12   	   13   	   6   

Шубҳасиз, улар тартибланмаган, шунинг учун иккаласини алмаштиришни амалга оширинг

  5   	   11   	   12   	   6   	   13   

Энди 6 12 дан кичик, шунинг учун яна алмаштиринг

  5   	   11   	   6   	   12   	   13   

Алмаштириш 11 ва 6 ни тартибламайди, шунинг учун яна алмаштиринг

  5   	   6   	   11   	   12   	   13   

Ниҳоят, массив тўлиқ тартибланган.

ИнсертионСорт

Дастури

#инcлуде <биц/стдc++.ҳ>
усинг намеспаcе стд;
воид инсертионСорт(инт арр[], инт н)
{
    инт и, кей, ж;
    фор (и = 1; и < н; и++)
    {
        кей = арр[и];
        ж = и - 1;
        wҳиле (ж >= 0 && арр[ж] > кей)
        {
            арр[ж + 1] = арр[ж];
            ж = ж - 1;
        }
        арр[ж + 1] = кей;
    }
}
воид принтАррай(инт арр[], инт н)
{
    инт и;
    фор (и = 0; и < н; и++)
        cоут << арр[и] << " ";
    cоут << эндл;
}
инт маин()
{
    инт арр[] = { 12, 11, 13, 5, 6 };
    инт Н = сизеоф(арр) / сизеоф(арр[0]);
    инсертионСорт(арр, Н);
    принтАррай(арр, Н);
    ретурн 0;
}