O’zbekiston respublikasi oliy va orta

Tez saralash va saralashni birlashtirish

Tez Sortlash va Merge Sort ikkala algoritmlari bo'linish va saralash usullariga asoslangan. Biroq, ular bo'linish va birlashtirish protseduralarini bajarish uchun
ishlatiladigan usullar bilan farqlanadi. Ular asosan bitta printsip asosida ishlaydi - masalani ikki yoki undan ortiq kichik muammolarga bo'lish va keyin ularni rekursiv ravishda hal qilish. Birlashtirish Sort eng yomon holatda Quick Sortga qaraganda samaraliroq, ammo ikkalasi o'rtacha holatda teng darajada samaralidir. Ammo Quick Sort birlashtirish tartibiga qaraganda tejamkorroq joy. Shunday qilib, tez saralash, shubhasiz, Merge Sort-ga qaraganda tezroq va yaxshiroq, ammo taqqoslash haqida gap ketganda, ba'zi holatlarda samarasiz bo'ladi.

Tez Saralash va Birlashtirish Saralash: Taqqoslash jadvali

6-rasm.

Tez saralash va saralashni birlashtirish

Tez Sortlash va Merge Sort ikkala algoritmlari bo'linish va saralash usullariga asoslangan. Biroq, ular bo'linish va birlashtirish protseduralarini bajarish uchun ishlatiladigan usullar bilan farqlanadi. Ular asosan bitta printsip asosida ishlaydi - masalani ikki yoki undan ortiq kichik muammolarga bo'lish va keyin ularni rekursiv
ravishda hal qilish. Birlashtirish Sort eng yomon holatda Quick Sortga qaraganda samaraliroq, ammo ikkalasi o'rtacha holatda teng darajada samaralidir. Ammo Quick Sort birlashtirish tartibiga qaraganda tejamkorroq joy. Shunday qilib, tez saralash, shubhasiz, Merge Sort-ga qaraganda tezroq va yaxshiroq, ammo taqqoslash haqida gap ketganda, ba'zi holatlarda samarasiz bo'ladi.

2. Sanash arqali sarlash

Sanash orqali saralash faqat chekli qiymatli sonlarni saralash mumkin. Masalan, massivning barcha elementlari qiymatlari 0..105 intervalga tegishlibo’lsa. Sanash orqali saralash uchun yordamchi massiv ochamiz, bu massiv har bir sondan qancha borligini saqlab turadi. Har bir songa kelganda uning sonini oshirish uchun yordamchi massivdan shu indeksning qiymatini 1 ga oshiramiz. Keyin har bir 0..105 indekslarni birma-bir ko’rib busondan necha marta uchragan bo’lsa shuncha martachiqaramiz.Bunday saralash usuli massiv elementlariningmaksimal qiymati massiv o’lchamiga nisbatan kichik bo‟lganda ancha effektiv bo’ladi.
Ishlash vaqti O(n+Max); Qo‟shimcha xotira O(Max);
Ko'p bosqichli saralash va ketma-ket saralash. Namuna olish hayotning eng muhim tomonlaridan biridir. Namunalarni har biridan tortib, hukumatgacha va kichik bir jamoadan tortib to yirik sanoatgacha talab qilinadi. Namuna tanlash kelajakka ta'sir ko'rsatadigan qarorlarni qabul qilish uchun foydalaniladigan natijalarni taqdim etadi. Namuna olish bu ma'lum bir mahsulot, g'oya yoki o'zgartirilishi kerak bo'lgan barcha narsalar to'g'risida ma'lumot to'plashning ilmiy usuli. Ko'p bosqichli saralash va ketma-ket saralash ma'lumotlar yig'ish va tahlil qilishning ikki usuli bo'lib, har xil turdagi ma'lumotlar uchun ishlatiladi. Ko'p bosqichli saralash ommaviy tanlov uchun ishlatiladi va ketma-ket saralash nisbatan kichik o'lchamdagi namunalarda qo'llaniladi.
Ko'p bosqichli saralash nima?
Ko'p bosqichli tanlovni klaster tanlovi bilan taqqoslash mumkin, ammo ancha murakkab. Ushbu tanlab olish usulida turli xil ma'lumotlar klasterlari shakllantirilgan va tahlil qilish uchun ushbu klasterlardan bir nechta namunalar tasodifiy tanlangan. Bu ko'p bosqichli saralashdir, chunki ma'lumotlar klasterlari turli darajalarda shakllanadi. Birinchi bosqichda ko'p sonli guruhlar shakllantiriladi va keyin ikkinchi darajani hosil qilish uchun har bir guruhdan bir nechta namunalar olinadi va bu jarayon barcha ma'lumotlarni tahlil qilish uchun takrorlanadi. Namuna olishning bu usuli tez va arzon va ko'p vaqtni tejaydi, ammo bu usul kamroq aniq. Agar namunalarning umumiy ro'yxati mavjud bo'lmasa, ko'p sonli tanlab olishda, agar ular odat bo'yicha yoki yoqtirish uchun ommaviy populyatsiyani o'rganish kerak bo'lsa, foydalaniladi.