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

Kiritish saralash ish vaqti

• INo'rtachahar bir element o'zidan oldingi elementlarning yarmidan ko'pi va shuningdek, ushbu elementlarning yarmidan kam bo'ladi, bu esa eng yomon holatga nisbatan ish vaqtini yarmiga qisqartiradi, ya'ni. ish vaqti saqlanib qoladi t(n2).
• Kiritish tartibi elementlarni D gacha koʻchirishi mumkin.n2) bir marta.
• Agar massiv deyarli tartiblangan bo'lsa, kiritishni tartiblash yaxshiroqdir.

Birlashtirish tartibi

Paradigma"bo'l va hukmronlik qil"
1)Ajratish. Vazifa bir xil vazifaning kichikroq namunalari bo'lgan bir nechta kichik vazifalarga bo'linadi.
2)hukmronlik. Kichik muammolar rekursiv hal qilinadi. Agar ular etarlicha kichik bo'lsa, ular asosiy holat sifatida hal qilinadi.
3)Uyushma. Kichik muammo yechimlari asl muammoning yechimiga birlashtiriladi.
q qiymatini p va r o'rtasida topib, saralanadigan pastki qatorni ajrating:
Ajratish bosqichida yaratilgan pastki qatorning har bir yarmidagi elementlarni rekursiv tartiblash (p dan q gacha va q+1 dan r gacha).
Saralangan elementlarning p dan q gacha va q+1 dan r gacha bo'lgan oraliqlarda birlashishi, shunda p-th dan r-th oralig'idagi elementlar tartiblanadi.

Birlashtirish tartiblash algoritmi

Protsedura Birlashtirish-Sort(A,p,r).
Kirish: A - massiv, p, r - A pastki massivning bosh va oxiri indekslari.
Natija: A[p..r] pastki massivning elementlari kamaymaydigan tartibda tartiblangan.
Jarayon bosqichlari:
1. Agar p≥r bo'lsa, A[p..r] pastki massivda ko'pi bilan bitta element mavjud, shuning uchun u avtomatik ravishda tartiblanadi. Biz protseduradan hech qanday harakat qilmasdan qaytamiz.
2. Aks holda, quyidagi amallarni bajaring:
A. O'rnatish
B. Rekursiv ravishda Merge-Sort(A,p,q) deb nomlanadi.
C. Birlashtirish-Sort(A,q+1,r) ni rekursiv chaqirish.
D. Chaqiruv Birlashtirish (A, p, q, r).
Asosiy holat r ≥ r bo'lganda. Birlashtirish (A, p, q, r) protsedurasi tartiblangan kichik massivlarni bitta tartiblangan kichik massiv A[p..q] ga birlashtiradi.