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](/data/documents/3b0df745-c454-42d9-b9eb-10051dd0a0fa/page_6.png)
![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]](/data/documents/3b0df745-c454-42d9-b9eb-10051dd0a0fa/page_7.png)
![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](/data/documents/3b0df745-c454-42d9-b9eb-10051dd0a0fa/page_8.png)
![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“
ʻ](/data/documents/3b0df745-c454-42d9-b9eb-10051dd0a0fa/page_9.png)
![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=[]](/data/documents/3b0df745-c454-42d9-b9eb-10051dd0a0fa/page_10.png)
![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](/data/documents/3b0df745-c454-42d9-b9eb-10051dd0a0fa/page_11.png)
Saralash algoritimi va ularni baholash Reja : I.Kirish . II.Saralash algoritmlari. 1.Saralash algoritmlarining ahamiyati. 2.Saralash algoritmlarining turlari. III.Xulosa. IV.Foydalanilgan adabiyotlar.
KIRISH Saralash tushunchasi Saralash - tartiblash (Sorting algorithms) deb, berilgan obyektlar ketma-ketligini ma’lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi.Python tilida saralash algoritmlari,bir qator yoki ro’yxatdagi elementlarni ma’lum bir tartibda saralash uchun ishlatiladi.Saralash bir nechta ko'rsatkichlarga bog'liq bo'lishi mumkin. Misol uchun maktab jurnalida o'quvchilar familiyasi alifbo tartibiga ko'ra saralangan bo'ladi. Masalan, bizga sonlar qatori berilgan: 8,23,0,-50,100 bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashishimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi Saralash algoritmlari ko'p va xilma-xil. Saralash algoritmlari ikki tipga bo'linadi. - O() vaqtda saralovchi algoritmlar. Yani kvadratik amallar talab qiladigan algoritmlar - O(n*log(N)) vaqtda saralovchi algoritmlar. Logarifmik amallar soni talab qiladigan algoritmlar Shu yerning o’zida 2ta saralashdan foydalanilyapti. Biri, bo’y uzunligi bo’yicha, ikkinchisi sinf jurnalidagi o’rinlar bo’yicha. Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz): Sonlar berilishi: 23, 54, 3, 22, 1, 45; Eng kattasini boshiga o’tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o’z o’rnida turibdi) Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)
Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi) Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100 Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana shu algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni ro'yxatning boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz. Saralash asosan ro'yxat, massiv elementlarida amalga oshiriladi. Masalan sinfda 5 ta o'quvchi bor. Ularni familiyasini alifbo tartibida saralash mumkin. Sonlar berilishi: 23, 54, 3, 22, 1, 45; Eng kattasini boshiga o’tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o’z o`rnida turibdi) Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi) Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi) Saralangan tartib quyidagi holatga keldi: 1, 3, 22, 23, 45, 54; Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100 Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana shu algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni ro'yxatning boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz. Eng kattasini boshiga o’tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o’z
o`rnida turibdi) Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi) Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi) Saralangan tartib quyidagi holatga keldi: 1, 3, 22, 23, 45, 54; Saralash asosan ro'yxat, massiv elementlarida amalga oshiriladi. Masalan sizning sinfingizda 5 ta o'quvchi bor. Ularni familiyasini alifbo tartibida saralash mumkin. Demak, miyamiz xuddi shu jarayonni takrorlar ekan. Endi bizga ma’lumki, bizning miyamiz o’zi optimal deb bilgan yo’nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo’lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo’ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o’rinda savol tug’iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o’zgartirilgan sanasi va o’lchami. Har birini o’sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho’qqiga chiqayotgan va ishlanayotgan ma’lumotlar o’lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish noqulay. Ma’lumotlar o’lchamlari esa juda katta, shu sabali ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug’ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. 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. II.Saralash algoritmlari. - Bubble sort (Pufakchali saralash) - Selection sort (Tanlab saralash) - Insertion sort (Joylashtirib saralash) - Quick sort (Tezkor saralash) - Merge sort (Qo'shib saralash) Bubble sort Bubble sort (Kabobchik saralash)- Bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar bilan solishtirishga asoslangan algoritm hisoblanadi. Unda yonma-yon turgan elementlardan chapdagisi o‘ngdagidan kattaligi aniqlansa, bu ikkala son o rni almashtiriladi. Bu jarayon almashtirish kerak bo lmay ʻ ʻ qolguncha davom etadi, ya ni barcha elementlar o‘sish tartibida bo‘lib ʼ qolguncha . Bubble sort algoritmi juda ham oddiy ishlaydi. U shunchaki array boshidan yurib ikkita qo’shni elementlarni ularning katta kichikligiga qarab joyini almashtiradi. Bu orqali har bir to’liq yurib chiqishdan keyin arraydagi eng katta (yoki eng kichik) element arrayning eng oxiriga o’tib qoladi. Ushbu xusiyatiga ko’ra bu algoritm ba’zida Sink sort (Cho’kib saralash) deb ham ataladi. Lekin, albatta, Bubble sort nomi ko’proq jarangdorroq eshitiladi.