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

Ish vaqtini saralash

• Oddiylik uchun massivning o'lchami deb faraz qilaylikn2 ning kuchi, shuning uchun har safar massivni yarmiga bo'lganimizda, pastki massivlarning o'lchamlari teng bo'ladi.
• Saralash vaqti T(n) uchta komponentdan iborat:

1) Bo'linish doimiy vaqtni oladi, chunki u faqat q indeksini hisoblashdan iborat.
2) Dominion har bir o'lchamdagi kichik massivlar uchun ikkita rekursiv chaqiruvdan iboratn/2 element, bu 2T vaqtni oladi(n/2).
3) Ikki rekursiv chaqiruv natijalarini tartiblangan pastki massivlarni birlashtirish orqali birlashtirish vaqt talab etadi D(n).

T(n)=2T(n/2)+ D(n)
Ushbu rekursiv tenglamani yechish natijasi:
T(n) t() shakliga eganjurnal2n).

Saralash algoritmlarini solishtirish

Birlashtirishning afzalliklari:
-- Ishlash vaqti bo'yicha birlashtiring [D(njurnal2n)] eng yomon ish vaqti bilan solishtirganda aniq afzaldir D(n2) tanlashni saralash va kiritishni tartiblash algoritmlari uchun.
Birlashtirish turining kamchiliklari:
-- Qo'shimcha xotira talab qiladi: Saralash butun kirish massivining to'liq nusxalarini yaratadi. Agar xotiradan foydalanish masalasi ustuvor bo'lsa, birlashtirish tartibidan foydalanib bo'lmaydi.

Tez tartiblash

Birlashtirish tartibida bo'lgani kabi, bo'l va zabt et paradigmasi (va shuning uchun rekursiya) qo'llaniladi.
Muhim farqlar:
a) Tezkor saralash qo'shimcha xotirani jalb qilmasdan, "joyida" ishlaydi;
b) O'rtacha holat uchun tezkor saralashning asimptotik ish vaqti eng yomon holat uchun ishlash vaqtidan farq qiladi;
c) Yaxshi doimiy multiplikator (birlashmalardan yaxshiroq), shuning uchun amalda tez-tez saralash afzalroqdir.

Keling, bitta elementni tanlaymiz va uni pivot deb nomlaymiz. Keling, mos yozuvlar elementidan kichikroq barcha elementlarni chapga va mos yozuvlardan kattaroq elementlarni ushbu elementning o'ng tomoniga joylashtiramiz. Agar pivot q pozitsiyasida bo'lsa, u holda p dan q-1 gacha va q+1 dan r gacha bo'lgan pozitsiyalardagi elementlar rekursiv tartiblanadi. Ushbu rekursiya to'liq tartiblangan massivni beradi.
Misolda har bir pastki qatorning oxirgi elementi asosiy element sifatida ishlatiladi.
Massivning har bir pozitsiyasidagi eng past qiymat tartiblash tugallangandan keyin qaysi element shu holatda bo'lishini ko'rsatadi.