Shell sort algorithms

C++ tilida Shell sort algoritmi

#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 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;
} 

Python tilida Shell Sort algoritmi

def shellSort(arr, n):

# Dastur kodi
gap=n//2
while gap>0:
j=gap
while j i=j-gap
while i>=0:
if arr[i+gap]>arr[i]:

break
else:

arr[i+gap],arr[i]=arr[i],arr[i+gap]

i=i-gap

j+=1
gap=gap//2

arr2 = [12, 34, 54, 2, 3]

print("input array:",arr2)

shellSort(arr2,len(arr2))

print("sorted array",arr2)


Berilgandagi holat:
12 34 54 2 3
Saralangandagi holat:
2 3 12 34 54

Vaqt murakkabligi: Yuqoridagi Shell sortini amalga oshirishning vaqt murakkabligi O(n2). 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 holatlarning murakkabligi
Qobiqni saralashning eng yomon murakkabligi O(n2)
Eng yaxshi holatlar murakkabligi
Berilgan massivlar roʻyxati tartiblangan boʻlsa, har bir intervalni taqqoslashlarning umumiy soni berilgan massivning oʻlchamiga teng boʻladi..
Shunday qilib, eng yaxshi murakkablik Ō(n log(n)) dir.

Oʻrtacha ish murakkabligi oʻrtacha vaqt murakkabligi, yigʻma tartiblashda esa O(N log N) vaqt murakkabligi mavjud. 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.
Eslatma: - 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. o'rtacha vaqt murakkabligi, yig'ish tartibi esa 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.
Eslatma: - 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.

http://en.wikipedia.org/wiki/Shellsort
Shell sort algoritmi haqida quyidagi havola orqali ham ma’lumot olishingiz mumkin!

ISHLASH KO’RINISHI


Qatorni teng ikkiga bo’lib olamiz.

Tanlangan qolgan elementlar bilan taqqoslanadi.Element kichik bo’lmagani uchun o’z joyida qoladi.

Yana sonlar qatorini teng ikkiga bo’lib, chapdan va o’ngdan element tanlab olinadi.

Tanlangan ikki elelment 2 va 34 taqqoslanib kichigi o’z joyini alishtiradi.Ya’ni chap tarafga joylashtiriladi.


Shell saralash algoritmi Isertion sort algoritmiga o’xshash bo’lganligi sababli, 2 va 3 o’z joyini almashadi.