Лекция 2 Алгоритмы сортировки и поиска

Tez tartiblash tartibi

Tez tartiblash (A,p,r) protsedurasi.
Kirish va natija: Birlashtirish-Sortlash protsedurasi bilan bir xil.
Jarayon bosqichlari:
1. Agar p > r bo'lsa, hech narsa qilmasdan protseduradan chiqing.
2. Aks holda, quyidagilarni bajaring:
A. Partition(A,p,r) ni chaqiring va q qiymatini belgilang
qo'ng'iroq natijasiga teng.
B. Rekursiv ravishda Quicksort (A,p,q-1) ni chaqiring.
C. Rekursiv ravishda Quicksort (A,q+1,r) ni chaqiring.
* Asosiy holat saralanadigan pastki qator ikkitadan kam elementni o'z ichiga olganida yuzaga keladi.
* Partition(A,p,r) protsedurasi A[p..r] pastki massivni ajratadi va pivot elementi joylashtirilgan joyning q indeksini qaytaradi.

Bo'lish tartibi

• Pivot element sifatida A[p..r] pastki massivdagi eng o'ng element A[r] ni tanlaymiz.
• Keyin biz pastki qatorni chapdan o'ngga takrorlaymiz, har bir elementni pivot bilan taqqoslaymiz.

Bo'lish tartibi

Protsedura bo'limi (A,p,r).
Kirish: Birlashtirish-Sortlash bilan bir xil.
Natija: A[p..r] elementlarining oʻrin almashishi shundayki, A[p..q-1] dagi har bir element koʻpi bilan A[q] va A[q+1..r] dagi har bir element kattaroq boʻladi. A[q ] ga qaraganda. q indeksining qiymatini qaytaradi.
Jarayon bosqichlari:
1. q ni p ga tenglashtiring.
2. u = p dan r-1 gacha:
A. Agar A[u] ≤ A[r] bo‘lsa, A[q] ni A[u] bilan almashtiring va keyin oshiring.
q 1 ga.
3. A[q] va A[r] ni almashtiring va keyin q ni qaytaring.
Har bir elementni mos yozuvlar bilan bir marta taqqoslash amalga oshiriladi va har bir element uchun bittadan ko'p bo'lmagan almashinish amalga oshiriladi, shuning uchun bo'linish jarayoni vaqti bilann-element pastki qatori t(n).

Tez saralash ish vaqti

• Eng yomon holatda, bo'lim o'lchamlari muvozanatsiz. Misol uchun, agar massiv dastlab tartiblangan bo'lsa, biz har safar A[p..r] massivni A[p..r-1] va A[r] pastki massivlarga ajratamiz. Keyin pastki qatorni saralash vaqti uchunnelementlardan takrorlanish munosabatini olamiz T(n)=T(n-1)+ D(n). Ma'lum bo'lishicha, bu holda T(n) t() shakliga egan2).
• Eng yaxshi holatda, agar har safar pastki qatorlarning har biri o'lchamga ega bo'lsan/2, keyin ish vaqti uchun takrorlanish munosabati birlashma tartiblash bilan bir xil bo'ladi: T(n)=2T(n/2)+D(n), bu T(n) t() shakliga eganjurnal2n).