logo

Ma’lumotlarni saralash. Saralashning o’rniga qo’yish (vstavka) algoritimi

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

357.5 KB
MAVZU: Ma’lumotlarni saralash. Saralashning o’rniga
qo’yish (vstavka) algoritimi.
MUNDARIJA
KIRISH
1.Bob.SARALASH TUSHUNCHASI
1.1.Saralash tushunchasi.
1.2.Algoritm samaradorligi.
1.3.Quiksort-tez saralash algoritmi.
2.Bob. SARALASHNING O’RNIGA QO’YISH ALGORITIMI
2.1.O’rniga qo’yish bilan saralash algoritmi.
2.2.Birlashtirish bilan saralash algoritmi.
2.3.Diskli xotira qurilmasining tuzilishi. 
FOYDALANILGAN ADABIYOTLAR RO‘YXATI.
    
1 KIRISH
    Biror   bir   ma’lumotni   saralash   yoki   qandaydir   qolipga   solish   juda   ham.   Sababi,
tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday
tizim sekin va xatoliklarga moyil bo’ladi
 Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil
bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi.
Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:
 Algoritmlarning   ishlash   vaqtlari   har   doim   ham   bir   xil   bo’lmaydi   va
ularning   ishlashi   qandaydir   ma’lum   holatlarda   o’zgarib   turadi.   Ya’ni,
umumiy   holatda   biror   algoritmdan   yomonroq   ishlovchi   boshqa   bir
algoritm,   aynan,   qandaydir   holat   uchun   undan   ko’ra   yaxshiroq   ishlashi
mumkin.
 Ikkinchi   sabab   sifatida   esa,   albatta,   saralash   algoritmining   xotiradan
qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi.
    Saralash  algoritmlarida   turg’unlik   (stability)   deganda,  ikkita  bir  xil  elementning
ilk   holatdagi   bir   biriga   nisbatan   o’rninini   saralashdan   keyin   ham   saqlab   qolishiga
aytiladi.
Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan
algoritm   saraladan   keyin   doim   birinchi   1   sonini   ikkinchi   1   sonidan   doim   oldin
joylashtirsa, bu algoritm   turg’un saralovchi algoritm   deyiladi.
Saralash   algoritmlari   ichidagi   Quick   Sort   ko’p   hollarda   Merge  yoki   Heap   sortdan
tez   ishlagani   bilan   u   turg’un   saralash   algoritmi   hisoblanmaydi   (Turg’un   holga
keltirishning iloji bor).
Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga
turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan
2 tizim   samaradorligiga   ta’sir   qilishi   mumkin.   Shu   sababdan,   turli   xil   saralash
algoritmlari ishlashini  o’rganish va tushunish professional  dasturchi uchun muhim
hislatlardan biri hisoblanadi.
                            1.Bob.SARALASH TUSHUNCHASI
                              1.1.SARALASH TUSHUNCHASI
Saralash   - tartiblash ( Sorting Algorithms ) deb, berilgan obyektlar ketma-
ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. 
Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun 
maktab jurnalida o'quvchilar familiyasi   alifbo   tartibiga ko'ra saralangan 
bo'ladi. Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100 Bu qatorni 
kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz 
mumkin. Bu saralashni amalga oshirish jarayoni   Saralash 
algoritmi   deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon 
hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab 
tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday 
amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana shu 
algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli 
qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni 
ro'yxatnin g boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib 
chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida 
qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz.
Saralash asosan ro'yxat, massiv elementlarida amalga oshiriladi. Masalan 
sizning sinfingizda 5 ta o'quvchi bor. Ularni familiyasini alifbo tartibida 
saralash mumkin.
Sonlar berilishi: 23, 54, 3, 22, 1, 45;
Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son 
bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turipti) Shu 
3 tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi 
eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 
54;(22 esa davomchi) Oxirgi marta almashtirishimiz quyidagi natijani 
beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi) Saralangan tartib quyidagi 
holatga keldi: 1, 3, 22, 23, 45, 54;
Bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun 
faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb 
bo`lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir 
qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ladi. Chunki ilk 
kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi 
saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda 
ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng 
foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil 
saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini 
o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi 
tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki 
tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan 
ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi 
algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, 
shu sababli ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga 
oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni 
yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi.
Saralash algoritmi turlari  
 Bubble sort   
 Selection sort   
 Insertion sort   
 Quick sort   
 Merge sort   
4 Bubble sort
 Bubble sort   ikki qo'shni elementni solishtirish va ular mo'ljallangan tartibda 
bo'lmaguncha, ularni almashtiradigan tartiblash algoritmidir. Xuddi suv 
yuzasiga ko'tarilgan havo pufakchalarining harakati kabi, massivning har bir 
elementi har bir iteratsiyada oxirigacha harakat qiladi. Shuning uchun u 
pufakchali saralash deb ataladi.
BubbleSort
“Bubble sort” bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar 
bilan solishtirishga asoslangan algoritm hisoblanadi. Unda yonma-yon 
turgan elementlardan chapdagisi o‘ngdagidan kattaligi aniqlansa, bu ikkala 
son o`rni almashtiriladi. Bu jarayon almashtirish kerak bo`lmay qolguncha 
davom etadi, ya`ni barcha elementlar o‘sish tartibida bo‘lib qolguncha.
“Bubble sort” nisbatan ko`p vaqt talab qiluvchi saralash algoritmi 
hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni taqriban 
n*n ga teng. Bu, n kichik son bo`lsa unchalik sezilmaydi. Sababi, hozirgi 
zamonaviy kompyuterlar uchun bu takrorlanish soni qiyinchilik tug`dirmaydi. 
Ammo butun boshli ma`lumotlar bazasidagi ma`lumotlarni saralash talab 
5 etilsachi? Albatta vaqtdan yutqazamiz. Ammo, bu algoritm saralash 
algoritmlarini tushunib olish uchun ilk qadam hisoblanadi.
Bubble-sort
Bosqichma-bosqich misol  
“5 1 4 2 8” raqamlari massivini oling va pufakchali tartiblash yordamida 
massivni eng kichik sondan eng katta raqamga tartiblang. Har bir 
bosqichda   qalin harf   bilan yozilgan elementlar taqqoslanadi. Uchta o'tish 
kerak bo'ladi;
Birinchi o'tish
 ( 5   1   4   2   8)   →   ( 1   5   4   2   8),   Bu   yerda   algoritm   dastlabki   ikki   elementni
taqqoslaydi va 5 > 1 dan keyin almashinadi.
 (1   5 4   2 8) → (1   4 5   2 8), 5 > 4 dan beri almashtirish
 (1 4   5 2   8) → (1 4   2 5   8), 5 > 2 dan beri almashtirish
 (1 4 2   5 8 ) → (1 4 2   5 8 ), Endi bu elementlar tartibda bo lgani uchun (8 >ʻ
5), algoritm ularni almashtirmaydi.
Ikkinchi o'tish
 ( 1 4   2 5 8) → ( 1 4   2 5 8)
 (1   4 2   5 8) → (1   2 4   5 8), 4 > 2 dan beri almashtirish
 (1 2   4 5   8) → (1 2   4 5   8)
 (1 2 4   5 8 ) → (1 2 4   5 8 )
Endi massiv allaqachon tartiblangan, lekin algoritm uning tugallanganligini 
bilmaydi. Algoritm tartiblanganligini bilish uchun uni almashtirishsiz   yana 
bitta to'liq   o'tish kerak.
Uchinchi o'tish
6  ( 1 2   4 5 8) → ( 1 2   4 5 8)
 (1   2 4   5 8) → (1   2 4   5 8)
 (1 2   4 5   8) → (1 2   4 5   8)
 (1 2 4   5 8 ) → (1 2 4   5 8 )
Algoritmi va dasturi  
public class BubbleSort {
public static void main(String[] args) {
int[] massiv = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
int n = massiv.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (massiv[i] > massiv[k]) {
int temp;
temp = massiv[i];
massiv[i] = massiv[k];
massiv[k] = temp;
}
}
for (int i = 0; i < massiv.length; i++) {
System.out.print(massiv[i] + ", ");
}
System.out.println("\n");
}
}
}
Chiqariluvchi natijamiz esa:
2, 4, 6, 9, 12, 23, 0, 1, 34, // 1-qadam.
2, 4, 6, 9, 12, 0, 1, 23, 34, //2-qadam.
2, 4, 6, 9, 0, 1, 12, 23, 34,//3-qadam.
2, 4, 6, 0, 1, 9, 12, 23, 34,//4-qadam.
2, 4, 0, 1, 6, 9, 12, 23, 34,//5-qadam.
7 2, 0, 1, 4, 6, 9, 12, 23, 34,//6-qadam.
0, 1, 2, 4, 6, 9, 12, 23, 34, //7-qadam.
0, 1, 2, 4, 6, 9, 12, 23, 34, //8-qadam.
0, 1, 2, 4, 6, 9, 12, 23, 34,//9-qadam.
0, 1, 2, 4, 6, 9, 12, 23, 34, // saralangan holdagi massiv.
Selection sort
 Selection sort   — Tanlab saralash bu   — oddiy tartiblash   algoritm. 
Ushbu tartiblash algoritmi o z joyida taqqoslashga asoslangan algoritm ʻ
bo lib, unda ro yxat ikki qismga bo linadi, tartiblangan qism chap tomonda 	
ʻ ʻ ʻ
va tartiblanmagan qism o ng tomonda. Dastlab, tartiblangan qism bo sh, 	
ʻ ʻ
tartiblanmagan qismi esa butun ro yxatdir.	
ʻ
Udtag sort 001
Eng kichik element tartiblanmagan massivdan tanlanadi va eng chap 
element bilan almashtiriladi va bu element tartiblangan massivning bir 
8 qismiga aylanadi. Bu jarayon tartiblanmagan massiv chegarasini bitta 
element bilan o ngga siljitishda davom etadi.ʻ
Ushbu algoritm katta ma lumotlar to plamlari uchun mos emas, chunki 	
ʼ ʻ
uning o rtacha va eng yomon holatlari murakkabligi n (n	
ʻ 2
), bu yerda n   — 
elementlar soni. 
Tanlab saralash qanday ishlaydi?  
Misol tariqasida quyidagi massivni ko rib chiqamiz: arr[] = {64, 25, 12, 22, 	
ʻ
11}
Birinchi o tish:	
ʻ   Saralangan massivdagi birinchi o rin uchun butun	ʻ   massiv   0 
dan 4 gacha bo lgan indeksdan ketma-ket o tkaziladi. Hozirgi vaqtda 64 	
ʻ ʻ
saqlanadigan birinchi pozitsiya, butun massivni aylanib o tgandan so ng, 11 	
ʻ ʻ
eng past qiymat ekanligi ayon bo ladi.	
ʻ
  64       25       12       22       11   
Shunday qilib, 64 ni 11 bilan almashtiring. Bir iteratsiyadan so ng 	
ʻ
massivdagi eng kam qiymat bo lgan 11 , tartiblangan ro yxatning birinchi 	
ʻ ʻ
pozitsiyasida paydo bo ladi.	
ʻ
  11       25       12       22       64   
Ikkinchi o tish:	
ʻ   25 mavjud bo lgan ikkinchi pozitsiya uchun massivning 	ʻ
qolgan qismini yana ketma-ketlikda aylantiring.
  11       25       12       22       64   
Ketishdan so ng biz 12 massivdagi ikkinchi eng past qiymat ekanligini va u 	
ʻ
massivda ikkinchi o rinda paydo bo lishi kerakligini aniqladik, shuning uchun 	
ʻ ʻ
bu qiymatlarni almashtiring.
  11       12       25       22       64   
9 Uchinchi o tish:ʻ   Endi, uchinchi o rin uchun, 25 mavjud bo lgan joyda yana 	ʻ ʻ
massivning qolgan qismini aylanib o ting va massivdagi uchinchi eng kam 	
ʻ
qiymatni toping.
  11       12       25       22       64   
Ketish paytida 22 uchinchi eng kam qiymat bo lib chiqdi va u massivda 	
ʻ
uchinchi o rinda paydo bo lishi kerak, shuning uchun 22 ni uchinchi 	
ʻ ʻ
o rindagi element bilan almashtiring.	
ʻ
  11       12       22       25       64   
To rtinchi o tish:
ʻ ʻ   Xuddi shunday, to rtinchi pozitsiya uchun massivning 	ʻ
qolgan qismini kesib o ting va massivdagi to rtinchi eng kichik elementni 	
ʻ ʻ
toping. 25 4-eng past qiymat bo lgani uchun u to rtinchi o rinni egallaydi.	
ʻ ʻ ʻ
  11       12       22       25       64   
Beshinchi o tish:	
ʻ   Nihoyat, massivda mavjud bo lgan eng katta qiymat 	ʻ
avtomatik ravishda massivning oxirgi pozitsiyasiga joylashtiriladi Olingan 
massiv tartiblangan massivdir.
   11       12       22       25       64 
Selsort de 0
Tanlab saralash algoritmi  
 1-qadam − MINni 0-indexli joyga qo ying
ʻ
 2-qadam − Ro yxatdagi minimal elementni qidiring	
ʻ
 3-qadam − MIN manzilidagi qiymat bilan almashtiring
 4-qadam − Keyingi elementga ishora qilish uchun MIN ni oshiring
 5-qadam − Ro yxat tartiblashtirilguncha takrorlang
ʻ
10 Dasturi  
# include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    for (i = 0; i < n-1; i++)
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
            min_idx = j;
        swap(&arr[min_idx], &arr[i]);
    }
}
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
11 }
Insertion sort
 Insertion sort   — (Joylab saralash)   ham 
tartibsiz   massiv   elementlarini   saralash   uchun mo ljallangan. Uning ishlash ʻ
algoritmi xuddi qo ldagi kartani saralashga o xshab ketadi. Tartibsiz turgan 	
ʻ ʻ
kartalar ichidan birini olasiz va uni o zi turishi kerak bo lgan joyga 	
ʻ ʻ
joylashtirib qo yasiz.	
ʻ
Insertion sort ham shu ko rinishda ishlaydi. Algoritm oldin massiv boshidagi 	
ʻ
ikkita elementni saralab olib, massivning qolgan elementlarini shunga 
qarab o z o rniga joylashtirib chiqadi.	
ʻ ʻ
Dark inverted insertion sorting
Joylab saralashning xususiyatlari  
Bu algoritm oddiy amalga oshirilgani uchun eng oddiy algoritmlardan biridir. 
Insertion sort kichik ma lumotlarni saralash uchun samarali. Joylab saralash 	
ʼ
tabiatan moslashuvchan, ya ni qisman saralangan ma lumotlar to plamlari 	
ʼ ʼ ʻ
uchun mos keladi.
Insertion sort ham   Selection sort   va   Bubble sort   kabi O(n 2
) vaqt 
murakkabligi bilan ishlasa ham, lekin ulardan ko ra samaraliroq algoritm 	
ʻ
hisoblanadi. Aynan, massiv elementlari deyarli saralangan holatda Insertion 
sort algoritmi   Merge sort   yoki   Quick sort   algoritmidan ham ko ra tezroq 	
ʻ
ishlaydi.                                                                                                
   Joylab saralash algoritmining ishlashi
Misolni ko rib chiqing: arr[]: {12, 11, 13, 5, 6}	
ʻ
12   12       11       13       5       6   
Birinchi o tishʻ
Dastlab, massivning dastlabki ikkita elementi joylash tartibida taqqoslanadi.
  12       11       13       5       6   
Bu   erda   12   11   dan   katta,   ular   o sish   tartibida   emas   va   12   o zining   to g ri   joyida	
ʻ ʻ ʻ ʻ
emas. Shunday qilib, 11 va 12 ning o rnini  almashtiring. Shunday qilib, hozircha	
ʻ
11 tartiblangan pastki qatorda saqlanadi.
  11       12       13       5       6   
Ikkinchi o tish	
ʻ
Endi keyingi ikkita elementga o ting va ularni solishtiring	
ʻ
  11       12       13       5       6   
Bu erda 13 12 dan katta, shuning uchun ikkala element ham o sish 	
ʻ
tartibida turibdi, almashtirish sodir bo lmaydi. 12, shuningdek, 11 	
ʻ
bilan birga tartiblangan pastki qatorda saqlanadi
Uchinchi o tish	
ʻ
Endi   tartiblangan   kichik   massivda   ikkita   element   mavjud,   ular   11   va   12   Keyingi
ikkita elementga o tish: 13 va 5	
ʻ
  11       12       13       5       6   
5 va 13 ikkalasi ham o z joyida emas, shuning uchun ularni almashtiring	
ʻ
  11       12       5       13       6   
Almashtirilgandan   so ng,   12   va   5   elementlar   tartiblanmadi,   shuning   uchun   yana
ʻ
almashtiriladi
  11       5       12       13       6   
13 Bu erda yana 11 va 5 tartiblanmadi, shuning uchun yana almashtiring
  5       11       12       13       6   
bu erda u o zining to g ri holatidaʻ ʻ ʻ
To rtinchi o tish	
ʻ ʻ
Endi tartiblangan kichik massivda mavjud bo lgan elementlar 5, 11 va 12 Keyingi	
ʻ
ikkita elementga o tish: 13 va 6	
ʻ
  5       11       12       13       6   
Shubhasiz,   ular   tartiblanmagan,   shuning   uchun   ikkalasini   almashtirishni   amalga
oshiring
  5       11       12       6       13   
Endi 6 12 dan kichik, shuning uchun yana almashtiring
  5       11       6       12       13   
Almashtirish 11 va 6 ni tartiblamaydi, shuning uchun yana almashtiring
  5       6       11       12       13   
Nihoyat, massiv to liq tartiblangan.
ʻ
InsertionSort
Dasturi  
#include <bits/stdc++.h>
14 using namespace std;
void insertionSort(int arr[], int n)
{
  int i, key, j;
    for (i = 1; i < n; i++)
  {
 key = arr[i];
   j = i - 1;
 while (j >= 0 && arr[j] > key)
  {
     arr[j + 1] = arr[j];
            j = j - 1;
       }
        arr[j + 1] = key;
    }
}
void printArray(int arr[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int main()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, N);
    printArray(arr, N);
    return 0;
}
 Saralash tushunchasi;
 Saralash algoritmlari:
 Qo’shish orqali saralash;
 Tanlash orqali saralash;
15  Alamashtirish orqali (pufaksimon) saralash;
 Saralashning yaxshilangan algoritmlari;
 Saralash algoritmlarining samaradorligi.
Saralash tushunchasi
 Saralash – bu tuzilma elementlarini qandaydirkriteriya asosida tartiblash.
 Kriteriya sifatida odatda kalit deb ataluvchi sonli maydon qo’llaniladi.
 Elementlarni kalit maydonlarining har bir keyingisi o’zidan oldingisidan 
kichik bo’lsa, bunday saralash kamayish tartibida saralash deyiladi.
 Agarda   har   bir   keyingi   kalit   maydoni   o’zidan oldingisidan   katta   bo’lsa, o’sish
tartibida saralash deyiladi.
Saralash tushunchasi
 Saralash   algoritmi –   bu   elementlarni   saralash   uchun qo’llaniladigan   algoritm
hisoblanadi.
 Saralash maqsadi –ma’lumotlarni qayta ishlashdaberilgan qiymat (kalit) bo’yicha
elementni qidiribtopishni yengillashtirishdan iborat
 Saralashning barcha algoritmlari ikki guruhga bo’linadi:
 - ichki saralash algoritmlari (massivda (ichki xotirada) saralash uchun qo’llaniladi);
 - tashqi saralash algoritmlari (faylda (tashqi xotirada) saralash uchun qo’llaniladi).
1.2..ALGORITM SAMARADORLIGI
Saralashning ikkita turi mavjud:   ichki   va   tashqi :
-ichki saralash   -operativ xotiradagi saralash ;
- tashqi saralash – tashqi xotirada saralash.
Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni
 almashtirishlar katta sarf (vaqt va xotira ma nosida) talab qiladi. Ushbu sarfni‟
16  kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi.
 Bunda faqatgina ma lumot ko’rsatkichlari almashtirilib, massiv o’z joyida qoladi.‟
 Bu usul adreslar jadvalini saralash usuli deyiladi.
 Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin
 bir xil kalitlilar boshlang’ich tartibda qanday joylashgan bo’lsa, shu tartibda
 qoldirilishi maqsadga muvofiq bo’ladi (Bir xil kalitlilar o’zlariga nisbatan).
 Bunday usulga turg’un saralash deyiladi.

Saralash samaradorligini bir necha mezonlar bo’yicha baholash mumkin:

saralashga ketgan vaqt;

saralash uchun   talab qilingan operativ xotira ;

dasturni ishlab chiqishga ketgan vaqt.
Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki
 almashtirishlar sonini hisoblash mumkin.
Faraz qilaylik,   N = 0,01n2   + 10n   – taqqoslashlar soni. Agar   n < 1000   bo’lsa,
 u holda ikkinchi qo’shiluvchi katta, aks holda ya’ni,   n > 1000   bo’lsa, birinchi
 qo’shiluvchi katta bo’ladi.
Demak, kichkina   n   larda taqqoslashlar soni   n   ga teng bo’ladi, katta   n   larda esa
  n2   ga teng bo’ladi.
Saralashda taqqoslashlar soni quyidagi oraliqlarda bo’ladi:
1 dan n gacha; – ideal holatda.
17 Saralashning quyidagicha usullari bor:
  qat’iy (to’g’ridan-to’g’ri) usullar;
  yaxshilangan usullar.
Qat’iy usullarning afzalliklarini ko’rib chiqaylik:
1. Bilamizki, dasturlarning o’zlari ham xotirada joy egallaydi. To’g’ridan-to’g’ri
 saralash usullarining dasturlari qisqa bo’lib, ular tushunishga oson.
2. To’g’ridan-to’g’ri saralash usullari orqali saralash tamoyillarining asosiy
 xususiyatlarini tushuntirish qulay.
3. Murakkablashtirilgan usullarda uncha ko’p amallarni   bajarib talab qilinmasada ,
 ushbu amallarning o’zlari ham ancha murakkabdir. Garchi yetarlicha katta
 n larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar
 tezroq ishlaydi.
Shu joyni o’zida qat iy usullarni ishlash tamoyillariga ko’ra 3 ta toifaga bo’lish‟
 mumkin:
1.   To’g’ridan-to’g’ri qo’shish usuli (by insertion);
2. To’g’ridan-to’g’ri tanlash usuli (by selection);
3.To’g’ridan-to’g’ri  almashtirish usuli (by exchange).
To’g’ridan-to’g’ri qo ’ shish usuli bilan saralash algoritmi
Bunday usul karta o’yinida keng qo’llaniladi. Elementlar (kartalar) hayolan 
“tayyor”   a(1),...,a(i-1)   va boshlang’ich ketma-ketliklarga bo’linadi. Har
18  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’yiladi.
To’g’ridan-to’g’ri qo’shish orqali saralash algoritmi quyidagicha
bo’ladi:
for(inti=1;i   i="">
x=a[i];
x ni a[0]...a[i]oraliqning mos joyiga qo‘shish
}
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi.
 2-elementdan
 boshlab har bir elementni qarab chiqamiz, ya ni har bir element o’zidan oldin‟
 turgan
 element bilan solishtiriladi. Agar qaralayotgan element kichik bo’lsa, oldinda
 turgan element bilan o’rin almashadi va yana o’zidan oldinda turgan element bilan
 solishtiriladi, jarayon shu kabi davom etadi. Bu jarayon quyidagi shartlarning
 birortasi bajarilganda to’xtatiladi:
1.   x   elementi oldida uning kalitidan kichik kalitli  a(j)   elementi chiqqanda.
2.   x   elementi oldida element qolmaganda.
for(inti=1;i<=""   i="">
while(a[j]<=""   i="">
19 int   t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Algoritm samaradorligi
Faraz qilaylik, taqqoslashlar soni   C , o’rinlashtirishlar soni   M   bo’lsin. Agar
 massiv elementlari kamayish tartibida bo’lsa, u holda taqqoslashlar soni eng
 katta bo’lib, u ga teng bo’ladi, ya ni . O’rinlashtirishlar soni esa ga teng 	
‟
bo’ladi, ya ni . Agar berilgan massiv o’sish tartibida saralangan bo’lsa,	
‟
 u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik
 bo’ladi, ya ni , .
‟
1.3.QUIKSORT-TEZ SARALASH ALGORITMI
  Bu algoritm “bo’lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu 
algotirm rekursiv bo’lib, o’rtacha     N*log2N	
  ta solishtirish natijasida saralaydi.
 Algoritm berilgan massivni saralash uchun uni 2taga bo’lib oladi. Bo’lib olish 
 uchun ixtiyoriy elementni tanlab undan 2ta qismga ajratiladi. Lekin o’rtadagi 
20 elementni tanlab,massivning teng yarmidan 2ga ajratgan maqul.Tanlangan kalit 
elementga nisbatan chapdagi va o’ngdagi har bir element solishtiriladi. Kalit
 elementdan kichiklar chapga, kattalar o’ng tomonga o’tkaziladi. Endi massivning
 har ikkala tomonidan xuddi yuqoridagi amallar takrorlanadi.Ya ni bu oraliqlarni‟
 o’rtasidagi elementlar kalit sifatida olinadi va h.k.
Misol uchun rasmdagi massivni saralash algoritmini ko’rib chiqamiz.
1. Oraliq sifatida   0   dan   n-1   gacha bo’lgan massivning barcha elementlarini
 olamiz.
2. Oraliq o’rtasidagi kalit elementni tanlaymiz, ya ni	
‟
key=(+)/2, i=,
j=.
3-rasm. Quicksort algoritmida o’rinlashtirish
3.Chapdagi i-elementni  	
key   bilan solishtiramiz. Agar   key   kichik bo’lsa,
 keyingi qadamga
 o’tamiz. Aks holda   i++   va shu qadamni takrorlaymiz.
4. O’ngdagi   j -element bilan   key   solishtiriladi. Agar   key   katta bo’lsa,
 keyingi qadamga o’tamiz, aks holda    j— va shu qadamni takrorlaymiz.
5.   i-   va   j- elementlarning o’rni almashtiriladi.
21  Agar   i<=j   bo’lsa, 
3-qadamga o’tiladi.
Birinchi o’tishdan keyin tanlangan element o’zining joyiga kelib joylashadi.
6. Endi shu ko’rilayotgan oraliqda   key   kalitning chap tomonida elementlar mavjud
 bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko’riladigan
 oraliq   0    dan   key-1 gacha deb belgilanadi va 2-qadamga. Aks holda keyingi
 qadamga o’tiladi.
7. Endi shu ko’rilayotgan oraliqda   key   kalitning o’ng tomonida elementlar mavjud
 bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya ni ko’riladigan	
‟
 oraliq   key+1   dan   n-1   gacha deb belgilanadi va 2-qadamga o’tiladi. Aks
 holda algoritm tugaydi.
2.Bob. SARALASHNING O’RNIGA QO’YISH ALGORITIMI
2.1. O'rniga qo'yish bilan saralash algoritmi
 Ushbu saralash algoritmining asosiy mohiyati saralangan ro'yxatga yangi el е m е nt 
qo'shishda uni “o'z joyiga” joylashtirishdan iboratdir. Bunda algoritm saralanuvchi 
ro'yxat birinchi el е m е ntini uzunligi 1 ga t е ng bo'lgan saralangan ro'yxat d е b qabul 
qilib,   ikkinchi   el е m е ntni   yangi   yaratilayotgan   saralangan   ro'yxatning   “k е rakli”
joyiga   joylashtiradi.   So'ngra   b е rilgan   ro'yxatning   uchinchi   el е m е nti   ham
saralangan   ikki   el е m е ntli   ro'yxatdagi   o'z   joyiga   joylashtiriladi   va   hokazo.   Ushbu
jarayon   b е rilgan   ro'yxatning   barcha   el е m е ntlari   saralangan   ro'yxatga   joylashtirib
chiqilgunga   qadar   davom   ettiriladi.   O'rniga   qo'yish   algoritmining   ifodasi
quyidagidan   iborat:   InsertSort(List,N)   For   i=2   to   N   do   newElement=list[i]
l о cation=i-1   while   (location)   >=1)   and(list[location]>   newElement)   do
22 list[location+1]   =   list[location]   location=   location-1   end   while   list[location+1]   =
newElement   end   For   Ushbu   algoritm   newElement   o'zgaruvchisiga   yangi   o'rniga
qo'yiluvchi   qiymatni   kiritadi.   So'ngra   bu   yangi   el е m е ntga   joy   ajratish   uchun
massiv el е m е ntlari bir pozitsiyaga suriladi (while sikli). Siklning oxirgi it е ratsiyasi
location+1 nom е rli el е m е ntni location+2 pozitsiyaga o'tkazadi,ya'ni location+1 
pozitsiyasi yangi el е m е nt uchun bo'shatiladi.
2.2.Birlashtirish bilan saralash algoritmi
  Ushbu   saralash   algoritmi   r е kursiv   xarakt е rga   egadir.   Bitta   el е m е ntdan   iborat
bo’lgan   ro’yxat   saralangan   bo’lganligi   uchun   algoritm   ro’yxatni   bir   el е m е ntli
ro’yxatlarga ajratib, so’ngra ularni k е tma-k е t birlashtiradi.Bunda ro’yxat k е tma-k е t
ikki   qismga   ajratib   boriladi.   Ikkiga   bo’lish   jarayoni   bo’lak   ro’yxat   birinchi
el е m е ntining   nom е ri   shu   bo’lakdagi   oxirgi   el е m е nti   nom е ridan   kichik   bo’lgunga
qadar davom etadi. Agar navbatdagi bo’lakda bu shart bajarilmasa, bitta el е m е ntli
bo’laklar   hosil   bo’lgan   d е b   hisoblanadi.   Uzunligi   birga   t е ng   bo’lgan   ro’yxatlar
uchun   ikkita   murojaatdan   so’ng   ushbu   ikki   ro’yxatni   birlashtiruvchi   prots е dura
chaqiriladi. Buning natijasida uzunligi ikkiga t е ng bo’lgan saralangan ro’yxat hosil
bo’ladi. K е yingi bosqichda ikkiga t е ng uzunlikdagi saralangan ro’yxatlar uzunligi
to’rtgat е ng   bo’lgan   saralangan   ro’yxatlarga   birlashadi.   Bu   jarayon   ikkita
saralangan yarim ro’yxatlar birlashuvchi qadamgacha davom etadi.
2.3.Diskli  хо tir а  qurilm а sining tuzilishi
 T а shqi s а r а l а sh j а r а yoni t а shqi  хо tir а d а  s а ql а nuvchi  ах b о r о tl а rni s а r а l а sh 
v а zif а sini b а j а r а di. T а shqi s а r а l а sh j а r а yoni ichki s а r а l а shd а n k а tt а  f а rq qil а di. 
Chunki   t а shqi   f а yll а rg а   mur о j аа t   to’g’rid а n   –   to’g’ri   em а s,   k е tm а -k е t     usuld а
а m а lg а   о shiril а di.   Bund а   ах b о r о tl а rni   f а q а t   bl о kl а b   o’qish   mumkin.   T а shqi
s а r а l а sh   j а r а yonini   tushunish   uchun   diskl а rning   fizik   tuzilishi   bil а n   umumiy
t а nishib   chiqish   k е r а k   bo’l а di.   Diskl а rning   t а shqi   sirti   m а gnitli   q о pl а mg а   eg а
bo’lib, ul а r d о imiy k а tt а  t е zlik bil а n o’z o’qi  а tr о fid а   а yl а n а di. Diskl а rning h а r bir
ish   s о h а sig а   bitt а   o’qish-yozish   qurilm а si   o’rn а tilg а n.   Ах b о r о tl а rg а   mur о j аа t
v а qtid а   o’qish-yozish   qurilm а si   t о m о nid а n   tr е kl а r   d е b   а t а luvchi   diskd а gi
m а ’lum о tl а r   yozilg а n   yo’l а kch а l а rd а n   b е rilg а nl а r   o’qil а di.   Bu   tr е kl а r   yig’indisi
j о riy   silindr   d е b   а t а l а di.O’qish-yozish   qurilm а l а ri   m ах sus   sht а ng а g а   o’rn а tilg а n
bo’lib, bu sht а ng а  burilg а nd а  o’qish-yozish qurilm а si b о shq а  silindrg а  o’tq а zil а di. 
Silindrl а r   sht а ng а ning   bir   t о m о ng а   h а r а k а ti   v а qtid а   o’qish-yozish   qurilm а l а ri
bl о kining   ul а rg а   mur о j аа t   qilish   t а rtibid а   n о m е rl а n а di.   B е rilg а nl а r   el е m е ntl а ri
23 о r а sid а gi m а s о f а  ular j о yl а shg а n silindrl а r n о m е rl а ri f а rqid а n ib о r а t bo’l а di. Хо tir а
el е m е ntl а rini   а dr е sl а sh   ul а r   j о yl а shg а n   silindr   d о ir а sid а   а m а lg а   о shiril а di.   F а yl
а dr е sl а r t а rtibi  bo’yich а   yozil а di,   а mm о   bo’sh j о y bo’lm а g а nd а , b о shq а   silindrg а
h а m   yozilishi   mumkin.Disk а d а gi   ах b о r о tl а rg а   mur о j аа t   а s о siy   хо tir а d а gi
ах b о r о tl а rg а  mur о j аа td а n  а nch а gin а  s е kin  а m а lg а   о shiril а di.Chunki bund а y 
mur о j аа t v а qti bu j а r а yond а  bir n е ch а  b а j а ril а dig а n  а m а l а rg а  k е t а dig а n v а qtd а n 
k е lib chiq а di: 
1. Silindr k е r а kli el е m е ntining o’qish-yozish qurilm а si t а gid а n 
o’tishini ko’rish v а qti;
 2. O’qish-yozish qurilm а sining b о shq а  silindrg а  
o’tq а zilishini ko’rish v а qti; 
3. T а shqi s а r а l а sh v а qti;
 4. T а shqi s а r а l а sh v а qti h а m 
o’z n а vb а tid а  bir n е cht а   а m а ll а r b а j а rilishig а  k е t а dig а n v а qtd а n h о sil bo’l а di:
 5. qisml а rining ichki s а r а l а nishi;
 6. B е rilg а nl а rning to’rt m а rt а  diskk а  yozilishi v а  
o’qilishi; 
7. O’qish-yozish  а ktl а ri  о r а sid а gi g о l о vk а  yurishl а ri;
  8. T а rtibl а ng а n qisml а rning birl а shuvi j а r а yonid а gi   хо tir а d а gi h а r а k а tl а r; T а shqi
хо tir а d а gi   f а yll а rni   s а r а l а sh   muhim   а m а liy   а h а miyatg а   eg а dir.   Bund а y   s а r а l а sh
j а r а yoni   n а tij а sid а   t а shqi   хо tir а d а gi   ах b о r о tl а rg а   mur о j аа t   v а qti   s е zil а rli
k а m а ytiril а di   v а   хо tir а g а   ах b о r о tl а r   o’qish-yozish   j а r а yoni   а nch а   t е zl а sh а di.
T а shqi   хо tir а d а gi f а yll а rni s а r а l а sh f а yl bl о kl а ri orqali b а j а ril а di. Bund а y s а r а l а sh
а lg о ritml а rid а n   biri   birl а shuv   yo’li   bil а n   s а r а l а sh   а lg о ritmidir.   Birl а shuv
tushunch а si   ikki   yoki   und а n   о rtiq   t а rtibl а ng а n   k е tm а -k е tlikl а rning   bitt а
t а rtibl а ng а n k е tm а -k е tlikk а   а yni p а ytd а  j о riy el е m е ntl а rni siklik t а nl а sh yord а mid а
а lm а shtirish(k е ltirish) ni bildir а di.Birl а shuv j а ryoni s а r а l а sh j а r а yonl а ri ichid а  eng
s о dd а   j а r а yon   his о bl а n а di.   Tashqi   saralash   usullarining   katta   qismi   quyidagi
umumiy   tamoyillarga   rioya   qiladi.   Saralanuvchi   fayl   bo’ylab   birinchi   u   o’tishda
xajmi   taxminan   operativ   xotira   xajmiga   mos   keluvchi   bloklarga   ajratiladi.
Keyinchalik   ushbu   fayl   bloklari   saralanadi.   So’ngra   saralangan   bloklarning
birlashuvi amalga oshiriladi. Bu maqsadda bir necha o’tishlar amalga oshirilib, har
bir   o’tish   jarayonida   saralanganlik   darajasi   ortib   boradi   va   jarayon   fayl   to’la
saralanib bo’lgunga qadar davom ettiriladi. Bunday yondashuv birlashuvli saralash
deb ataladi. Birl а shuvli saralash j а r а yonini r еа liz а tsiya qiluvchi bir n е cht а   а lg о ritm
m а vjud. Bul а rd а n biri B о uz-N е ls о n  а lg о ritmidir.
24 XULOSA
Xulosa   qilib   aytish   mumkinki,   saralash   deb,   berilgan   obyektlar   ketma-ketligini
ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha
ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktabda jismoniy tarbiya
dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida
esa   sinf   jurnalidagi   familiyalar   ketma-ketligiga   qarab   topshirishadi.   Shu   yerning
o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi
sinf   jurnalida   alfabit   tartibida   saralanadi.   Saralash   jarayoni   qanday   kechadi?
Saralash   jarayoni   taqqoslashga   asoslangan   jarayon   hisoblanadi.   Biror   bir
ma’lumotni   saralash   yoki   qandaydir   qolipga   solish   juda   ham   muhim.   Sababi,
tartibsiz   ma’lumotlar   bilan   ishlash   doimo   noqulayliklar   keltirib   chiqaradi   va
bunday   tizim   sekin   va   xatoliklarga   moyil   bo’ladi.   Tartiblangan   ma'lumotlar
hammaga   yoqadi.   Saralash   ma'lumotlarni   kerakli   ketma-ketlikda   tartibga   solish
imkonini   beradi,   masalan,   o'sish   yoki   kamayish   tartibida.   Tasavvur   qiling-a,   siz
yirik   kompaniyada   ishlaysiz   va   siz   xodimlarning   ismlarini   maoshiga   qarab
tartiblashingiz kerak. Buning uchun saralash algoritmlari qo'llaniladi. Dasturlashda
turli xil saralash algoritmlar mavjud. Masalani turi mazmuniga qarab turib saralash
algoritmlarning   biri   qo’llaniladi.   Biz   yuqorida   eng   ko’p   qo’llaniladigan   saralash
algoritmlarini ko'rib chiqdik. Saralash algoritmlarining samaradorligini baholashda
ikki mezon bo’yicha fazo va vaqt murakkabligi hisoblanadi. Fazoviy murakkablik
–   bu   algoritmni   bajarish   uchun   foydalaniladigan   xotira   hajmi   bilan   ifodalanadi.
Fazoviy   murakkablik   yordamchi   xotira   va   kirish   xotirasini   o'z   ichiga   oladi.
Yordamchi  xotira -  kirish  ma'lumotlariga  qo'shimcha  ravishda  algoritm  egallagan
qo'shimcha   joy.   Algoritmlarning   fazoviy   murakkabligini   hisoblashda   hisobga
olinadi.   Vaqtning   murakkabligi   –   bu   kirish   ma'lumotlarini   hisobga   olgan   holda
algoritm   vazifani   bajarishga   sarflagan   vaqtni   bildiradi.   Har   bir   saralash   algoritmi
25 o'ziga   xos   vaqt   va   makon   murakkabligiga   ega.   Vazifalarga   qarab,   taqdim   etilgan
algoritmlarning   biridan   foydalanish   mumkin.   Lekin   mening   sub'ektiv   fikrimcha,
tez tartiblash eng yaxshi algoritmdir. U asosiy tayanch elementni tanlash imkonini
beradi va massivni 3 qismga ajratadi: kichik, teng va tayanchdan katta.
FOYDALANILGAN   ADABIYOTLAR   RO‘YXATI
1.   А . В .   Трухин .   «Об   использовании   виртуальных   лабораторий   в
образовании» // Открытое и дистанционное образование. - 2002. - № 4 (8). 
2.   Соколов   А.Г.   Природа   экранного   творчества:   психологические
закономерности. М.: Изд.А.Дворников, 2004. 638 с. 
3. Корнеев Г. А. Технология разработки визуализаторов алгоритмов / Труды
II межвузовской конференции молодых уче?ных. СПб.:  СПбГУ ИТМО, 2005,
с. 18-23 
4. Бергер, А. Видеть – значит верить. Введение в зрительную коммуникацию.
М.: Издательский дом «Вильямс», 2005. 288 с. 
5.   Федоров   А.В.   Проблемы   аудиовизуального   восприятия   //   Искусство   и
образование. 2001. № 2. С. 57–64. 
6.   Соловов   А.В.   Eлектронное   обучение:   проблематика,   дидактика,
технология. Самара: «Новая техника», 2006. – 464 с. 
7.https://fayllar.org/malumotlarni-saralash-algoritmlarini-tartibli-statistikasi.html
8.  https://uz.wikipedia.org/wiki/Bubble_sort
9.  https://uz.wikipedia.org/wiki/Selection_sort
10.  https://uz.wikipedia.org/wiki/Insertion_sort
26 27 28 29 30 31 32 33 34 35 36

MAVZU: Ma’lumotlarni saralash. Saralashning o’rniga qo’yish (vstavka) algoritimi. MUNDARIJA KIRISH 1.Bob.SARALASH TUSHUNCHASI 1.1.Saralash tushunchasi. 1.2.Algoritm samaradorligi. 1.3.Quiksort-tez saralash algoritmi. 2.Bob. SARALASHNING O’RNIGA QO’YISH ALGORITIMI 2.1.O’rniga qo’yish bilan saralash algoritmi. 2.2.Birlashtirish bilan saralash algoritmi. 2.3.Diskli xotira qurilmasining tuzilishi. FOYDALANILGAN ADABIYOTLAR RO‘YXATI. 1

KIRISH Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi. Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin:  Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin.  Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi. Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi. Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi. Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor). Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan 2

tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi. 1.Bob.SARALASH TUSHUNCHASI 1.1.SARALASH TUSHUNCHASI Saralash - tartiblash ( Sorting Algorithms ) deb, berilgan obyektlar ketma- ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktab jurnalida o'quvchilar familiyasi alifbo tartibiga ko'ra saralangan bo'ladi. Masalan bizga sonlar qatori berilgan: 8, 23, 0, -50, 100 Bu qatorni kichigidan kattasiga qarab yoki kattasidan kichigiga qarab saralashimiz mumkin. Bu saralashni amalga oshirish jarayoni Saralash algoritmi deyiladi. Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Yuqoridagi sonli qatorni kichigidan kattasiga qarab tartiblaganimizda -50, 0, 8, 23, 100 ko'rinishiga keladi. Biz buni qanday amalga oshirdik. Bunda har xil usuldan foydalanish mumkin va mana shu algoritm turlaridir Biz algoritmlardan bittasidan foydalanib yuqoridagi sonli qatorni tartiblaymiz. Avval, sonli qatordan eng kichigini topamiz va uni ro'yxatnin g boshiga qo'yamiz. Har bir sonni boshqasi bilan solishtirib chiqamiz. Agar son o'zidan keyingi sondan kichik bo'lsa, son shu joyida qoladi, agar katta bo'lsa sonlarning o'rnini almashtiramiz. Saralash asosan ro'yxat, massiv elementlarida amalga oshiriladi. Masalan sizning sinfingizda 5 ta o'quvchi bor. Ularni familiyasini alifbo tartibida saralash mumkin. Sonlar berilishi: 23, 54, 3, 22, 1, 45; Eng kattasini boshiga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turipti) Shu 3

tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son) Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi) Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi) Saralangan tartib quyidagi holatga keldi: 1, 3, 22, 23, 45, 54; Bizning miyamiz o`zi optimal deb bilgan yo`nalishdan ketadi va biz uchun faqat bitta saralash algoritmi mavjud. Ammo dasturlashda bunday deb bo`lmaydi. Dasturlashga talab ortib, bu soha rivojlanib borgani sari unda bir qator sohalardagi kabi tezlikni oshirish muammosi paydo bo`ladi. Chunki ilk kompyuter tizimlarida kompyuter tizimining 30% tezligi, operativ xotirasi saralashga sarflanar edi. Shu o`rinda savol tug`iladi, operatsion tizimlarda ham saralashdan foydalaniladimi? Albatta ha! Fikrimiz isbotini hozirda keng foydalaniladigan Total Commander dasturi isbotlaydi. Unda bir necha xil saralash mavjud: fayl turi, nomi, o`zgartirilgan sanasi va o`lchami. Har birini o`sish yoki kamayish tartibida saralash mumkin. Ha aytgancha, hozirgi tizimlar 30% emas anchagina kamroq tezlik va xotira sarflashadi. Chunki tezlik masalasi tobora yuqori cho`qqiga chiqayotgan va ishlanayotgan ma`lumotlar o`lchami oshib borayotgan bir paytda sekin ishlovchi algoritmlardan foydalanish kulguli. Ma`lumotlar o`lchamlari esa juda katta, shu sababli ularni aniq va tez saralashga ehtiyoj mavjud. Buni amalga oshirish uchun esa yangi algoritmlarga ehtiyoj tug`ila boshladi. Buni yechimi sifatida bir necha turdagi algoritmlardan foydalaniladi. Saralash algoritmi turlari  Bubble sort  Selection sort  Insertion sort  Quick sort  Merge sort 4

Bubble sort Bubble sort ikki qo'shni elementni solishtirish va ular mo'ljallangan tartibda bo'lmaguncha, ularni almashtiradigan tartiblash algoritmidir. Xuddi suv yuzasiga ko'tarilgan havo pufakchalarining harakati kabi, massivning har bir elementi har bir iteratsiyada oxirigacha harakat qiladi. Shuning uchun u pufakchali saralash deb ataladi. BubbleSort “Bubble sort” bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar bilan solishtirishga asoslangan algoritm hisoblanadi. Unda yonma-yon turgan elementlardan chapdagisi o‘ngdagidan kattaligi aniqlansa, bu ikkala son o`rni almashtiriladi. Bu jarayon almashtirish kerak bo`lmay qolguncha davom etadi, ya`ni barcha elementlar o‘sish tartibida bo‘lib qolguncha. “Bubble sort” nisbatan ko`p vaqt talab qiluvchi saralash algoritmi hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni taqriban n*n ga teng. Bu, n kichik son bo`lsa unchalik sezilmaydi. Sababi, hozirgi zamonaviy kompyuterlar uchun bu takrorlanish soni qiyinchilik tug`dirmaydi. Ammo butun boshli ma`lumotlar bazasidagi ma`lumotlarni saralash talab 5