Tez saralash (quick sort)
Tez tartiblash
Nomidan ko‘rinib turibdiki, Quicksort eng tezkor saralash algoritmlaridan biridir.
Quicksort algoritmi qiymatlar massivini oladi, qiymatlardan birini “pivot” element sifatida tanlaydi va boshqa qiymatlarni shunday o‘zgartiradiki, pastki qiymatlar pivot elementning chap tomonida, yuqoriroq qiymatlar esa uning o‘ng tomonida bo‘ladi.
{{ msgDone }}
Ushbu qo‘llanmada massivning oxirgi elementi pivot element sifatida tanlangan, lekin biz massivning birinchi elementini yoki massivdagi istalgan elementni ham tanlagan bo‘lardik.
Keyin, Quicksort algoritmi pivot elementning chap va o‘ng tomonidagi pastki massivlarda bir xil amalni rekursiv ravishda bajaradi. Bu massiv tartiblashtirilguncha davom etadi.
Rekursiya - funksiya o‘zini chaqirganda.
Quicksort algoritmi pivot elementini chap tomonda pastroq qiymatlari bo‘lgan pastki massiv va o‘ng tomonda yuqori qiymatlari bo‘lgan pastki massiv orasiga qo‘ygandan so‘ng, algoritm o‘zini ikki marta chaqiradi, shunda Quicksort chap tomondagi pastki massiv uchun va o‘ng tomondagi pastki massiv uchun yana ishlaydi. Quicksort algoritmi kichik massivlar tartiblash uchun juda kichik bo‘lgunga qadar o‘zini chaqirishda davom etadi.
Algoritmni quyidagicha tavsiflash mumkin:
Qanday ishlaydi:
- Asosiy element bo‘lish uchun massivdagi qiymatni tanlang.
- Massivning qolgan qismini shunday tartiblang, shunda pivot elementdan pastroq qiymatlar chapda, yuqoriroq qiymatlar esa o‘ngda bo‘lsin.
- Pivot elementini yuqori qiymatlarning birinchi elementi bilan almashtiring, shunda pivot elementi pastki va yuqori qiymatlar orasiga tushadi.
- Pivot elementining chap va o‘ng tomonidagi kichik massivlar uchun xuddi shunday amallarni (rekursiv) bajaring.
Qo‘lda yugurish
Quicksort algoritmini dasturlash tilida amalga oshirishdan oldin, keling, qisqa massivni qo‘lda bajaramiz, shunchaki fikrni tushunish uchun.
1-qadam: Biz tartiblanmagan massivdan boshlaymiz.
[ 11, 9, 12, 7, 3]
2-qadam: Biz asosiy element sifatida oxirgi 3 qiymatini tanlaymiz.
[ 11, 9, 12, 7, 3]
3-qadam: Massivdagi qolgan qiymatlar hammasi 3 dan katta va 3 ning o‘ng tomonida bo‘lishi kerak. 3 ni 11 bilan almashtiring.
[ 3, 9, 12, 7, 11]
4-qadam: 3-qiymat endi to‘g‘ri holatda. Biz qiymatlarni 3 ning o‘ng tomoniga saralashimiz kerak. Yangi pivot element sifatida oxirgi qiymat 11 ni tanlaymiz.
[ 3, 9, 12, 7, 11]
5-qadam: 7 qiymati pivot qiymati 11 ning chap tomonida, 12 esa uning o‘ng tomonida bo‘lishi kerak. 7 va 12 ni siljiting.
[ 3, 9, 7, 12, 11]
6-qadam: 11ni 12 bilan almashtiring, shunda pastroq qiymatlar 9 va 7 11 ning chap tomonida, 12 esa o‘ng tomonda bo‘ladi.
[ 3, 9, 7, 11, 12]
7-qadam: 11 va 12 to‘g‘ri pozitsiyalarda. Biz 11 ning chap tomonidagi [ 9, 7] kichik massivda pivot element sifatida 7 ni tanlaymiz.
[ 3, 9, 7, 11, 12]
8-qadam: Biz 9 ni 7 ga almashtirishimiz kerak.
[ 3, 7, 9, 11, 12]
Va endi, massiv tartiblangan.
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
Python-da Quicksort-ni qo‘llash
Massivni qisqaroq va qisqaroq pastki massivlarga ajratadigan "tezkor Sort" usulini yozish uchun biz rekursiyadan foydalanamiz. Bu shuni anglatadiki, "quickSort" usuli o‘zini pivot elementining chap va o‘ng tomonidagi yangi pastki massivlar bilan chaqirishi kerak. Rekursiya haqida ko‘proq o‘qing.
Python dasturida Quicksort algoritmini amalga oshirish uchun bizga kerak:
- Saralash uchun qiymatlari bo‘lgan massiv.
- Agar pastki massivning o‘lchami 1 dan katta bo‘lsa, o‘zini (rekursiya) chaqiradigan QuickSort usuli.
- Quyi massivni qabul qiladigan, qiymatlarni harakatlantiruvchi, pivot elementni pastki massivga almashtiradigan va pastki massivlarda keyingi bo‘linish sodir bo‘ladigan indeksni qaytaradigan bo‘lim usuli.
Olingan kod quyidagicha ko‘rinadi:
Misol
Python dasturida Quicksort algoritmidan foydalanish:
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i += 1
array[i], array[j] = array[j], array[i]
array[i+1], array[high] = array[high], array[i+1]
return i+1
def quicksort(array, low=0, high=None):
if high is None:
high = len(array) - 1
if low < high:
pivot_index = partition(array, low, high)
quicksort(array, low, pivot_index-1)
quicksort(array, pivot_index+1, high)
mylist = [64, 34, 25, 5, 22, 11, 90, 12]
quicksort(mylist)
print(mylist)
Misolni ishga tushirish »
Tez tartiblash vaqtining murakkabligi
Quicksort uchun eng yomon holat stsenariysi \(O(n^2) \). Bu pivot elementi har bir kichik massivdagi eng yuqori yoki eng past qiymat bo‘lsa, bu ko‘plab rekursiv chaqiruvlarga olib keladi. Yuqoridagi dasturimiz bilan bu massiv allaqachon tartiblangan bo‘lsa sodir bo‘ladi.
Ammo o‘rtacha hisobda Quicksort uchun vaqt murakkabligi aslida faqat \(O(n \log n) \), bu biz ko‘rib chiqqan avvalgi tartiblash algoritmlariga qaraganda ancha yaxshi. Shuning uchun Quicksort juda mashhur.
Quyida o‘rtacha \(O(n \log n) \) stsenariysi bo‘yicha Quicksort uchun vaqt murakkabligining sezilarli yaxshilanishini ko‘rishingiz mumkin, oldingi “Bubble”, “Tanlash” va “Qo‘shish” vaqt murakkabligi bilan tartiblash \(O(n^2) \) bilan solishtirganda:
Quicksort algoritmining rekursiya qismi aslida o‘rtacha saralash stsenariysi juda tez bo‘lishining sababidir, chunki pivot elementni yaxshi tanlash uchun algoritm har safar o‘zini chaqirganda massiv biroz teng ravishda yarmiga bo‘linadi. Shunday qilib, \(n \) qiymatlar soni ikki barobar bo‘lsa ham, rekursiv chaqiruvlar soni ikki baravar ko‘paymaydi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!