Algoritmlar nazariyasining boshlang’ich tushunchalari

TANLOVNI SARALASH:: TANLOVNI SARALASH

Oddiy va oddiy - biz maksimal elementni izlash uchun massivdan o'tamiz. Topilgan maksimal oxirgi element bilan almashtiriladi. Massivning saralanmagan qismi bitta elementga qisqardi (biz topilgan maksimalni qayta tashkil qilgan oxirgi elementni o'z ichiga olmaydi). Xuddi shu harakatlarni ushbu tartiblanmagan qismga qo'llaymiz - biz maksimalni topamiz va uni massivning saralanmagan qismidagi oxirgi joyga qo'yamiz. Shunday qilib, massivning tartiblanmagan qismi bitta elementga kamayguncha davom etamiz.

Tanlash (ma'lumotlar): i, e uchun enumerate(ma'lumotlar): mn = min (diapazon(i, len(ma'lumotlar)), kalit=data.__getitem__) ma'lumotlar[i], ma'lumotlar = ma'lumotlar, e ma'lumotlarini qaytarish
Oddiy tanlash tartiblash qo'pol ikkilangan sanab hisoblanadi. Uni yaxshilash mumkinmi? Keling, bir nechta o'zgartirishlarni ko'rib chiqaylik.

IKKI MARTA TANLASH TARTIBI

Shu kabi g'oya pufakchali tartiblashning varianti bo'lgan da qo'llaniladi. Massivning saralanmagan qismidan o'tib, maksimaldan tashqari, biz yo'lda minimalni ham topamiz. Biz minimalni birinchi o'ringa, maksimalni oxirgiga qo'yamiz. Shunday qilib, saralanmagan qism har bir iteratsiyada ikkita elementga kamayadi.
Bir qarashda, bu algoritmni 2 marta tezlashtiradiganga o'xshaydi - har bir o'tishdan keyin tartiblanmagan pastki qator birdan emas, balki ikki tomondan qisqaradi. Biroq, shu bilan birga, taqqoslashlar soni 2 barobar oshdi, almashtirishlar soni esa o'zgarishsiz qoldi. Ikki marta tanlash algoritm tezligini biroz oshiradi va ba'zi tillarda u ba'zi sabablarga ko'ra sekinroq ishlaydi.

TANLANGAN SARALASH VA QO'SHISH TARTIBI O'RTASIDAGI FARQ

Ko'rinishidan, tanlov bir xil va bir xil narsa, algoritmlarning umumiy klassi. Xo'sh, yoki qo'shish turlari - tanlovni saralashning bir turi. Yoki tanlash turlari qo'shish turlarining alohida holatidir. Va u erda va u erda biz elementlarni massivning tartiblanmagan qismidan navbat bilan olib, ularni tartiblangan maydonga yo'naltiramiz.
Asosiy farq: kiritish tartibida biz massivning tartiblanmagan qismidan ajratamiz har qanday elementni tanlang va uni tartiblangan qismdagi joyiga joylashtiring. Tanlovda biz maqsadli ravishda qidiramiz maksimal element (yoki minimal), biz massivning tartiblangan qismini to'ldiramiz. Qo'shimchalarda biz keyingi elementni qaerga qo'yishni qidiramiz va tanlashda biz uni qaerga qo'yishimizni oldindan bilamiz, lekin ayni paytda bu joyga mos keladigan elementni topishimiz kerak.
Bu esa algoritmlarning ikkala sinfini ham o‘z mohiyati va qo‘llaniladigan usullari bilan bir-biridan butunlay farq qiladi.