Saralash algoritimi va ularni baholash
![Yuqoridagi animatsiyada arrayning boshidan emas, orqasidan yurib
chiqilgani sababli har bir array bo’ylab yurib chiqishda eng kichik
element boshiga o’tib qolmoqda. Bu narsa algoritm qanday
implementatsiya qilinganiga bog’liq.
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.
Algoritm murakkabligi
Bubble sort algoritmining ishlash tezligi ham O(n²) hisoblanadi (n —
array uzunligi). Ya’ni yuqorida ko’rib o’tganimizdek, bitta tashqi
takrorlanish har bir qadamida arrayni to’liq ko’rib chiqish kerak bo’ladi.
def bubble_sort(a):
n=len(a)
for i in range(n-1):
for j in range(n-i-1):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
Selection sort
Tanlab saralash bu — oddiy tartiblash algoritmidir. Selection sort g’oyasi](https://docx.uz/documents/cae1173b-3033-416a-8918-a3d178ef816e/page_6.png?v=1)
![Selection sort g’oyasi juda ham oddiy: har qadamda arrayning saralanmagan
qismidagi eng kichik (yoki eng katta) elementni topib saralangan qism oxiriga
qo’shib ketish.
Algoritm qadamlari
Yuqorida aytganimizdek arrayda ikkita qism saralanmagan va saralangan qism
bo’ladi. Algoritm boshida array butunligicha saralanmagan qismda bo’ladi va
algoritm oxirida esa saralangan qismga o’tadi.
1.Array boshidan yurib chiqamiz.
2.Har bir qadamda saralanmagan qismdagi eng kichik elementni topib uni
saralanmagan qism boshidagi element bilan almashtiramiz.
3.Saralangan qismni ko’rsatkichini bittaga oshiramiz.
4.Oxirgi element avtomatik tarzda o’z joyida bo’lib qoladi.
Algoritm murakkabligi
Selection sort eng oddiy saralash algoritmlaridan bo’lib O(n²) vaqt tezligida
ishlaydi. Ya’ni, algoritm barcha elementlarni ko’rib chiqish (n-1) mobaynida,
har bir qadamda eng kichik elementni topish uchun qolgan elementlarni ko’rib
chiqishi kerak bo’ladi.
Tanlash saralash algoritmi,ro’yxatdagi eng kichik elementni topib,uni
ro’yxatning boshiga joylashtirib saralashni amalga oshiradi.Ushbu jarayon eng
kichik element topilguncha takrorlanadi.
Def kichik_element(a):
n=len(a)
for i in range(n):
min_idx=i
for j in range(i+1,n):
if a[j]<a[min_idx]:
min_idx=j
a[i],a[min_idx]=a[min_idx],a[i]](https://docx.uz/documents/cae1173b-3033-416a-8918-a3d178ef816e/page_7.png?v=1)
![Insertion sort
Insertion sort (Joylab saralash) ham tartibsiz array elementlarini saralash uchun
mo’ljallangan. Uning ishlash prinsipi (g’oyasi) huddi qo’ldagi kartani
saralashga o’xshab ketadi. Ya’ni tartibsiz turgan kartalar ichidan birini olasiz
va uni o’zi turishi kerak bo’lgan joyga joylashtirib qo’yasiz. (Yuqoridagi
rasmga qarang)
Insertion sort ham shunday ishlaydi. Algoritm oldin array boshidagi ikkita
elementni saralab oladida qolgan elementlarni shularga qarab o’z o’rniga
joylashtirib ketaveradi. (Ulardan oldiga, ularning orasiga yoki ulardan
keyinga). Har bir element huddi shu tartibda o’z o’rnini topib boraveradi.
Algoritm qanday ishlashini quyidagi animatsiya orqali ham ko’rishingiz
mumkin:
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.
Algoritm murakkabligi
Insertion sort ham Selection va Bubble sort kabi O(n²) vaqt murakkabligi bilan
ishlasa ham, lekin ulardan ko’ra samaraliroq algoritm hisoblanadi . Bir
elementni to’g’ri o’rniga joylashish uchun qolgan elementlar orasida
muvofiqligi topilguncha taqqoslash va joylashtirish bilan analga oshiradi.
def insertion_sort(a):
n=len(a)
for i in range(1,n):
b=i-1
while j>=0 and a[j]>b:
a[j+1]=a[j]
j=j-1
a[j+1]=b](https://docx.uz/documents/cae1173b-3033-416a-8918-a3d178ef816e/page_8.png?v=1)
![Quick sort
Tez saralash - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir .
Saralash algoritmi,pivot elementini tanlab,unga qarab elementlarni bo’lib,pivotdan
kichik elementlar qismi va katta elementlar qismi o’rniga joylashtirib,bo’sh
elementlar qismi orqali saralashni amalga oshiradi.keyinchalik,kichik va katta
elementlarning qismi ham rekursiv ravishda tez saralashga o’tkaziladi.
Ishlash printsipi tahrir
1.Massivda ixtiyoriy tayanch element tanlaymiz.
2.Keyin undan kichik yoki teng elementlarni uning chap tomoniga, katta
elementlarni o ng tomoniga o tkazamiz.ʻ ʻ
3.1-2-chi qadamlarni tayanch elementning o ng va chap tomonlaridagi elementlar
ʻ
uchun qo llaymiz.
ʻ
Algorimning 2 qadami turlicha bo lib uning bir nechta realizatsiyalari mavjud.
ʻ
Ayni shu 2 qadamda elementlarni joylashtirish algoritmi tufayli algoritm saralash
algoritmlari ichida eng tez ishlaydiganlaridan biridir.
def quick_sort(a):
if len(a)<=1:
return a
pivot=a[len(a)//2]
chap=[x for x in a if x <pivot]
o’rtasida=[x for x in a if x==pivot]
o’ng=[x for x in a if x>pivot]
return quick_sort(chap)+o’rtasida+quick_sort(o’ng)
Merge sort
Birlashtirib saralash -algoritmi asosiy beshta saralash algoritmlaridan biri bo lib,
ʻ
chiziqli saralash algoritmlaridan farqli ravishda „bo lib tashla va hukmronlik qil“
ʻ](https://docx.uz/documents/cae1173b-3033-416a-8918-a3d178ef816e/page_9.png?v=1)
![tipidagi algoritm hisoblanadi.Birlashtirish saralash algoritmi,ro’yxatni yarim-yarim
bo’lib,har bir yarimini rekursiv ravishda birlashtirib saralashni amalga oshiradi.
Birlashtirish jarayonida,birlashtirilayotgan ro’yxatlarning elementlari to’g’ri
tartibda joylashtiriladi.
Merge Sort va uning ishlash prinsipi
Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi
algoritm bo'lib, uning ishlash prinsipida to'liq bo'lib tashla va hukmronlik qil
g'oyasini uchratish mumkin. Demak, merge sort asosiy ikkita qismdan iborat:
Berilgan arrayni rekursiv holda teng ikkita qismlarga bo'lib chiqish. Bu qadam,
qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo'lib qolguncha davom etadi.
Hosil bo'lgan arraylarni qaytib birlashtirib chiqish va bir vaqtni o'zida hosil
bo'luvchi array saralangan bo'lishini ta'minlash.
Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga
e'tiboringizni qaratmoqchiman. Unda amallar tartibi ham ko'rsatib qo'yilgan
Merge sort algoritmi qadamlari
1.Merge Sort funksiyasiga array va uning boshlang'ich (left) va oxirgi nuqtalari
(right) beriladi.
2.Arraynining o'rtasi hisoblanadi: mid = (left + right)/2. Bu narsa uni teng ikkiga
bo'lish uchun kerak bo'ladi.
3.Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
4.2- va 3-qismlarda hosil bo'lgan arraylar birlashtirib chiqiladi.
def merge_sort(a):
if len(a)<=1:
return a
orta=len(a)//2
chap=a[:o’rta]
ong=a[o’rta:]
chap=merge_sort(chap)
ong=merge_sort(ong)
return merge(chap,ong)
def merge(chap,ong):
natija=[]](https://docx.uz/documents/cae1173b-3033-416a-8918-a3d178ef816e/page_10.png?v=1)
![i=j=0
while i<len(chap) and j<len(ong):
if chap[i]<ong[j]:
natija.append(ong[j])
j=j+1
natija.extend(chap[i:])
natija.extend(ong[j:])
print(natija)
Merge sort algoritmi
Merge Sort funksiyasiga massiv va uning boshlang ich (eng chapdagi element) vaʻ
oxirgi nuqtalari (eng o ngdagi element) beriladi.
ʻ
Massivning o rtasi hisoblanadi: o rtasi = (chap + o ng)/2. Bu narsa uni teng
ʻ ʻ ʻ
ikkiga bo lish uchun kerak bo ladi.
ʻ ʻ
Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
Ikkinchi va uchinchi qismlarda hosil bo lgan massivlar birlashtirib chiqadi.
ʻ
Dastur:
def saralash(arr):
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr](https://docx.uz/documents/cae1173b-3033-416a-8918-a3d178ef816e/page_11.png?v=1)
Saralash algoritimi va ularni baholash