Tezkor saralash algoritmlari
![#Natija:
[1,2,2,3,4,5,6,6,8]](/data/documents/1225a6d0-3902-4d52-bb6b-a72c2e4aabc4/page_8.png)
![Dasturi:
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
x = arr.pop() # choosing the last element as pivot
a = []
b = []
for i in arr:
if i <= x:
a.append(i)
else:
b.append(i)
return quicksort(a) + [x] + quicksort(b)
arr = [2,6,3,1,6,5,2,4,8]
print(quicksort(arr))](/data/documents/1225a6d0-3902-4d52-bb6b-a72c2e4aabc4/page_9.png)
Mavzu: Tezkor saralash algoritmlari Reja: 1. KIRISH: 2.A SOSIY QISM: Qo’llanilishi Dasturi Blok sxemasi 3.XULOSA:
KIRISH: Informatika yoki matematikada algoritmlar aniq va aniq muammoni hal qilishning bosqichma-bosqich jarayonini ta'minlaydi. Ular odatda raqamlarni saralash, mashinani o'rganish yoki ma'lumotlarni ekranda ko'rsatish kabi turli xil vazifalar uchun ishlatiladi. Vaziyatni istiqbolga qaratish uchun, yeryong'oqli sendvich tayyorlash uchun barcha qadamlaringizni o'ylab ko'ring, agar biz bu jarayonni avtomatlashtirsak, yeryong'oqli sendvich tayyorlamoqchi bo'lganingizda, xuddi shu jarayonni ongsiz ravishda bajarayotganingizni sezasiz. , biz bir xil qadamlardan foydalanamiz. Bu algoritmlar ortidagi umumiy fikr. Tezkor saralash Quicksort - bu joy-joyida saralashning samarali algoritmi bo'lib, u yaxshi amalga oshirilganda birlashtirish va yig'indili saralashdan ikki-uch baravar tezroq ishlaydi. Tezkor saralash - bu taqqoslash turi bo'lib, u kamroq munosabat aniqlangan har qanday turdagi elementlarni saralash imkonini beradi. Samarali ilovalarda odatda barqaror tur emas. Quicksort, o'rtacha, n ta elementni saralash uchun O(n.log(n)) taqqoslashlarini amalga oshiradi. Eng yomon holatda, u O (n2) taqqoslashni amalga oshiradi, garchi bu xatti-harakatlar juda kam uchraydi. Quicksort qanday ishlaydi? Quicksort - bu Bo'l va bosib ol algoritmi. Barcha “bo‘l va zabt et” algoritmlari singari, u avval katta massivni ikkita kichikroq kichik massivlarga ajratadi, so‘ngra kichik massivlarni rekursiv saralaydi. Umuman olganda, butun jarayon uchta bosqichni o'z ichiga oladi: Pivot tanlash: massivdan pivot deb ataladigan elementni tanlang (odatda bo'limning eng chap yoki eng o'ng elementi). Bo'limlar: massivni shunday tartiblangki, qiymatlari pivotdan kichik bo'lgan barcha elementlar pivotdan oldin keladi. Aksincha, pivotdan kattaroq qiymatga ega bo'lgan barcha elementlar undan keyin keladi. Teng qiymatlar ikkala
tomonga ham borishi mumkin. Ushbu bo'linishdan so'ng, pivot oxirgi holatidadir. Takrorlash: Yuqoridagi qadamlarni aylanmadan kichikroq qiymatlarga ega bo'lgan elementlarning pastki qatoriga va pivotdan kattaroq qiymatlarga ega bo'lgan elementlarning pastki qatoriga alohida qo'llang. Rekursiyaning asosiy holati 1 o'lchamdagi massivlar bo'lib, ularni hech qachon tartiblash kerak emas. Quyidagi diagrammada biz Quicksort algoritmining har bir bosqichida eng chap elementni pivot sifatida qanday tanlashimiz, massivni pivot bo‘ylab taqsimlash va bo‘lish jarayonidan so‘ng olingan ikkita kichik massivda takrorlash ko‘rsatilgan: Tezkor saralash ishlashi Quicksort ning eng yomon vaqt murakkabligi O(n2), bu erda n - kirish hajmi. Eng yomon holat, pivot ro'yxatdagi eng kichik yoki eng katta element bo'lganda yoki barcha massiv elementlari teng bo'lganda sodir bo'ladi. Bu eng muvozanatsiz bo'limga olib keladi, chunki pivot massivni 0 va n-1 o'lchamdagi ikkita pastki qatorga ajratadi. Agar bu har bir bo'limda qayta-qayta sodir bo'lsa (aytaylik, biz massivni tartibladik), u holda har bir rekursiv qo'ng'iroq avvalgi ro'yxatdan bir kichikroq o'lchamdagi ro'yxatni qayta ishlaydi, natijada O(n2) vaqt. Tezkor saralash algoritmi Britaniyalik kompyuter olimi Toni Xoar 1959 yilda QuickSort algoritmini ixtiro qildi. "Tezkor tartiblash" nomi ma'lumotlar elementlari ro'yxatini boshqa saralash usullariga qaraganda ancha tezroq (ikki yoki uch barobar tezroq) saralashi mumkinligidan kelib chiqqan. Quicksort eng samarali saralash algoritmlaridan biridir. U massivni (bo'limni) kichikroqlarga bo'lish va kichikroqlarini almashtirish (almashtirish) orqali ishlaydi. Tez saralash murakkabligi Quicksort o'zining ta'sirchan o'rtacha ishlashi bilan mashhur bo'lib, uni katta ma'lumotlar to'plamlarini saralash uchun mashhur tanlovga aylantiradi. Bu qulay o'rtacha vaqt murakkabligi va kompyuter fanining turli sohalarida ko'p
qirrali ilovalarga ega kuchli saralash algoritmidir. Uning murakkabligini tushunish va bir nechta dasturlash tillarida kodni amalga oshirish talabalar va mutaxassislar uchun qimmatli bo'lishi mumkin, bu ularga Quicksort samaradorligidan o'z loyihalari va ilovalarida foydalanish imkonini beradi. Massivni saralash informatika fanining klassik "Algoritmlar va ma'lumotlar tuzilmalari" kursida o'rganilgan birinchi jiddiy muammolardan biridir. Shu munosabat bilan, yozish turlari va tegishli savollar ko'pincha stajyor yoki kichik ishlab chiquvchi lavozimiga intervyu paytida topiladi. Muammoni shakllantirish An'anaga ko'ra, muammoni hal qilish usullarini taqdim etishni uning bayonoti bilan boshlash kerak. Odatda, saralash vazifasi ba'zi bir butun sonlar massivlarini o'sish tartibida tartiblashni o'z ichiga oladi. Lekin, aslida, bu biroz soddalashtirilgan. Ushbu bo'limda keltirilgan algoritmlar o'rtasida tartib munosabatlari o'rnatiladigan har qanday ob'ektlar massivini tartibga solish uchun ishlatilishi mumkin (ya'ni har qanday ikkita element haqida biz aytishimiz mumkin: birinchisi ikkinchisidan, ikkinchisi birinchisidan kattaroq). , yoki ular teng). Siz o'sish yoki kamayish tartibida saralashingiz mumkin. Biz standart soddalashtirishdan foydalanamiz. Tez tartiblash Oxirgi marta biz biroz murakkabroq tur - qo'shish turi haqida gapirgan edik. Bugun biz ancha murakkab algoritm - tez tartiblash (hoare sort deb ham ataladi) haqida gaplashamiz. Algoritmning tavsifi Tez tartiblash algoritmi rekursivdir, shuning uchun soddaligi uchun protsedura l inklyuzivdan r inklyuzivsizgacha bo'lgan massiv bo'limi chegaralarini kiritadi. Ko'rinib turibdiki, butun massivni saralash uchun l parametri sifatida 0 ni, r parametri sifatida n ni o'tkazish kerak, bu erda an'anaga ko'ra, n massiv uzunligini bildiradi. Tez tartiblash algoritmi bo'lish tartibiga asoslanadi. Bo'lim massivning ba'zi elementini tanlaydi va massiv bo'limining elementlarini shunday tartibga soladiki, massiv 2 qismga bo'linadi: chap qismda bu elementdan kichik bo'lgan
elementlar, o'ng qismida esa undan katta yoki teng bo'lgan elementlar mavjud. bu element. Ushbu bo'linuvchi element pivot deb ataladi. Massivdan “aylanuvchi” elementni tanlaydigan va qolgan elementlarni ikkita pastki qatorga bo‘luvchi o‘z joyida tartiblash algoritmi. Pivotdan kichik elementlar chap pastki qatorga o'tkaziladi va pivotdan kattaroq elementlar o'ng pastki qatorga o'tkaziladi. Algoritm ushbu pastki qatorlarni rekursiv tarzda tartiblaydi. O'rtacha, tezkor saralash O(nlog(n)) vaqtida ishlaydi. Tez tartiblash algoritmi nima? Quicksort algoritmi Toni Hoare tomonidan yaratilgan va 1961 yilda nashr etilgan bo‘lish va zabt etish algoritmidir. U asosiy elementni (ro‘yxatni bo‘lish uchun boshqa elementlarni solishtirish uchun foydalaniladigan ro‘yxatdagi element) tanlash orqali ishlaydi. birinchi, oxirgi, tasodifiy yoki median element bo'lib, barcha kichikroq elementlarni pivotning chap tomoniga va barcha kattaroq elementlarning o'ng tomoniga joylashtiring. Bu har bir iteratsiya kirish ro'yxatini ikkita ro'yxatga bo'lish (bo'lish) ma'nosida bo'ladi, ulardan biri pivotning chap tomonidagi qiymati kichikroq barcha elementlarni, ikkinchisi esa o'ng tomonidagi barcha kattaroq elementlarni o'z ichiga oladi. aylanish. Keyin ikkala ro'yxat yoki massivni qayta birlashtirishdan oldin ularni rekursiv saralaydi va shu bilan ro'yxatni samarali saralaydi. Bu hali ham mavjud bo'lgan eng samarali umumiy maqsadli saralash algoritmlaridan biri hisoblanadi. Bu erda ikkita narsaga e'tibor berish kerak: bo'lim va rekursiya. Bo'lim - bu saralash algoritmidagi sendvichdagi yeryong'oq moyi; biz kiritilgan ro'yxatni shunday tartibda joylashtiramiz va rekursiya oddiygina shart bajarilmaguncha va ro'yxat tartiblashtirilguncha algoritmni takrorlashni anglatadi. Tezkor saralash algoritmi uchun qadamlar: 1-qadam - Siz foydalanayotgan bo'lim algoritmiga qarab pivot elementini tanlang