Shell sort algoritmi orqali Respublikamizdagi viloyatlar maydonini o’sish tartibida joylashtiring

Shell tartiblash algoritmi
shellSort(array, size)
for interval i <- size/2n down to 1
for each interval "i" in array
sort all the elements at interval "i"
end shellSort
Pythonda Shell Sort Code
# Shell sort in python
def shellSort(array, n):


# Rearrange elements at each n/2, n/4, n/8, ... intervals
interval = n // 2
while interval > 0:
for i in range(interval, n):
temp = array[i]
j = i
while j >= interval and array[j - interval] > temp:
array[j] = array[j - interval]
j -= interval


array[j] = temp
interval //= 2
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Shell sort - bu beqaror tartiblash algoritmi, chunki bu algoritm intervallar orasidagi elementlarni tekshirmaydi.
Vaqtning murakkabligi

• 
  Eng yomon holatlarning murakkabligi : dan kichik yoki teng bo'lgan qobiq tartiblash uchun eng yomon holat murakkabligi har doim dan kichik yoki teng bo'ladi . Poonen teoremasiga ko'ra, qobiqli tartiblash uchun eng yomon holat murakkabligi yoki yoki yoki ularning orasidagi narsadir.O(n²)
  O(n²)
  
  Θ(Nlog N)²/(log log N)²)Θ(Nlog N)²/log log N)Θ(N(log N)²)
  
• 
  Eng yaxshi holatlar murakkabligi : Massiv O(n*log n)
  allaqachon tartiblangan bo'lsa, har bir interval (yoki o'sish) uchun taqqoslashlarning umumiy soni massiv o'lchamiga teng bo'ladi.
  
• 
  O'rtacha Case murakkabligi : O(n*log n)
  Bu atrofida .O(n^1.25)
  

Murakkablik tanlangan intervalga bog'liq. Yuqoridagi murakkabliklar tanlangan o'sish ketma-ketligi uchun farq qiladi. Eng yaxshi o'sish ketma-ketligi noma'lum.
Kosmik murakkablik: