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

Tartiblash

Massivlarni saralashning to'rtta algoritmini ko'rib chiqing:

• Ularning barchasida eng yomon ish vaqti bor yoki D(n2), yoki D(njurnal2n);
• agar siz faqat bitta yoki bir nechta qidiruvni amalga oshirishingiz kerak bo'lsa, unda chiziqli qidiruvda to'xtash yaxshiroqdir;
• agar siz ko'p marta qidirishingiz kerak bo'lsa, unda birinchi navbatda massivni tartiblash va keyin ikkilik qidiruvni qo'llash mantiqan;
• saralashning o‘zi muhim vazifadir;
• saralash kaliti - saralanadigan elementlarga moslashtirilgan va elementlarning joylashish tartibini belgilovchi ma'lumot;
• Vazifa: elementlarni o'sish tartibida joylashtiring

Tanlash tartibi

• Biz butun massivni aylanib chiqamiz, eng kichik elementni topamiz va bu elementni birinchi element bilan almashtiramiz.
• Yana ikkinchi elementdan boshlab massivdan o'tamiz, qolganlar orasidan eng kichik elementni topamiz va bu elementni massivning ikkinchi elementi bilan almashtiramiz.
• Xuddi shu narsa uchinchi element uchun ham amalga oshiriladi va hokazo.
• Kerakli element joyiga qo'yilgandan so'ngn-1, saralash tugallandi.

Tanlovni saralash algoritmi

Protsedura tanlash-Sort(A,n).
Kirish:
• A – saralanadigan massiv.
• n – A massivdagi tartiblangan elementlar soni.
Natija: A massivning elementlari kamaymaydigan tartibda tartiblangan.
Jarayon bosqichlari:
1. i = 1 dan n-1 gacha:
A. Eng kichik o'zgaruvchining qiymatini i ga o'rnating.
B. j = i+1 dan n gacha:
i. Agar A[j] < A[eng kichik] o'zgaruvchiga tayinlansa
j ning eng kichik qiymati.
C. A[i] ↔ A[eng kichik] almashish.

Tanlovni saralash algoritmi

• A[i.. pastki massivdagi eng kichik elementni topish.n] chiziqli qidiruvning variantidir.
• "Ich-ichiga o'rnatilgan halqa" ning mavjudligi.
• To'g'riligini isbotlash ikkita invariant yordamida amalga oshirilishi mumkin (har bir tsikl uchun bittadan)

a) "1-bosqichdagi siklning har bir iteratsiyasi boshida A[1..i-1] pastki qatori tartiblangan tartibda i-1 eng kichik massiv elementlarini o'z ichiga oladi."
b) "1B-bosqichda halqaning har bir iteratsiyasi boshida A [eng kichik] elementi A[i..j-1] pastki massivdagi eng kichik element hisoblanadi."