Shell sort

Шелл сорт – (Қисқартириб борувчи қадамлар орқали саралаш)1959-йилда Д.Шелл томонидан таклиф қилинган бўлиб, қўшиш орқали саралашнинг модификацияси ҳисобланади. Гарчи таққослашлар сони бир мунча ортиб борсада, элементларни ўринлаштиришлар анча кам бўлади. Бу усул натижасида ҳар бир ўтишдан кейин саралашлар камайиб боради. Энг ёмон ҳолатда охирги ишни яккалик саралаш амалга оширади. Шелл саралаш усулининг ягона тавсифи ҳар бир ўтишдан кейин қадамларни тўғри танлашдан иборат.

Шелл сорт анимацион усулда

Алгоритми

Фараз қилайлик а[0], а[1], а[2],…, а[н] бошланғич элементлар кетма-кетлиги бўлсин.
1-қадам.Бошланғич кетма-кетликнинг ҳар р1 ўрнида жойлашган элементлари гурухланиб, ҳар бир гурух алоҳида қўшиш усули орқали сараланади({а[0], а[р<суб>1</суб>], а[2*р<суб>1</суб>],…,}, {а[1], а[1+р<суб>1</суб>], а[1+2*р<суб>1</суб>],…,} ва ҳоказо).
2-қадам. Ҳосил қилинган кетма-кетликда ҳар р2 ўринда жойлашган элементлар гуруҳланиб, ҳар бир гуруҳ алоҳида сараланади.
…………………………….
к-қадам. к-1 қадамда ҳосил бўлган кетма-кетлик оддий қўшиш усули орқали сараланади.

р<суб>1</суб>>р<суб>2</суб>>…>р<суб>к-1</суб>>р<суб>к</суб>=1. 

Усул самарадорлиги

Ўртача ҳолат – О(н^7/6),

Энг ёмон ҳолат- О(н^4/3).

Седжвик усули орқали қадамлар танлаётганда, агар 3*инc[с]>н бўлса, у ҳолда энг катта қадам инc[с-1] бўлади.

Дастури

#инcлуде <иостреам> 
        /* функция шеллСорт ёрдамида аррни тартиблаш учун */
воид шеллСорт(инт арр[], инт н) 
{       // Катта бо'шлиқдан бошланг, кейин бо'шлиқни камайтиринг
  фор (инт гап = н / 2; гап > 0; гап /= 2) { 
       // Ушбу бо'шлиқнинг катталиги учун бо'ш жойни қо'шинг.
        // биринчи бо'шлиқлар элементлари арр [0..гап-1] аллақачон тартибда
        // бутун массив бо'лгунча яна битта элемент қо'шишни давом эттиринг
        // бо'ш жой сараланган
        фор (инт и = гап; и < н; и += 1) { 
           // бо'ш жойни ажратилган элементларга арр [и] қо'шиш
            // арр [и] ни темпда сақланг ва и ҳолатида тешик қилинг
            инт темп = арр[и]; 
           // олдинги бо'шлиқларни тартибланган элементларни то'г'ри қадар о'згартиринг
            // арр [и] учун жой топилди
            инт ж; 
            фор (ж = и; ж >= гап && арр[ж - гап] > темп; ж -= гап) 
                арр[ж] = арр[ж - гап]; 
              // темп (оригинал арр [и]) ни то'г'ри жойда жойлаштиринг 
            арр[ж] = темп; 
        } } } 
воид принтАррай(инт арр[], инт н) 
{ 
    фор (инт и = 0; и < н; и++) 
        стд::cоут << арр[и] << " "; 
    стд::cоут << "\н"; 
} 
  
инт маин() 
{ 
    инт арр[] = { 12, 34, 54, 2, 3 }; 
    инт н = сизеоф(арр) / сизеоф(арр[0]); 
  
    стд::cоут << "Аррай бефоре сортинг: \н"; 
    принтАррай(арр, н); 
  
    шеллСорт(арр, н); 
  
    стд::cоут << "Аррай афтер сортинг: \н"; 
    принтАррай(арр, н); 
}