Dastur kodi:
def partition(arr, low, high):
i = (low-1) # kichik elementlar indeksi
pivot = arr[high] # pivot
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quickSort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n-1)
print("Saralangan massiv: ")
for i in range(n):
print("%d" % arr[i])
HEAP SORT
Heap Sort, tartiblangan elementlardan iborat ro'yxatni tartiblash uchun ishlatiladigan algoritmdir. Ushbu algoritm max-heap (yoki min-heap) nomlanadigan ma'lumot strukturasidan foydalanadi. Max-heapda, har bir ota element o'z farzandlari bilan solishtirilganda katta bo'lishi shart qilinadi. Heap Sort algoritmi quyidagi tartibda ishlaydi:
1. Berilgan ro'yxatdan max-heap yaratamiz. Bu max-heap yaratish jarayoni o'z ichida max-heap shartini qanoatlantiradi: har bir ota element farzandlari bilan solishtirilganda katta bo'lishi kerak.
2. Max-heapning eng katta elementini (bu ro'yxatning birinchi elementi) o'zimiz olamiz va undan keyin o'chirib tashlaymiz. Bunday qilish bilan, eng katta element ro'yxatning oxiriga o'tkaziladi va tartiblangan bo'lgan qismi chiqariladi.
3. Ro'yxatning qoldiq qismini qayta max-heap holatiga olib boramiz.
4. 2-3-qadamni tartiblab qaytarib, ro'yxat o'zining boshidagi tartiblangan elementlar bilan to'ldiriladi.
5. Ro'yxat boshqa elementlardan iborat bo'lishi va 2-4-qadamlarni takrorlash orqali elementlarni tartiblash davom etadi.
Dastur kodi:
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [4, 2, 7, 1, 3]
heapSort(arr)
print(arr)
Ushbu kod Heap Sort ni amalga oshiradi va natijadagi tartiblangan ro'yxatni chiqaradi. "arr" nomli ro'yxatni o'zgartirib natijani ekranga chiqaradi.
Berilgan masalalar uchun eng mos saralash algoritmini tanlash uchun, masalalarning xususiyatlarini va saralash algoritmlarining xususiyatlarini taqqoslash kerak.
1.Masala: Katta sonlarni tartiblash
Xususiyatlar: Katta sonlardan iborat bo'lgan ro'yxatni tartiblash talab qilinadi.
Eng mos algoritm: Quick Sort. Bu algoritm o'rtacha vaqt hajimiga ega bo'lib, katta sonlarni qisqa vaqt ichida tartiblay oladi.
2.Masala: E'tiborli tartiblash
Xususiyatlar: Elementlardan iborat ro'yxatni e'tiborli tartiblash talab qilinadi. Masalan, ikki xususiyatni e'tibor qilish kerak bo'lishi mumkin.
Eng mos algoritm: Merge Sort. Bu algoritm yaxshi vaqt hajimiga ega bo'lib, ro'yxatni bo'sh ro'yxatlarga bo'lib birlashtirish jarayonlari orqali tartiblaydi.
3.Masala: O'zgaruvchanlikni taqqoslash
Xususiyatlar: Ro'yxatdagi o'zgaruvchanlikni taqqoslash talab qilinadi. Boshqa so'zlar bilan aytganda, qisqa bo'ylabroq ro'yxatni tartiblash kerak bo'lishi mumkin.
Eng mos algoritm: Insertion Sort. Bu algoritm odatda kichik ro'yxatlarni katta ro'yxatlarga qo'shish jarayoniga asoslanadi va o'zgaruvchanlikni taqqoslaydi.
4.Masala: Kichik ro'yxatlarni tartiblash
Xususiyatlar: Kichik ro'yxatlardan iborat bo'lgan to'plamni tartiblash talab qilinadi.
Eng mos algoritm: Selection Sort. Bu algoritm kichik ro'yxatlarni eng kichikdan boshlab tartiblaydi.
|
