Kompyuter injiniringi” fakulteti “Telekommunikatsiya texnologiyalari” kafedrasi

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

“KOMPYUTER INJINIRINGI” FAKULTETI

“Telekommunikatsiya texnologiyalari” KAFEDRASI
“Ma’lumotlar tuzilmasi va algoritmlar” fanidan
4- LABORATORIYA ISHI

Mavzu:

4.3. Saralashning yaxshilangan usullari va ularning qo‘llanilishi

Bajardi :Toshmatov Sh


Fan o‘qituvchisi: Abduvoitov A


S a m a r q a n d _ 2021

4.3. Saralashning yaxshilangan usullari va ularning qo‘llanilishi
Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar qanday saralash usullari va algoritmlari mavjudligini va ularning samaradorliklarini baholashni o'rganishlari kerak. Shu asosda saralash usullarini qiyosiy tahlil qilishlari va ularga oid dasturlar tuzishni o'zlashtirishlari kerak.
Qo'yilgan masala: Talabalar topshiriq variantiga mos saralash usuli yordamida masalani yechish dasturini yaratish ko'nikmasiga ega bo'lishlari kerak.
Ishni bajarish tartibi:

• 
  Tajriba ishi nazariy ma'lumotlarini o'rganish;
  
• 
  Berilgan topshiriqniтп algoritmini ishlab chiqish;
  
• 
  Python dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Nazariy qism

1. 
   Spagetti sort saralash algoritmi.
   

Spagetti Sort - massivda maksimal elementni topish masalasini hal qilish uchun ajoyib analog algoritmdir.
Tasavvur qilaylik, massivda faqat N ta butun son bor. N ta pishirilmagan spagetti tayoqchasini oling, ularning har birining uzunligi massivdagi bitta qiymatga mos keladi.
Qo'lingizda spagetti yig'ing. Buzilmasligi uchun hovuchni tekis yuzaga qo'ying. Natijada, eng uzun (maksimal) somon birinchi navbatda ko'rinadi.
Bunday algoritmning asimptotik murakkabligi O (1) ga teng. Ammo raqamli dunyoda bu qo'llanilmaydi.

Kvant algoritmi. Grover algoritmi (yoki Grover sxemasi) kvant hisoblashda sanab chiqish masalalarini hal qilish uchun ishlatiladi. Uning yordamida, maksimal topish murakkabligi uchun kamayadi O (sqrt (N)).

2. 
   "Xanoy minorasi" saralash algoritmi
   

Xanoy minorasi. Uchta novda bor, ularning birinchisi turli diametrli disklar bilan bog'langan, kichikroq disklar esa kattaroqlarga tayanadi. 

Ikki qoidaga rioya qilgan holda disklarni bir novdadan ikkinchisiga o'tkazishga ruxsat beriladi:

• 
  Bir vaqtning o'zida faqat bitta disk ko'chiriladi.
  
• 
  Kichikroq disklarni faqat katta disklarga joylashtirishga ruxsat beriladi.
  

Vazifa barcha disklarni birinchi pivotdan oxirgisiga o'tkazishdan iborat (o'rtasi yordamchi sifatida ishlatiladi) Jumboqni yechish uchun optimal rekursiv algoritm O (2 ⁿ -1) vaqt murakkabligiga ega (n bo'ladi).

2-rasm. “Xanoy mino

1. 
   Bubble sort algoritmi orqali Respublikamizdagi viloyatlar maydonini o’sish tartibida joylashtiring. (Foydalangan saralash algoritmingiz haqida nazariy ma’lumotlar bering?)
   

def bubble_sort(our_list):

for i in range(len(our_list)):
for j in range(len(our_list) - 1):
if our_list[j] > our_list[j+1]:
our_list[j], our_list[j+1] = our_list[j+1], our_list[j]

our_list = [4200, 39400, 6800, 20500, 6300,7900,110800, 28400, 160000, 16400, 5100, 15300, 20800] # viloyat maydonlari

bubble_sort(our_list)
print(our_list)