MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI "KOMPYUTER INJINIRING" FAKULTETI
“Algoritmlarni loyihalash” fanidan
MUSTAQIL ISHI-4
Tayyorladi: 21_08-guruh talabsi
Ramazonov Jamshid
Samarqand 2023.
Belgilardan iborat massiv berilgan. Massivni Quick sort algoritmi bo’yicha saralang
Quyidagi Quick sort algoritmi orqali belgilardan iborat massivni saralashingiz mumkin:
Quick sort algoritmi rekursiv ravishda ishlaydi. Boshlash uchun saralashni boshlang'ich indeksidan va oxirgi indeksidan belgilab boshlaymiz.
Saralash uchun birorta "pivot" elementni tanlaymiz. Odatda, massivning o'rta elementini pivot sifatida tanlash qo'llaniladi. Bunday holatda, massivning boshlang'ich indeksidan, oxirgi indeksidan va o'rta indeksidan olgan belgilar orqali pivot belgini topamiz.
Pivot belgisi orqali massivni ikki qismini ajratamiz. Bir tomonida pivotdan kichik elementlar, ikkinchisida esa pivotdan katta elementlar bo'lishi kerak. Bu amalni bajarish uchun boshlang'ich indeksdan boshlab yurgizib, pivotdan kichik belgini topishimiz va ikkinchisida oxirgi indeksdan boshlab yurgizib, pivotdan katta belgini topishimiz. Agar bitta belgi kamayib ketgan bo'lsa, ularni almashtiramiz.
Keyingi qadamda, pivot belgasi o'rta joyga keladi va massivni ikki qisimiga ajratgan holda pivot belgisini tanlangan qismga o'rnatamiz.
Qismlar bo'lganidan so'ng, rekursiv ravishda qismlarni Quick sort algoritmi orqali saralashni davom ettiramiz. Bunda har bir qisimning boshlang'ich va oxirgi indekslaridan foydalanamiz.
Algoritmdan foydalanib massivni saralab chiqishimiz uchun, massivning boshlang'ich va oxirgi indekslaridan boshlab qadam qo'shamiz.
Quyidagi Python kodi orqali Quick sort algoritmini amalga oshirishimiz mumkin:
python
Copy code
def quick_sort(arr, low, high):
if low < high:
# pivot belgisini topamiz
pivot_index = partition(arr, low, high)
# Qismlarni rekursiv ravishda saralash
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
# pivot belgisini tanlaymiz
pivot = arr[high]
# pivotdan kichik belgilarni ajratamiz
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Pivot belgisini o'rta joyga joylashtiramiz
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# Massivni test qilish
arr = [8, 3, 1, 9, 5]
n = len(arr)
# Quick sort algoritmini chaqirish
quick_sort(arr, 0, n - 1)
# Natijani chiqarish
print("Saralangan massiv:", arr)
Ushbu kodi ishga tushirgandan so'ng, arr massivi saralgan holatda chiqadi.
|
