Ma’lumotlar tuzilmasi va algoritmlar” fanidan 4- laboratoriya is hini bajarishga namuna

Algoritmi:
arr [] = 64 25 12 22 11
// arrdagi minimal elementni toping [0 ... 4]
// uni boshiga qo'ying 11 25 12 22 64
// arrdagi minimal elementni toping [1 ... 4 ]
// va uni arr boshiga qo'ying [1 ... 4]
11 12 25 22 64
// arrdagi minimal elementni toping [2 ... 4]
// va uni arrning boshiga qo'ying [2 .. .4]
11 12 22 25 64
// arrdagi minimal elementni toping [3 ... 4]
// va uni arr [3 ... 4] boshiga joylashtiring
11 12 22 25 64
Dastur kodi:
A = [64, 25, 12, 22, 11]
# Barcha massiv elementlari bo'ylab harakatlaning
for i in range(len(A)):
# Qolganlardan minimal elementni toping
min_idx = i
for j in range(i+1, len(A)):
if A[min_idx] > A[j]:
min_idx = j
A[i], A[min_idx] = A[min_idx], A[i]
print ("Saralangan massiv: ")
for i in range(len(A)):
print("%d" %A[i])
Algoritm samaradorligi:
 Taqqoslashlar soni:
 Almashtirishlar soni:
 Massiv teskari tartiblanganda o'rinlashtirishlar soni
Ushbu usul bo'yicha saralash bajarilsa, eng yomon holda taqqoslashlar va o'rinlashtirishlar soni tartibi n2 bo'ladi.
1.3. To'g'ridan-to'g'ri almashtirish, pufaksimon saralash (Bubble sort) usuli
Ushbu usulning g'oyasi quyidagicha: n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo'lsa, u holda ularning o'rni almashtiriladi (6.1- rasm).
Misol : massiv: 4, 3, 7, 2, 1, 6.

2-rasm. Pufaksimon saralash usulida massiv elementlarining o'rnini almashtirish
Pufaksimon usulni massiv elementlarida pastdan yuqoriga va yuqoridan pastga o'tishni bir vaqtda amalga oshirish natijasida yaxshilash mumkin.

2-rasm. Massivni pufaksimon saralashga misol
3-rasmda berilgan misolda 5 ta elementdan iborat massiv berilgan. Demak, massivda pastdan yuqoriga (yuqoridan pastga) o'tishlar soni 5-1=4 marta bo'ladi. Misoldan ko'rinib turibdiki, algoritm ichki siklda 3-qadamdan boshlab massivni “bekor” qayta ishlaydi, 4-qadamni bajarmasa ham bo'ladi.
Berilgan usullarning afzalligi:
1) Eng sodda algoritm;
2) Amalga oshirish sodda;
3) Qo'shimcha o'zgaruvchilar shart emas.
Kamchiliklari:
1) Katta massivlarni uzoq qayta ishlaydi;
2) Har qanday holatda ham o'tishlar soni kamaymaydi.
Dastur kodi:
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [4, 3, 7, 2, 1, 6]
bubbleSort(arr)
print ("Saralangan massiv: ")
for i in range(len(arr)):
print ("%d" %arr[i])