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

Tanlovni saralash ish vaqti

1) Tashqi halqaning i-bosqichida ichki halqa bajariladin-i marta.
2) ichki halqaning umumiy takrorlash soni tashqi halqaning barcha iteratsiyalari yig‘indisiga teng:
3) Demak, tanlash saralashning ishlash vaqti t(n2) barcha holatlarda (agar takrorlashlar doimiy vaqtda bajarilsa).

• Bu sekin algoritm.
• Vaqt D(n2) har bir iteratsiyada elementlarni taqqoslash tufayli yuzaga keladi.
• Massiv elementlarini almashish soni faqat T(n).

Kiritish tartibi

• Saralash shunday amalga oshiriladiki, birinchi i pozitsiyalaridagi elementlar dastlab birinchi i pozitsiyalarida bo'lgan, ammo hozir to'g'ri tartibda (o'sish bo'yicha) tartiblangan elementlar bo'ladi.
• Elementni A[i] ga dastlab qaerga qo‘yish kerakligini aniqlash uchun qo‘shish tartibi A[i-1] elementidan boshlab o‘ngdan chapga A[1..i-1] pastki qatordan o‘tadi va undan kattaroq har bir elementni o‘rab oladi. A[i] dan o'ngga bir pozitsiya.
• A[i] dan oshmaydigan yoki massivning chap uchiga siljigan element topilsa, dastlab A[i] da bo‘lgan element massivdagi yangi joyiga o‘tkaziladi.

Qo'shishni tartiblash algoritmi

Protsedura qo'shish-Sartlash(A,n).
Kirish va natija: Tanlash-Sartlashdagi kabi.
Jarayon bosqichlari:
1. i = 1 dan n-1 gacha:
A. Asosiy o'zgaruvchini A[i] ga o'rnating va
i-1 qiymatini belgilash uchun j o'zgaruvchisi.
B. j > 0 va A[j] > tugmalari ekan, quyidagilarni bajaring:
i. A[j+1] ga A[j] qiymatini belgilang.
ii. j ni bittaga kamaytiring (tayinlash
o'zgaruvchi j qiymati j-1).
C. A[j + 1] tugmachasini o'rnating.

Kiritish saralash ish vaqti

• Ichki pastadirni takrorlash soni tashqi tsiklning i indeksiga ham, massiv elementlarining qiymatlariga ham bog'liq.
• eng yaxshi holat: massiv A allaqachon tartiblangan (ichki tsikl nol takrorlashni amalga oshiradi). Keyin tashqi pastadirning iteratsiyalari bajariladin-1 marta va protsedura vaqt oladi D(n) (tashqi halqaning har bir iteratsiyasi doimiy vaqtni oladi deb hisoblaymiz).
• Eng yomon holat: massiv A teskari tartibda tartiblangan (ichki tsikl maksimal mumkin bo'lgan takrorlash sonini bajaradi). Keyin tashqi halqa ichki halqani har safar i-1 marta takrorlaydi. Natija tanlov tartibidagi bilan bir xil: ish vaqti D(n2).