86. Xasis algoritm qachon qo’llaniladi

86. Xasis algoritm qachon qo’llaniladi?

Agar ochko'z algoritm ushbu muammoni echishga imkon beradigan bo'lsa, qanday qilib bilasiz? Bu erda umumiy retseptlar mavjud emas, ammo hasis algoritmlar tomonidan hal qilingan muammolarga xos bo'lgan ikkita xususiyat mavjud. Bu hasis tanlov printsipi va pastki qismlarga maqbullik xususiyati.

87.“Бўлиб ташла ва ҳукмронлик қил” алгоритмининг босқичларини айтинг.

Dasturlashda, bo’lib tashla va hukmronlik qil — bu algoritmik paradigma bo’lib, bu paradigmaning asosiy g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib tashlab, ularni rekursiv hal qilishdan iborat. Bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos holat bo’lishi kerak. Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:

1. 
   Bo’lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.
   
2. 
   Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
   

3.Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.

88.Qanday saralash algoritmlarini bilasiz?

1. 
   Selection sort (Tanlab saralash)
   
2. 
   Bubble sort (Pufakchali saralash)
   
3. 
   Insertion sort (Joylashtirib saralash)
   
4. 
   Quick sort (Tezkor saralash)
   
5. 
   Merge sort (Qo’shib saralash)
   
6. 
   Radix sort
   

Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:

• 
  Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin.
  
• 
  Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.
  

Insertion sort (Joylab saralash) 

Algoritm qadamlari

1. 
   Array boshidagi ikkita element solishtirib, saralab olinadi.
   
2. 
   Qolgan elementlar bitta bitta qarab chiqiladi. (Tashqi iteratsiya)
   
3. 
   Har bir element ichki takrorlanish orqali o’z joyiga joylashtirib boriladi. Bu yerda array chegaralaridan o’tib ketib qolmaslikka e’tibor berish kerak.
   
4. 
   Tashqi takrorlanish tugashi bilan array ham saralangan bo’ladi
   

Bubble sort algoritm

Algoritm qadamlari

Ko’rib turganingizdek algoritm g’oyasi juda ham oddiy. Endi uni qadamma-qadam keltirib o’tamiz.

1. 
   Array boshidan uning oxirgi elementidan bitta oldingi elementigacha yurib chiqamiz.
   
2. 
   Har bir yurib chiqishda ichki takrorlanish orqali qo’shni elementlarni bir-biri bilan solishtirib, katta elementni o’ng tomonga joylashtirib ketamiz. (O’sish tartibidagi saralashda)
   
3. 
   Har bir tashqi takrorlanish qadami tugagandan so’ng bizda array oxiridan boshlab array saralanib boradi. Shu sababli har safar ichki takrorlanishda bu qismni qayta ko’rib chiqish shart emas.
   
4. 
   Tashqi takrorlanish tugaganda bizda saralangan massiv hosil bo’ladi
   

89.Саралаш алгоритмлари самарадорлигини қандай баҳолаш мумкин?

Saralash samaradorligini bir necha mezonlar bo’yicha baholash mumkin:

• 
  Saralashga ketgan vaqt
  
• 
  Saralash uchun talab qilingan operativ xotira
  
• 
  Dasturni ishlab chiqishga ketgan vaqt
  

Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin. Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo’lsa, u holda ikkinchi qo’shiluvchi katta, aks holda ya’ni, n > 1000 bo’lsa, birinchi qo’shiluvchi katta bo’ladi. Demak, kichkina n larda taqqoslashlar soni n ga teng bo’ladi, katta n larda esa n2 ga teng bo’ladi.

Saralashning quyidagicha usulla

• 
  Qatiy usul
  
• 
  yaxshilangan usul
  

Qat’iy usullarning afzalliklarini ko’rib chiqaylik: 1. Bilamizki, dasturlarning o’zlari ham xotirada joy egallaydi. To’g’ridanto’g’ri saralash usullarining dasturlari qisqa bo’lib, ular tushunishga oson. 2. To’g’ridan-to’g’ri saralash usullari orqali saralash tamoyillarining asosiy xususiyatlarini tushuntirish qulay. 3. Murakkablashtirilgan usullarda uncha ko’p amallarni bajarish talab qilinmasada, ushbu amallarning o’zlari ham ancha murakkabdir. Garchi yetarlicha katta n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.
90.Stek тузилмасини тушунтиринг ва мисол келтиринг.

Stack bu yana bir chiziqli ma’lumot tuzilmasi bo’lib, u ham Linked listning maxsus bir ko’rinishi hisoblanadi. Stackda har bir tugunda ma’lumot va o’zidan oldingi tugun adresi saqlanadi. Shuning uchun unda faqat oxirgi qo’shilgan ma’lumot ustidagina qandaydir amal bajarish mumkin. Ko’pchilikni “hayotini saqlab qolgan” CTRL+Z operatsiyasini ko’z oldingizga keltiring. Har safar bu tugmalarni bosganda oxirgi qilgan ishlaringiz orqadan oldinga qarab chiqib keladi (bekor qilinadi). Huddi shu yerda stack tuzilmasi ishlatilganini ko’rishimiz mumkin.

Stackga hayotiy misol sifatida bir uchi yopiq bo’lgan trubani keltirish mumkin. Trubaga do’stingiz bir nechta turli rangdagi sharlar tashladi. Endi siz sharlar rangini bilish uchun faqatgina do’stingiz oxirgi bo’lib truba ichiga tashlagan sharning ranginigina ko’ra olasiz. Qolgan sharlarni ko’rish uchun do’stingiz tashlagan tartibdan teskari tartibda ularni olib chiqishingiz kerak bo’ladi.

Stack ustidagi asosiy amallar

• 
  Stackga element qo’shish (Push)
  
• 
  Stackdan elementni olish. Element o’chiriladi (Pop)
  
• 
  Stackdagi top elementni ko’rish. Element o’chirilmaydi (Peek)
  
• 
  Stackni bo’shlikka tekshirish (isEmpty)
  

# Python dasturi

# stekning bajarilishini namoyish eting

# ro'yxatidan foydalanish

Dastur kodi:

stack = []
# append() function to push

# element in the stack

stack.append('a')

stack.append('b')

stack.append('c')
print('Initial stack')

print(stack)

# pop() fucntion to pop

# element from stack in

# LIFO order

print('\nElementlar ustunlardan paydo bo'ldi:')

print(stack.pop())

print(stack.pop())

print(stack.pop())
print('\nElementlar keyin stack:')

print(stack)

# bo'ysunmaydigan print(stack.pop())

# IndexError sabab bo'ladi