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

Misol: MergeSort(A,1,10)

Birlashtirish tartibi

Qo'shimcha xotirani jalb qilmasdan birlashtirib bo'lmaydi.
1) Maylin1= q-p+1 - A[p..q] dagi elementlar soni, an2= rq - A[q+1..r] dagi elementlar soni. Vaqtinchalik massivlarni yarating B sn1elementlar va C bilann2elementlar va A[p..q] dan elementlarni tartibini buzmagan holda B massivga, A[q+1..r] dan elementlarni C massivga ko‘chiring.
2) B va C massivlar elementlarini A[p..r] pastki massivga qaytadan ko‘chiring, B va C massivlar elementlarini ketma-ket taqqoslab, ularning minimalini nusxalash.
3) Har safar massivlardan biri to'liq tugaydimi yoki yo'qligini tekshirmaslik uchun biz B va C massivlarning o'ng uchiga qo'shimcha elementni joylashtiramiz, bu boshqa elementlardan aniq kattaroqdir, ya'ni. qandaydir cheklovchi. B va C massivlarining barcha elementlari asl massivga ko'chirilganda, ular hali ham asl massivga tushmaydigan eng kichik elementlar sifatida chegaralovchilarga ega bo'ladi.

Pastki massivlarni birlashtirish algoritmi

Birlashtirish protsedurasi (A,p,q,r).
Kirish: A - massiv, p, q, r - A massivdagi indekslar. A[p..q] va A[q+1..r] pastki qatorlar allaqachon tartiblangan hisoblanadi.
Natija: dastlab A[p..q] va A[q+1..r] pastki massivlardagi barcha elementlarni o'z ichiga olgan tartiblangan A[p..r] kichik massiv.
Jarayon bosqichlari:
1. O'rnatishn1q-p+1 ga teng, an2— rq ga teng.
2 IN 1 ..n1+1] va C[1..n2+1] yangi massivlardir.
3. A[p..q] dan B[1.. ga nusxa ko‘chiring.n1], A[q+1..r] esa C[1..da.n2].
4. [ ga o‘rnatingn1+1] va C[n2+1] ∞ ga teng.
5. i va j ni 1 ga o‘rnating.
6. k = p dan r gacha:
A. Agar B[i] ≤ C[j] bo‘lsa, A[k] ni B[i] ga teng qilib, i ni oshiring.
tomonidan 1.
B. Aks holda (B[i] > C[j]) A[k] ni C[j] ga tenglashtiring.
va j ni 1 ga oshiring.
d(n)