Ma'lumotlar tuzilmalari va algoritmlari
(Ikkinchi qism — Saralash)
Ma'lumotlar tuzilmalari va algoritmlarini o'rganishimizning "birinchi qismida" biz tartiblangan massivdan foydalanish elementlarni topish, o'zgartirish yoki o'chirish kabi vazifalarni bajarishda bizga ko'proq moslashuvchanlikni ta'minlashini bilib oldik. Bu bizning kundalik faoliyatimizda keng tarqalgan ko'plab elementlar bilan ishlashda qimmatli bo'ladi. Ushbu harakatlar tez-tez qo'llanilishi sababli, tartiblash algoritmlarini muhokama qilish uchun biroz vaqt talab etiladi, ayniqsa tartibsiz massivlar bilan ishlashda.
Maqola quyidagicha tuziladi:
Buni qanday qilgan bo'lardingiz?
Bubble Saralash
Tanlovni saralash
Qo'shishni saralash
Siz buni qanday qilgan bo'lardingiz?
Shaxs sifatida siz kompyuter dasturidan afzalliklarga egasiz. Siz bir vaqtning o'zida barcha bolalarni ko'rib chiqishingiz va har birini o'lchash va taqqoslashga hojat qoldirmasdan tezda eng balandini tanlashingiz mumkin.
Ba'zi norasmiy o'zgarishlardan so'ng, rasmda ko'rsatilganidek, barcha bolalarni bir qatorga osongina joylashtirishingiz mumkin.
Biroq, kompyuter dasturi xuddi shu tarzda ma'lumotlarni qayta ishlay olmaydi. Taqqoslash operatorlari qanday ishlashi tufayli u bir vaqtning o'zida faqat ikkita bolani solishtirishi mumkin. Bu cheklangan istiqbol algoritmlarda umumiy mavzudir. Odamlarga hamma narsa oddiy ko'rinsa-da, algoritmlar umumiy rasmni ko'ra olmaydi. Buning o'rniga, ular aniq tafsilotlarga e'tibor berishadi va oddiy qoidalarga amal qilishadi.
Ushbu bobdagi uchta algoritm ma'lumotlar saralanmaguncha ikki bosqichni takrorlaydi
Bubble Saralash
Bubble Sort – oddiy tartiblash algoritmi bo‘lib, u elementlar ro‘yxatini qayta-qayta bosib o‘tadi va qo‘shni elementlarni taqqoslaydi, agar ular noto‘g‘ri tartibda bo‘lsa, ularni almashtiradi. U "Bubble Sort" deb ataladi, chunki kichikroq elementlar ro'yxatning tepasiga "qabariq", kattaroq elementlar esa pastga "cho'kadi".
Bubble Sort qanday ishlaydi:
- Ro'yxatning birinchi ikkita elementini solishtirishdan boshlang. Agar birinchi element ikkinchisidan katta bo'lsa, ularni almashtiring.
- Keyingi juft elementlarga o'ting va ularni solishtiring. Agar kerak bo'lsa, yana almashtiring.
- Ushbu jarayonni butun ro'yxat uchun davom ettiring, qayta-qayta taqqoslash va qo'shni elementlarni almashtirish kerak bo'lmaguncha.
- Ro'yxat bo'ylab bir marta o'tgandan so'ng, eng katta element oxirgi pozitsiyaga "ko'tariladi". Qolgan tartiblanmagan elementlar uchun jarayonni takrorlang.
- To'liq ro'yxat saralanmaguncha 1-4 bosqichlarni takrorlashni davom eting.
Bubble Sort tushunish va amalga oshirish oson, lekin katta ro'yxatlar uchun unchalik samarali emas. Uning o'rtacha va eng yomon vaqt murakkabligi O(n²), bu erda "n" ro'yxatdagi elementlar soni. Bu katta ma'lumotlar to'plamini saralashni amaliy bo'lmaydi. Biroq, bu kichik ro'yxatlar uchun yoki tartiblash algoritmlarini tushunish uchun o'quv mashqi sifatida ajoyib tanlov bo'lishi mumkin.
Tanlovni saralash
Tanlovni saralash oddiy tartiblash algoritmi bo‘lib, massivning saralanmagan qismidan minimal (yoki maksimal) elementni qayta-qayta tanlash va uni tartiblangan qismning boshiga (yoki oxiriga) joylashtirish orqali ishlaydi. U o'rtacha va eng yomon stsenariylar uchun vaqt murakkabligi O(n²) ga ega, bu uni katta ro'yxatlar uchun samarasiz qiladi.
Tanlovni saralash algoritmi quyidagicha ishlaydi:
- Massivning tartiblanmagan qismidagi minimal (yoki maksimal) elementni toping.
- Uni tartiblanmagan qismning birinchi elementi bilan almashtiring.
- Yuqoridagi amallarni massivning qolgan saralanmagan qismi uchun takrorlang, faqat tartiblangan qismga joylashtirilgan element bundan mustasno.
Tanlash Saralash shunday nomlanadi, chunki u eng kichik (yoki eng katta) elementni “tanlaydi” va uni massivning tartiblangan qismidagi toʻgʻri holatiga “koʻpiklaydi”. Oddiyligiga qaramay, Tanlash Saralash kvadratik vaqt murakkabligi tufayli katta massivlar uchun samarali emas.
Bubble Sort kabi ba'zi boshqa tartiblash algoritmlaridan farqli o'laroq, Tanlash Saralash massivni skanerlashda doimiy ravishda elementlarni almashtirmaydi. Bu xususiyat elementlarni almashtirish qimmat bo'lgan holatlarda foydali bo'lishi mumkin.
Qo'shishni saralash
Insertion Sort - bu so'nggi tartiblangan massivni bir vaqtning o'zida bitta elementni yaratadigan oddiy tartiblash algoritmi. Bu taqqoslashga asoslangan tartiblash algoritmi bo'lib, massiv tartiblangan va tartiblanmagan qismga bo'linadi. Har bir iteratsiyada algoritm saralanmagan qismdan elementni oladi va uni tartiblangan qism ichida o'zining to'g'ri joyiga qo'yadi.
Insertion Sort qanday ishlaydi:
- Ikkinchi elementdan boshlang (indeks 1) va uni birinchi element bilan solishtiring (indeks 0).
- Agar ikkinchi element birinchi elementdan kichikroq (yoki saralash tartibiga qarab kattaroq) bo'lsa, ularni almashtiring.
- Uchinchi elementga o'ting (indeks 2) va uni tartiblangan qismdagi oldingi elementlar bilan solishtiring. Kattaroq elementlarni o'ngga siljitish orqali uni tartiblangan qismning to'g'ri joyiga joylashtiring.
- Jarayonni qolgan saralanmagan elementlar uchun takrorlang, har safar joriy elementni tartiblangan qism ichidagi to'g'ri joyiga qo'ying.
Insertion Sort kichik ma'lumotlar to'plamlari yoki qisman tartiblangan massivlar uchun samarali. Tartiblangan massivlar uchun O(n) chiziqli vaqt murakkabligiga ega. Biroq, uning eng yomon vaqt murakkabligi kvadratik bo'lib, uni katta massivlar uchun kamroq moslashtiradi.
Xulosa qilib aytganda, Insertion Sort tushunish va amalga oshirish oson bo'lgan oddiy tartiblash algoritmidir. Bu katta ma'lumotlar to'plamlari uchun eng samarali tanlov bo'lmasa-da, kichik yoki tartiblangan massivlar uchun amaliy variant bo'lishi mumkin.
