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

1.1. To'g'ridan-to'g'ri qo'shish usuli bilan saralash algoritmi
Qo'shish orqali saralash (insertion sort)- bu qo'lda o'yin kartalarini saralash uslubiga o'xshash oddiy tartiblash algoritmi. Massiv deyarli saralangan va saralanmagan qismga bo'linadi. Tartiblanmagan qismdan qiymatlar tanlanadi va tartiblangan qismning to'g'ri joyiga joylashtiriladi.
Algoritm:
n kattalikdagi massivni o'sish tartibida saralash uchun:

1. 
   array [1] dan arr [n] ga massiv ustida takrorlang;
   
2. 
   Joriy elementni (kalitni) avvalgisiga solishtiring;
   
3. 
   Agar kalit element avvalgisidan kichik bo'lsa, uni oldingi elementlar bilan solishtiring. O'zgartirilgan element uchun joy ajratish uchun katta elementlarni bir joyga ko'taring.
   

Misol: 

1-rasm. Insertion sort algoritmi
Dastur kodi:
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >=0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print ("Saralangan massiv:")
for i in range(len(arr)):
print ("%d" %arr[i])
Algoritm samaradorligi. Faraz qilaylik, taqqoslashlar soni C, o'rinlashtirishlar soni M bo'lsin. Agar massiv elementlari kamayish tartibida bo'lsa, u holda taqqoslashlar soni eng katta bo'lib, u ga teng bo'ladi, ya'ni . O'rinlashtirishlar soni esa ga teng bo'ladi, ya’ni . Agar berilgan massiv o'sish tartibida saralangan bo'lsa, u holda taqqoslashlar va o'rinlashtirishlar soni eng kichik bo'ladi, ya’ni .
1.2. Tanlash orqali saralash (selection sort) algoritmi
Mazkur usul quyidagi tamoyillarga asoslangan:
1. Eng kichik kalitga ega element tanlanadi.
2. Ushbu element birinchi element bilan o'rin almashinadi.
3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.