Toshkent Axborot Texnologiyalar Universiteti Axborot xavfsizligi fakulteti715-20 guruh talabasi Ismoilov Feruzning ma’lumotlar tuzilmasi va algoritmlari fanidan bajargan mustaqil ishi Kriptalogiya kafedrasi Toshkent 2022 Mavzu

QuickSort barqarormi ?  
Standart dastur barqaror emas. Biroq, taqqoslash parametri sifatida indekslarni hisobga olgan holda har qanday tartiblash algoritmini barqaror qilish mumkin. 

ShellSort
ShellSort asosan Insertion Sort ning o'zgarishidir . Qo'shish tartibida biz elementlarni faqat bir pozitsiya oldinga siljitamiz. Elementni ancha oldinga siljitish kerak bo'lganda, ko'plab harakatlar ishtirok etadi. ShellSort g'oyasi uzoqdagi narsalarni almashish imkonini beradi. ShellSort-da biz massivni h ning katta qiymati uchun h-tartibga solamiz. Biz h qiymatini 1 ga aylanguncha kamaytirishda davom etamiz. Agar har bir h elementning barcha quyi ro'yxatlari tartiblangan bo'lsa, massiv h-tartiblangan deyiladi.

Quyida ShellSort dasturining amalga oshirilishi keltirilgan.

#include using namespace std; int shellSort(int arr[], int n) { for (int gap = n/2; gap > 0; gap /= 2) { for (int i = gap; i < n; i += 1) { int temp = arr[i]; int j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) arr[j] = arr[j - gap]; arr[j] = temp; } } return 0; } void printArray(int arr[], int n) { for (int i=0; i cout << arr[i] << " "; } int main() { int arr[] = {12, 34, 54, 2, 3}, i; int n = sizeof(arr)/sizeof(arr[0]) cout << "Array before sorting: \n"; printArray(arr, n); shellSort(arr, n); cout << "\nArray after sorting: \n"; printArray(arr, n); return 0; }

Chiqish:
Saralashdan oldin massiv:
12 34 54 2 3
Saralashdan keyin massiv:
2 3 12 34 54
Vaqt murakkabligi: Yuqoridagi shellsortni amalga oshirishning vaqt murakkabligi O(n ² ). Yuqoridagi amalga oshirishda bo'shliq har bir iteratsiyada yarmiga kamayadi. Vaqtni murakkablashtirishga olib keladigan bo'shliqni kamaytirishning ko'plab boshqa usullari mavjud.