Shell sort

Shell sort – (Qisqartirib boruvchi qadamlar orqali saralash)1959-yilda D.Shell tomonidan taklif qilingan boʻlib, qoʻshish orqali saralashning modifikatsiyasi hisoblanadi. Garchi taqqoslashlar soni bir muncha ortib borsada, elementlarni oʻrinlashtirishlar ancha kam boʻladi. Bu usul natijasida har bir oʻtishdan keyin saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni yakkalik saralash amalga oshiradi. Shell saralash usulining yagona tavsifi har bir oʻtishdan keyin qadamlarni toʻgʻri tanlashdan iborat.

Shell sort animatsion usulda

Algoritmi

Faraz qilaylik a[0], a[1], a[2],…, a[n] boshlangʻich elementlar ketma-ketligi boʻlsin.
1-qadam.Boshlangʻich ketma-ketlikning har r1 oʻrnida joylashgan elementlari guruxlanib, har bir gurux alohida qoʻshish usuli orqali saralanadi({a[0], a[r<sub>1</sub>], a[2*r<sub>1</sub>],…,}, {a[1], a[1+r<sub>1</sub>], a[1+2*r<sub>1</sub>],…,} va hokazo).
2-qadam. Xosil qilingan ketma-ketlikda har r2 oʻrinda joylashgan elementlar guruhlanib, har bir guruh alohida saralanadi.
…………………………….
k-qadam. k-1 qadamda hosil boʻlgan ketma-ketlik oddiy qoʻshish usuli orqali saralanadi.

r<sub>1</sub>>r<sub>2</sub>>…>r<sub>k-1</sub>>r<sub>k</sub>=1. 

Usul samaradorligi

Oʻrtacha holat – O(n^7/6),

Eng yomon holat- O(n^4/3).

Sedjvik usuli orqali qadamlar tanlayotganda, agar 3*inc[s]>n boʻlsa, u holda eng katta qadam inc[s-1] boʻladi.

Dasturi

#include <iostream> 
        /* funktsiya shellSort yordamida arrni tartiblash uchun */
void shellSort(int arr[], int n) 
{       // Katta bo'shliqdan boshlang, keyin bo'shliqni kamaytiring
  for (int gap = n / 2; gap > 0; gap /= 2) { 
       // Ushbu bo'shliqning kattaligi uchun bo'sh joyni qo'shing.
        // birinchi bo'shliqlar elementlari arr [0..gap-1] allaqachon tartibda
        // butun massiv bo'lguncha yana bitta element qo'shishni davom ettiring
        // bo'sh joy saralangan
        for (int i = gap; i < n; i += 1) { 
           // bo'sh joyni ajratilgan elementlarga arr [i] qo'shish
            // arr [i] ni tempda saqlang va i holatida teshik qiling
            int temp = arr[i]; 
           // oldingi bo'shliqlarni tartiblangan elementlarni to'g'ri qadar o'zgartiring
            // arr [i] uchun joy topildi
            int j; 
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
                arr[j] = arr[j - gap]; 
              // temp (original arr [i]) ni to'g'ri joyda joylashtiring 
            arr[j] = temp; 
        } } } 
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        std::cout << arr[i] << " "; 
    std::cout << "\n"; 
} 
  
int main() 
{ 
    int arr[] = { 12, 34, 54, 2, 3 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    std::cout << "Array before sorting: \n"; 
    printArray(arr, n); 
  
    shellSort(arr, n); 
  
    std::cout << "Array after sorting: \n"; 
    printArray(arr, n); 
}