|
int partition(a: T[n], int l, int r)
T v = a[(l + r) / 2]
int i = l
int j = r
while (i ⩽⩽ j)
while (a[i] < v)
i++
while (a[j] > v)
j--
if (i ⩾⩾ j)
break
swap(a[i++], a[j--])
return j
O'rta elementni burilish sifatida tanlashda maksimal taqqoslashlar soni bilan massivni yaratish usuli
Ba'zi bir tezkor saralash algoritmlarida, ko'rib chiqilayotgan qatorning o'rtasida joylashgan element burilish sifatida tanlangan. Pivot sifatida tanlangan o'rta element bilan tezkor tartiblash Θ(n2) taqqoslashni amalga oshiradigan qatorni ko'rib chiqing. Shubhasiz, bunga eng yomon holatda erishiladi (har bir bo'lim uchun bitta qator 1 ta, ikkinchisida n - 1 ta element bo'lsa).
Dastlab, n uzunlikdagi massivni 1 dan n gacha bo'lgan elementlar bilan to'ldiring, so'ng quyidagi algoritmni qo'llang (noldan raqamlash):
void antiQsort(a: T[n])
for i = 0 to n - 1
swap(a[i], a[i / 2])
Keyin har bir qadamda eng katta element o'rta element sifatida joylashtiriladi.
Bo'limni bajarishda Θ (n) taqqoslashlar i va j indekslaridan foydalangan holda eng yaxshi Ω (n) elementlardan o'tishi (agar indekslar paydo bo'lishi bilan funktsiya ishlashni to'xtatsa), eng yomoni tufayli amalga oshiriladi. case Θ(n2) elementlari (agar ikkala indeks ham qatorni to'liq aylantirsa). Har safar indeks o'zgarganda taqqoslash amalga oshiriladi, ya'ni bo'linish protsedurasi doimiygacha) (n) taqqoslashni amalga oshiradi.
Har bir qadamda aylanma sifatida qaysi element tanlanishini ko'rib chiqing. antiQsort har bir qadamda oxirgi va markaziy elementlarni almashtiradi, shuning uchun eng katta element markazda joylashgan. Va bo'lim bu protseduraga mutlaqo nosimmetrik amallarni bajaradi, lekin teskari yo'nalishda: markaziy elementni oxirgisi bilan almashtiradi, shunda eng katta element oxirgi bo'ladi va keyin xuddi shu amalni uzunlikdagi massivda kamroq bajaradi. Ko'rinib turibdiki, eng katta element doimo asosiy element sifatida tanlanadi, chunki antiQsort istalgan uzunlikdagi massivda bo'linishga teskari operatsiyalarni bajaradi. Aslida, bo'lim boshqa yo'l bilan ishlaydigan antiQsort. Shuni ham ta'kidlash joizki, ajratish protsedurasi har qadamda elementlarning faqat bitta o'zgarishini amalga oshiradi. Birinchidan, men qatorning o'rtasiga, burilish elementiga o'taman, j oxirgi element indeksiga teng bo'lib qoladi. Keyin almashtirish sodir bo'ladi va men oxirgi elementga yetguncha yana ko'payishni boshlayman, j o'z o'rnini yana o'zgartirmaydi. Keyin vaqtdan chiqish sodir bo'ladi.
Massiv Θ (n) marta bo'linadi, chunki qism 1 va n - 1 uzunlikdagi massivlarga bajariladi, chunki bo'limning har bir bosqichida eng katta element mos yozuvlar sifatida tanlanadi (taxminiy eng yomon ish vaqti yuqorida isbotlangan). Shuning uchun, bo'limning har bir bajarilishi uchun yuqorida tavsiflangan tartibda qurilgan massivda Θ (n) bo'lim va Θ (n) taqqoslashlar amalga oshiriladi. Keyin quicksort shu tarzda qurilgan massiv uchun Θ (n2) taqqoslashni amalga oshiradi.
Determiniv burilish tanlovi uchun maksimal taqqoslashlar soni bilan massivni yaratish usuli
Qatorni qurish algoritmini ko'rib chiqing, bunda deterministik burilish tanlovi bilan tezkor saralash maksimal (bu holda Θ (n2)) taqqoslashlar sonini hosil qiladi. Ushbu taqqoslashlar soniga har bir takrorlashda uzunlik 1 va n - 1 massivlarga bo'lish orqali erishiladi. Juftlik turi elementlari bilan to'ldirilgan n uzunlikdagi a massiv yarating. Bunday element juft qiymatlarni saqlaydi (val, key), bu erda val - massiv elementi, kalit esa indeks. Dastlab a [i] elementi (0, i) shaklga ega.
Keling, ushbu qator uchun tez tartiblash algoritmini ishga tushiramiz. Ikki turdagi elementni val qiymatlari bilan taqqoslang. Har bir qadamda biz quyidagi amallarni bajaramiz: i-chi elementni k qadam raqamidagi mos yozuvlar elementi deb ataganimizda, a [i] elementi uchun val = n - k + 1 ni belgilaymiz. Keyin saralash bosqichini amalga oshiramiz. Tez saralash algoritmi tugagandan so'ng, biz qo'shimcha ravishda hosil bo'lgan juft elementlarni asosiy qiymatlar bo'yicha saralaymiz. Qidiruv mos keladigan ketma-ketlikdagi val elementlari massivi bo'ladi.
2.2,1,1 qo'llab-quvvatlash elementlarini ketma-ket tanlash bilan n = 4 uchun namuna.
1-qadam
|
2-qadam
|
3-qadam
|
4-qadam
|
5-qadam
|
6-qadam
|
7-qadam
|
1 2 3 4
0 0 0 0
|
1 2 3 4
0 4 0 0
|
1 4 3 2
0 0 0 4
|
1 2 3 4
0 0 0 4
|
1 4 3 2
0 3 0 4
|
1 3 4 2
0 0 3 4
|
1 3 4 2
0 0 3 4
|
8-qadam
|
9-qadam
|
10-qadam
|
11-qadam
|
12-qadam
|
Natija
|
|
1 3 4 2
|
Do'stlaringiz bilan baham: |
