4.3-4-lab_slaydedewdewdewdewdewdeedd.pptx

deded

1. “ Ma’lumotlar tuzilmasi va algoritmlar ” fanidan 4-LABORATORIYA ISHI BAJARISHGA NAMUNA (2-kurslar uchun ) Fan o‘qituvchisi: Ass.Ibrohimova Z.E .

2. 4.3. Saralashning yaxshilangan usullari va ularning qo‘llanilishi Rejalashtirildi : Spaghetti sort algoritmi . Radix sort algoritmi . Hisoblash (counting) sort algoritmi .

3. Spaghetti sort algoritmi

4. 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 . Spaghetti sort algoritmi

5. a=[4,18,12,11,16,17,19] def spagetti (a): aa=[] while len (a)>0: bb=max(a) ss = a.index (bb) a.pop ( ss ) aa.append (bb) return aa nat = spagetti (a) print( nat [::-1 ]) Spaghetti sort algoritmi

6. Spaghetti sort algoritmi Algoritm nomi : Spagetti turi Muallifi: Aleksandr Dyudni Yili: 1984 yil Sinfi: Parallel turlar Davomiyligi: Ha Taqqoslashlar soni: Yo'q Samaradorligi O (n)

7. 2. Radix saralash algoritmi

8. Metodologiyasi . Radix Sortning qiziqarli tomoni shundaki , ko'pgina tartiblash algoritmlaridan farqli o'laroq , u taqqoslashga asoslanmaydi . Ya'ni , saralangan qiymatlar o'rtasida to'g'ridan-to'g'ri taqqoslash yo'q . Yana bir qiziq jihat shundaki , Radix sortda faqat raqamlardan tashqari boshqa turdagi ma’lumotlarni ham samarali saralash uchun foydalanish mumkin , masalan , satrlar . 2. Radix saralash algoritmi

9. def num_digits ( arr ): maxDigit = 0 for num in arr : maxDigit = max( maxDigit , num ) return len ( str ( maxDigit )) from functools import reduce def flatten( arr ): return reduce(lambda x, y: x + y, arr ) def radix( arr ): digits = num_digits ( arr ) for digit in range(0, digits): temp = [[] for i in range(10 )] 2. Radix saralash algoritmi for item in arr : num = (item // (10 ** digit)) % 10 temp[ num ].append(item) arr = flatten(temp) return arr array = [55, 45, 3, 289, 213, 1, 288, 53, 2] array = radix(array) print(array)

10. Algoritm nomi : Radiksli tartiblash Muallifi: Xarold H. Seward Yili: 1954 yil Sinfi: Tarqatish saralash Barqarorligi: Yo'q Taqqoslashlar soni: Yo'q Vaqtning murakkabligi: Eng yomoni O ( n × k ) Eng yaxshi O ( n ) Samaradorligi: O( n+k ) 2. Radix saralash algoritmi

11. 3.Hisoblash (counting) sort algoritmi

12. Algoritmi g’oyasi . Massivda har bir qiymat necha marta takrorlanishini hisoblaymiz va massivni tegishli miqdorlarda hisoblangan elementlar bilan to'ldiramiz .  Raqamlarning butun diapazoni uchun hisoblagichlar oldindan yaratiladi ( dastlab nolga teng ). Metodologiyasi . Hispblash saralash algoritmi qiymatlarni solishtirishni talab qilmaydigan tartiblash algoritmlari toifasiga kiradi . Bunday turlar taqqoslanmaydigan turlar deb nomlanadi . Buning o'rniga , hisoblash tartibi ro'yxatdagi har bir qiymatning pozitsiyalarini to'g'ri baholashning juda qiziqarli va murakkab usulidan foydalanadi . 3.Hisoblash (counting) sort algoritmi

13. def counting(data): counts = [0 for i in range(max(data)+1)] print(counts) for value in data: counts[value] += 1 print(counts) for index in range(1, len (counts)): counts[index] = counts[index-1] + counts[index] print(counts ) 3.Hisoblash (counting) sort algoritmi arr = [0 for loop in range( len (data))] for value in data: index = counts[value] - 1 arr [index] = value counts[value] -= 1 return arr data = [2, 7, 16, 20, 15, 1, 3, 10] print(counting(data))

14. Algoritm nomi: Hisoblash tartibi Muallifi: Xarold H. Sevard Yili: 1954 yil Sinfi: Tarqatish saralash Barqarorligi: Ha Taqqoslashlar soni: Yo'q Vaqtning murakkabligi: Eng yomoni O  ( n+k ) O'rtacha O  ( n+k ) Eng yaxshi O ( n ) Samaradorligi: General O ( n + k ) Qo'shimcha O ( k ) 3.Hisoblash (counting) sort algoritmi

15. E’tiboringiz uchun rahmat !!! Laboratoriya topshiriqlarini vaqtida bajaring va mustaqil bilimga ega bo’lin !!!

16. “ Ma’lumotlar tuzilmasi va algoritmlar ” fanidan 4-LABORATORIYA ISHI BAJARISHGA NAMUNA (2-kurslar uchun ) Fan o‘qituvchisi: kat.o‘q. Kudratov R.B .

17. 4.4. Piramidali va birlashtirish orqali saralash Rejalashtirildi : Piramidali (Heapsort) saralash algoritmi . " Xanoy minorasi " saralash algoritmi . Birlashtirish orqali (Merge sort) algoritmi .

18. 1. Piramidali (Heapsort) saralash algoritmi

19. Saralash mohiyati : Kirishdan maksimal yig'in hosil qiling . Bu nuqtada , eng katta element uyumning ildizida saqlanadi .  Uni to'pning oxirgi elementi bilan almashtiring va keyin uning hajmini 1 ga kamaytiring . Nihoyat , hosil bo'lgan daraxtni yangi ildizga ega bo'lgan maksimal - to'pga aylantiring . Daraxt hajmi 1 dan katta bo'lguncha yuqoridagi amallarni takrorlang . 1. Piramidali (Heapsort) saralash algoritmi

20. def heapsort( alist ): build_max_heap ( alist ) for i in range( len ( alist ) - 1, 0, -1): alist [0], alist [ i ] = alist [ i ], alist [0] max_heapify ( alist , index=0, size= i ) def parent( i ): return ( i - 1)//2 def left( i ): return 2* i + 1 def right( i ): return 2* i + 2 def build_max_heap ( alist ): length = len ( alist ) start = parent(length - 1) while start >= 0: max_heapify ( alist , index=start, size=length) start = start - 1 1. Piramidali (Heapsort) saralash algoritmi def max_heapify ( alist , index, size): l = left(index) r = right(index) if (l < size and alist [l] > alist [index]): largest = l else: largest = index if (r < size and alist [r] > alist [largest]): largest = r if (largest != index): alist [largest], alist [index] = alist [index], alist [largest] max_heapify ( alist , largest, size) alist = input(" Ro'yxat elementlarni kiriting : ").split() alist = [ int (x) for x in alist ] heapsort( alist ) print(" Saralangan ro'yxat : ", end='') print( alist )

21. Algoritm nomi : Piramidali saralash (Heap sort, Пирамидальная сортировка, Pyramid sort) Muallifi: J. Uilyams Yili: 1964 yil Sinfi: Tanlovni saralash Barqarorligi: Yo'q Taqqoslash soni: Ha Vaqtning murakkabligi: Eng yaxshi O (n*log n) O'rtacha Eng yomoni Samaradorligi: General O(n) Qo'shimcha O(1) 1. Piramidali (Heapsort) saralash algoritmi

22. 2. " Xanoy minorasi " saralash algoritmi

23. 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  n  -1)  vaqt murakkabligiga ega  (n bo'ladi ). Algoritmi . Keling , jumboqning yagona shartini o'zgartiraylik : birinchi novda disklarni istalgan tartibda bog'laymiz .  Qolgan qoidalarni o'zgarishsiz qoldiramiz . Ushbu qoidalarga muvofiq disklarni birinchi novdadan boshqasiga o'tkazish , agar siz disklarning diametrlarini raqamlar sifatida talqin qilsangiz , tartiblash jarayonidan boshqa narsa emas . 2. "Xanoy minorasi" saralash algoritmi

24. def hanoy_sorted ( arr , x, y): if len ( arr ) == 1: print( arr [0], x, y) elif len ( arr ) > 1: hanoy_sorted ( arr [1:], x, 6 - x - y) print( arr [0], x, y) hanoy_sorted ( arr [1:], 6 - x - y, y) def merge(arr1, x, arr2, y): if len (arr2) == 0: hanoy (arr1, x, y) elif len (arr1) > 0: n = arr1[-1] j = len (arr2) - 1 if n < arr2[-1]: print(arr1[-1], x, y) j = len (arr2) else: for i in range(0, len (arr2)): if n > arr2[ i ]: j = i + 1 break 2. " Xanoy minorasi " saralash algoritmi hanoy_sorted (arr2[j - 1:], y, x) hanoy_sorted ([n] + arr2[j - 1:], x, y) arr2.insert(j, n) merge(arr1[: len (arr1) - 1], x, sorted(arr2)[::-1], y) def hanoy ( arr , x, y): if len ( arr ) == 1: print( arr [0], x, y) if len ( arr ) > 1: mi = arr.index (max( arr )) up = arr [mi + 1:] z.append (up[:]) hanoy (z[-1], x, 6 - x - y) print( arr [mi], x, y) merge( arr [:mi], x, sorted(up)[::-1], 6 - x - y) arr.remove ( arr [mi]) hanoy_sorted (sorted( arr )[::-1], 6 - x - y, y) del z[-1] n = int (input(" Ro'yxat elementlarini sonini kiriting : ")) arr = list(map( int , input(" Ro'yxat elementlarini kiriting :").split()))[::-1] z = [] hanoy ( arr , 1, 3 )

25. Algoritm nomi : "Ханойская башня"(Tower of Hanoi sort, Hanoi sort) Muallifi : Edvard Lyuka Sinfi: Ezoterik saralash Barqarorligi: Mavjud Vaqtning murakkabligi : Eng yomoni O (2  n  -1 ) O'rtacha O (exp(n)) Eng yaxshi O (n) Samaradorligi: Qo'shimcha O (n) 2. " Xanoy minorasi " saralash algoritmi

26. 3. Birlashtirish orqali (Merge sort) algoritmi

27. 3. Birlashtirish orqali (Merge sort) algoritmi

28. 3. Birlashtirish orqali (Merge sort) algoritmi

29. 3. Birlashtirish orqali (Merge sort) algoritmi