Malumotlar tuzilmasi va algoritmlar

Algoritm:
1-qadam -
2-bosqichni boshlang - bo'shliq o'lchamining qiymatini ishga tushiring. Misol: h
3-qadam - Ro'yxatni kichikroq kichik qismga bo'ling. Har birida h ga teng intervallar bo'lishi kerak
4-qadam – Qo'shish tartibidan foydalanib ushbu kichik ro'yxatlarni tartiblang
5-qadam – Ro'yxat tartiblashtirilguncha ushbu 2-bosqichni takrorlang.
6-qadam - Saralangan ro'yxatni chop eting.
7-qadam - To'xtatish.
Va
Yuqoridagi Shell sortini amalga oshirishning vaqt murakkabligiO(n ² ). Yuqoridagi amalga oshirishda bo'shliq har bir iteratsiyada yarmiga kamayadi. Bo'shliqlarni kamaytirishning boshqa ko'plab usullari mavjud, bu esa vaqtni yanada murakkablashtiradi. Batafsil ma'lumot uchun buni ko'ring .
Eng yomon holat murakkabligi
Shell tartiblash uchun eng yomon holat murakkabligi O(n ² )
Eng yaxshi holat murakkabligi
Berilgan massivlar ro'yxati allaqachon tartiblangan bo'lsa, har bir oraliqning taqqoslashlarining umumiy soni berilgan massivning o'lchamiga teng bo'ladi.
Shunday qilib, eng yaxshi holatlar murakkabligi Ō(n log(n))
O'rtacha holatlar murakkabligi
Shell sort Average Case Complexity dasturchi tanlagan intervalga bog'liq. 
th(n log(n)2) .
O'rtacha registrlar murakkabligi: O(n*log n)~O(n ^1.25 ) qobiqning fazoviy murakkabligi O(1) ga teng .
1. Big-O belgisiga ko'ra, qobiqli tartiblash O(n^{1.25}) o'rtacha vaqt murakkabligiga ega bo'lsa, yig'ma tartiblash O(N log N) vaqt murakkabligiga ega. Big-O belgisining qat'iy matematik talqiniga ko'ra, saralash uchun 2000 ta elementga yaqinlashganda, yig'ma tartiblash samaradorlik bo'yicha qobiq sortidan oshib ketadi.
Es Big-O yaxlitlangan taxmindir va analitik baholash har doim ham 100% to'g'ri emas, bu algoritmlarni amalga oshirishga bog'liq bo'lib, haqiqiy ish vaqtiga ta'sir qilishi mumkin.


Dasturlar:
#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 a,i;
cout<<"nechta element kiritmoqchisiz: ";
cin>>a;
int arr[a] ;
for(int i=0;i
cin>>arr[i];
cout<
}
int n = sizeof(arr)/sizeof(arr[0]);

cout << "siz kiritgan massiv elementlari: \n";
printArray(arr, n);

shellSort(arr, n);

cout << "\nsaralangan massiv elementlari: \n";
printArray(arr, n);

return 0;
}

heapsort tartiblash nima?