“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Qo‘yish orqali saralash algoritmi tahlili
Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
Taqqoslashlar soni:
O‘rinlashtirishlar soni:
Saralashga ketgan vaqt:
Tanlash orqali saralash(Selection sort)
1. Berilgan ob’ektlar ichidan eng kichik kalitga ega element tanlanadi.
2. Ushbu element boshlang‘ich ketma-ketlikdagi birinchi element a1 bilan o‘rin almashadi.
3. Undan keyin ushbu jarayon qolgan n-1 ta element, n-2 ta element va xokazo, toki bitta eng “katta” element qolguncha davom ettiriladi.
Misol:
- boshlang’ich holat
Ғоя:
• Энг кичик элементни топинг ва уни биринчи ўринга қўйинг (A[0] билан ўрнини алмаштириш)
• қолганларидан энг кичигини топинг ва уни иккинчи ўринга қўйинг (A[1] билан ўрнини алмаштириш), ва бошқалар.
Tanlash orqali saralash algoritmi tahlili
Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.
Taqqoslashlar soni:
O‘rinlashtirishlar soni:
Saralashga ketgan vaqt:
Eng sodda saralash usuli
Massivni chapdan o'ngga qarab ko'rib chiqiladi va yo'l davomida qo'shnilarni solishtiriladi. Agar o'zaro saralanmagan elementlar uchrasa, ularning o’rni almashtiriladi va eng boshiga qaytiladi. Massiv boshidan yana ko’rib chiqiladi va yana tekshiriladi, agar qo'shni elementlarning "noto'g'ri" juftligi yana uchrasa, ularning joylari almashtiriladi va barchasi qaytadan boshlanadi. Massiv saralanguncha davom ettiriladi.
Глупая сортировка
Oddiy saralash usuliga birgina o’zgartirish kiritib, uni takomillashtiramiz. O'tish paytida ikkita qo'shni saralanmagan elementni topib, ularni almashtirib, biz massivning boshiga qaytmaymiz, balki uning o'tishini oxirigacha davom ettiramiz. Bunday holda, bizning oldimizda taniqli Pufaksimon saralash usuli namoyon bo’ladi.