|
Saralash tushunchasi va uning vazifasi
| | bet | 5/8 | | Sana | 07.10.2024 | | Hajmi | 1 Mb. | | #273965 |
Bog'liq Ma\'lumotlar tuzilmasi va algaritim-1 Saralash tushunchasi va uning vazifasi.
Saralash – bu berilgan to’plam elementlarini biror bir tartibda joylashtirish jarayonidir. Saralashni maqsadi tartiblangan to’plamda kerakli elementni topishni osonlashtirishdan iborat. Saralash dasturlarni translyasiya qilinayotganda, ma’lumotlar majmuasini tashqi xotirada tashkil qilinayotganda, kutubxonalar, kataloglar, ma’lumotlar bazasi yaratilayotganda tadbiq qilinadi. Ma’lumki, saralashning turli hil algoritmlari mavjud. Sababi, bitta masalani saralash uchun juda ko’plab turli hil algoritmlardan foydalanish mumkin. Berilgan masalani hal qilishda ba’zilari mukammal bo’lishi mumkin. Shuning uchun saralash masalasida algoritmlarni qiyosiy tahlilini o’tkazish zarurati paydo bo’ladi.
Saralashning qat’iy usullari va ularning samaradorligi.
To’g’ridan-to’g’ri qo’shish usuli bilan saralash. Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartlar) hayolan “tayyor” a(1),...,a(i-1) va boshlang’ich ketma-ketliklarga bo’linadi. Har bir qadamda (i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi) boshlang’ich ketma-ketlikdan i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo’shiladi.
Taklif qilinayotgan usulni quyidagi misolda ko’rib chiqamiz.
Faraz qilaylik, kalit qiymati 4, 5, 3, 8, 1, 7 bo’lgan elementlar berilgan bo’lsin.
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi. Taqqoslashlar amalga oshirish mobaynida, navbatdagi a(j) element bilan solishtiriladi, keyin esa x bo’sh joyga qo’yiladi yoki a( j ) o’nga suriladi va jarayon chapga “ketadi”. Shuni e’tiborga olish lozimki, saralash jarayoni quyidagi shartlarni birortasi bajarilganda yakunlanadi:
-
x elementi kalitidan kichik kalitli a(j) element topildi.
-
tayyor ketma-ketlikning chap tomoni oxiriga yetib borildi.
Taklif etilayotgan usul algoritmi quyidagicha bo’ladi:
for (int i=1;i int j=i;
while(a[j] int t=a[j-1]; a[j-1]=a[j]; a[j]=t;
j=j-1;
}
}
|
| |
