logo

Ma’lumotlarni saralash usullari

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

283.34375 KB
1Ma’lumotlarni saralash usullari
MUNDARIJA
KIRISH ............................................................................................................ 2
I Bob. Saralash usulining nazariy asoslari. ................................................ 3
1.Tuzilma elementlarini saralash ............................................................... 3
1.qat'iy (to'g'ridan-to'g'ri) usullar; .................................................................... 3
 2.Saralash tushunchasi va uning vazifasi ................................................. 4
3. Ma lumotlarni tartiblash usullariʼ ........................................................... 5
4. Guruhlash turlari .................................................................................... 6
1. Maqsad va vazifalarga qarab ....................................................................... 6
2. Guruhlash belgilari soniga qarab ................................................................. 6
3. Manbaiga qarab ........................................................................................... 6
4. Tipologik guruhlash .................................................................................... 6
5. Analitik guruhlash ....................................................................................... 7
6. Tuzilmaviy guruhlash .................................................................................. 7
7. Oddiy guruhlash .......................................................................................... 7
8. Murakkab guruhlash .................................................................................... 7
9. Birlamchi guruhlash .................................................................................... 7
10. Ikkilamchi guruhlash ................................................................................. 7
1.  tipologik; .................................................................................................... 7
2.  analitik; ....................................................................................................... 7
2.Selection sort ........................................................................................ 10
3.Insertion sort ......................................................................................... 10
4.Merge sort ............................................................................................. 11
5.Quicksort .............................................................................................. 12
6. Heapsort ............................................................................................... 13
7.Radixsort .............................................................................................. 15
 XULOSA ...................................................................................................... 20
ADABIYOTLAR RO’YXATI ...................................................................... 21
ILOVALAR ................................................................................................... 22
ILOVA 1. Quicksort usuli kodi ............................................................... 22
ILOVA 2. Megesort usuli kodi ................................................................ 23
 i = 0; .............................................................................................................. 23
 j = 0; .............................................................................................................. 23
 k = left; ......................................................................................................... 23 2 KIRISH       
Ishdan   maqsad:   Ushbu   laboratoriya   ishining   maqsadi   talabalar   qanday
saralash   usullari   va   algoritmlari   mavjudligini   va   ularning   samaradorliklarini
baholashni   o'rganishlari   kerak.   Shu   asosda   saralash   usullarini   qiyosiy   tahlil
qilishlari va ularga oid dasturlar tuzishni o'zlashtirishlari kerak.
Qo'yilgan   masala:   Talabalar   topshiriq   variantiga   mos   saralash   usuli
yordamida masalani yechish dasturini yaratish ko'nikmasiga ega bo'lishlari kerak.
Ish tartibi:
1.  Tajriba ishi nazariy ma'lumotlarini o'rganish;
2.  Berilgan topshiriqniтп algoritmini ishlab chiqish
3.  C++ dasturlash muhitida dasturni yaratish;
4.  Natijalarni tekshirish;
5.  Hisobotni tayyorlash va topshirish 3I Bob. Saralash usulining nazariy asoslari.          
1.Tuzilma elementlarini saralash
Ma'lumotlarni   kompyuterda   qayta   ishlashda   elementning   informatsion
maydoni   va   uning   mashina   xotirasida   joylashishini   bilish   zarur.   Shu   maqsadda
ma'lumotlarni   saralash   amalga   oshiriladi.   Demak,   saralash   –   bu   ma'lumotlarni
kalitlari bo'yicha doimiy ko'rinishda mashina xotirasida joylashtirishdan iborat. Bu
yerda doimiylik ma'lumotlarni massivda kalitlari bo'yicha o'sishi tartibida berilishi
tushuniladi.
Ma'lumotlarga   qayta   ishlov   berilayotganda   ma'lumotning   informatsion
maydonini hamda uning mashinada joylashishini (adresini) bilish zarur.
Saralashning ikkita turi mavjud: ichki va tashqi:
1.ichki saralash bu operativ xotiradagi saralash;
2.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
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:
1.   saralashga ketgan vaqt;
2.   saralash uchun talab qilingan operativ xotira;
3.  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:
dan gacha; – ideal holatda.
Saralashning quyidagicha usullari bor:
1.qat'iy (to'g'ridan-to'g'ri) usullar;
2.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. 43.       Murakkablashtirilgan   usullarda   uncha   ko'p   amallarni   bajarish   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).
                             2.Saralash tushunchasi va uning vazifasi
Saralash   –   bu   berilgan   to‘plam   elementlarini   biror   bir   tartibda   (o‘sish   yoki
kamayish) joylashtirish jarayonidir.
Saralash   (inglizcha   sorting   -   tasniflash,   tartiblash)   -   tanlangan   mezonga
qarab biror narsani ketma-ket joylashtirish yoki guruhlarga bo'lish.
Saralash–   bu   massiv   elementlarini   tartiblash   (o’sish,   kamayish,   oxirgi   raqami,
bo’luvchilari bo’yicha, …)
Saralash   deb,   berilgan   obyektlar   ketma-ketligini   ma`lum   mantiqiy   tartibda
qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq
bo`lishi mumkin. 
Ma'lumotlarni saralash - uni qandaydir atributga ko'ra tartibga solishdir.
Saralashdagi qiyinchiliklar quyidagi hollarda mavjud bo’ladi:
   ma'lumotlar   massivlari   katta   bo’lganda   -   minglab,   o'nlab   va   yuz   minglab
elementlar;
   ma'lumotlarga   murojaat   qilish   qiyin   bo'lishi   mumkin   (masalan,   ular
ma’lumotlar oqimi bo’lganda);
 kompyuterning   imkoniyatlari   yetarli   emas   va   dasturlash   tiliga   kiritilganidan
ko'ra tejamkorroq algoritmlar kerak.
Bunday hollarda saralashning ixtisoslashtirilgan algoritmlarini tanlash kerak,
zarurat bo’lsa ularni masalaga qarab optimallashtirish mumkin.
Saralashdan   maqsad   -   tartiblangan   to‘plamda   kerakli   elementni   topishni
osonlashtirishdan iborat.
dasturlarni translyasiya qilishda;
ma’lumotlar majmuasini tashqi xotirada tashkil qilishda;
kutubxonalar, kataloglar, ma’lumotlar bazasini yaratishda va boshqalar.
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 5algoritm   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 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.
3. Ma lumotlarni tartiblash usullariʼ
     Alfabetik   tartib:   Odatda,   ma'lumotlar   alfabetik   tartibda   joylashgan   holda
tartiblanadi. Misol uchun, ismilar ro'yxatini A dan Z gacha joylashgan tartibda
joylashtirish mumkin.
     Sanash   tartibi:   Bu   tartiblash   usuli   ma'lumotlarni   sonlarga   asoslangan
tartiblashdir.   Misol   uchun,   telefon   raqamlarini   yoki   o'yinlardagi   darajalarni
tartiblashda sanash tartibi qo'llaniladi.
     Kronologik   tartib:   Ma'lumotlarni   vaqtni   yoki   yilni   asoslashga   asoslangan
tartiblash   usuli.   Misol   uchun,   tarixiy   voqealar   ro'yxati   yoki   bir   yil   davomida
sodir bo'lgan tadbirlar ro'yxati kronologik tartibda joylashtiriladi. 6     Tug'ilgan   yil   bo'yicha   tartiblash:   Bu   tartiblash   usuli   ma'lumotlarni   tug'ilgan
yiliga   ko'ra   tartiblashni   bildiradi.   Misol   uchun,   shaxslar   ro'yxati   tug'ilgan   yili
bo'yicha tartiblangan bo'lishi mumkin.
    Ma'lumotlar turlariga asoslangan tartiblash: Bu tartiblash usulida ma'lumotlar
turiga   qarab   joylashtiriladi.   Misol   uchun,   kitoblar   ro'yxati   avtorlariga,
janrlariga yoki nashr etilgan yillariga qarab tartiblangan bo'lishi mumkin.
     Anket   tartibi:   Bu   tartiblash   usulida   ma'lumotlar   anket   topshiruvchilari
tomonidan   berilgan   tartiblash   bo'yicha   joylashtiriladi.   Misol   uchun,   anket
topshiruvchilari   tomonidan   berilgan   preferanslarga   qarab   tartiblangan   bo'lishi
mumkin.
     O'rnatish   tartibi:   Bu   tartiblash   usuli   ma'lumotlarni   bir-birining   o'rniga   qarab
joylashtirish   bilan   bog'liq   bo'ladi.   Misol   uchun,   elementlar   jadvallarida
kimyoviy elementlarning atom raqamlariga ko'ra tartiblangan bo'lishi mumkin.
Bu   faqat   bir   necha   tartiblash   usullarining   misollaridir.   Ma'lumotlarni   tartiblash
usullari   juda   keng   qamrovli   bo'lishi   mumkin   va   maqsadga   qarab   o'zgarishi
mumkin.
Alfabetik   tartib:   Apple,   Banana,   Cherry,   Date,   Elderberry,   Fig,   Grape,
Honeydew, Jackfruit, Kiwi.
Sanash tartibi: 3, 8, 12, 15, 20, 25, 30, 35, 40, 45.
Kronologik   tartib:   2005,  2008,   2010,  2013,   2015,  2017,   2019,  2021,   2022,
2023.
Tug'ilgan yil bo'yicha tartiblash: John (1982), Kate (1990), Michael (1975),
Emily (1988), Daniel (1985), Sophia (1995), David (1978), Olivia (1992), Robert
(1980), Emma (1998).
Ma'lumotlar   turlariga   asoslangan   tartiblash:   Avtomobillar:   Toyota,   BMW,
Honda, Mercedes-Benz, Ford, Audi, Chevrolet, Volkswagen, Nissan, Hyundai.
Anket tartibi:  Kitob o'qish doimiyligi bo'yicha tartiblash: Sifatli o'quvchilar,
Ko'p o'quvchilar, O'rtacha o'quvchilar, Kam o'quvchilar.
O'rnatish tartibi:  Kimyoviy elementlar asar bo'yicha tartiblash: S, Cl, Ti, Fe,
Zn, Ag, Sn, I, Pt, Au.
4.  Guruhlash turlari
Guruhlash statistik bog‘lanishlar va qonuniyatlarni aniqlash, o‘rganilayotgan
to‘plamning   tuzilishini   o‘rganish   va   ho‘jaliklarning   sotsial-iqtisodiy   tiplarini
tasvirlash maqsadida bajariladi. Uning har xil turlari va shakllari mavjud.
Guruhlash turlari
1.  Maqsad va vazifalarga qarab
2.  Guruhlash belgilari soniga qarab
3.  Manbaiga qarab
4.  Tipologik guruhlash 75.  Analitik guruhlash
6.  Tuzilmaviy guruhlash
7.  Oddiy guruhlash
8.  Murakkab guruhlash
9.  Birlamchi guruhlash
10.  Ikkilamchi guruhlash
                            Guruhlash turlari.
Guruhlash maqsad va vazifalariga qarab uch turga bo‘linadi:
1.    tipologik;
2.    analitik;
3.   tuzilmaviy guruhlash.
            Tipologik   guruhlash   –   bu   to‘plamni   sotsial-iqtisodiy   tiplarga   ajratishdir.
Tipologik   guruhlash   deganda,   o‘rganilayotgan   hodisalar   to‘plamini   sotsial-
iqtisodiy   tiplarga   taqsimlash   tushuniladi.   Tip   so‘zi   quyidagi   lug‘aviy   mazmunga
ega:   a)   bir   turdagi   narsa   uchun   umumiy   bo‘lgan   namuna;   b)   biologik   hayvon   va
o‘simliklar   sistematikasidagi   o‘zaro   o‘xshash   sinflarni   birlashtiradigan   oliy
bo‘linma;   c)   bir   qator   ichki   yoki   tashqi   belgilar   yagonaviyligi   asosida   birlashgan
kishilar kategoriyasi.
Sotsial   iqtisodiy   tip   jamiyatda   iqtisodiyotda   bajaradigan   funksiyalar   va
tutgan o‘rinning umumiyligi bilan belgilanadi
Sotsial-iqtisodiy   tip   deganda   jamiyatda,   iqtisodiyotda   bajaradigan
funksiyalari   va   tutgan   o‘rni   umumiyligiga   asoslangan   ho‘jalik   yurituvchi
subyektlar,   shaxslar,   qandaydir   narsalar   (ishlab   chiqarish   vositasi,   ishlovchi   kuch
va h.k.) kategoriyasi, to‘plami tushuniladi.
Tipologik   guruhlashni   tuzish   algoritmi   quyidagi   ketma-ket   operatsiyalarni
bajarishdan iborat:
            1.   o‘rganilayotgan   hodisalarni   qanday   tiplarga   ajratish   dastlab   belgilab
qo‘yiladi;
      2.  tiplar tasvirini shakllantiruvchi guruhlash belgilari saylab olinadi;
      3.  guruhlarning oraliq chegaralari aniqlanadi;
            4.   guruhlash   belgilari   birikmasi   asosida   har   qaysi   tip   guruhiga   tegishli
to‘plam birliklari soni aniqlanadi;
       5.  ayrim tiplarni tasvirlash uchun tegishli birliklar haqidagi boshlang‘ich
ma’lumotlar asosida umumiy ko‘rsatkichlar hisoblanadi.
Guruhlash   belgilarini   ixtisoslashtirish   -   bu   sharoitlarga   moslashtirib
guruhlash belgilarini o‘zgartirib turishdir.
Ayrim  hollarda tiplarning shakllanish  sharoitlarini  ifodalaydigan guruhlarni
har   xil   belgilar,   masalan   ko‘p   energiya   talabchan   tarmoqlarda   -   iste’mol   qilingan
elektroenergiya, ko‘p xom-ashyo talabchan tarmoqlarda - tovar - moddiy zaxiralar,
mehnat   talabchan   tarmoqlarda   -   ishchilar   soni,   kapital   talabchan   tarmoqlarda   -
asbob-uskunalar   qiymati   asosida   tuzish   mumkin.   Bunday   tartibda   guruhlash
belgilarini olish guruhlar belgilarini ixtisoslashtirish deb yuritiladi. Shu bilan birga
tiplarni   to‘laroq   belgilash   maqsadida   konkret   sharoitni   hisobga   olib   guruhlar
oralig‘ini ham ixtisoslashtirish tavsiya etiladi. 8Tuzilmaviy   guruhlash   -   bu   bir   belgi   asosida   to‘plam   tizilishini   tasvirlovchi
taqsimot qatoridir.
Tuzilmaviy   guruhlash   odatda   ma’lum   bir   belgiga   qarab   to‘plam   tuzilishini
ta’riflaydi. Buning uchun dastlab bir belgi asosida taqsimot qatori tuziladi, so‘ngra
har   qaysi   guruh   uchun   tuzilmani   ta’riflovchi   to‘plama   ko‘rsatkichlar,   masalan
guruhlash   belgisining   guruhlardagi   yig‘ma   hajmi   va   u   bilan   yaqindan   bog‘liq
bo‘lgan belgilar to‘plama miqdorlari hisoblanadi va nihoyat ularga asoslanib ayrim
guruhlarning umumiy to‘plamdagi hissalari aniqlanadi.
Tuzilmaviy   guruhlash   taqsimot   qatorlari   bilan   umumiylikka   ega,   ammo
ulardan qator jihatlari bilan farq qiladi.
Tuzilmaviy   guruhlashlar   bilan   taqsimot   qatorlari   bir   biriga   o‘xshashib
ketadi, ammo ular vazifalari va tuzilish jihatidan bir biridan farq qiladi. Tuzilmaviy
guruhlashda ko‘zlangan maqsad - to‘plam tuzilishini o‘rganish. Buning uchun har
bir  tuzilma bir to‘da ko‘rsatkichlar yordamida tavsiflanishi  kerak, bu holda uning
turli   jihatlari   oydinlashadi.   Taqsimot   qatorlari   esa   statistik   to‘plam   tuzilmaviy
xususiyatlarini va qonuniyatlarini aniqlash uchun xizmat qiladi.
Tuzilmaviy   guruhlashlar   tuzilishidagi   o‘zgarishlarni   dinamika   va   fazo
jihatidan statistik o‘rganish va miqdoriy baholash imkonini  beradi. Buning uchun
ikki   usuldan   foydalanish   mumkin:   biri   -   har   bir   to‘plamning   ichidagi   farqlarni
miqdoriy   baholashga   asoslanadi,   ikkinchisi   esa   -   to‘plamlar   tuzilishi   orasidagi
farqlarni baholashga tayanadi . 9II Bob. Saralash usullarining ishlash strukturasi.
1.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.
1-rasm qo’shni elementlarni solishtirish va tartiblash
”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   etilsachi?   Albatta	
ʼ ʼ 10vaqtdan   yutqazamiz.   Ammo,   bu   algoritm   saralash   algoritmlarini   tushunib   olish
uchun ilk qadam hisoblanadi.
Bubble Sort Misol :
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
               
2.Selection sort
Selection sort — Tanlab saralash bu — oddiy tartiblash algoritmidir. 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 tuzatdim.
Eng kichik element tartiblanmagan massivdan tanlanadi va eng chap element
bilan   almashtiriladi   va   bu   element   tartiblangan   massivning   bir   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 (n2), bu yerda n -elementlar	
ʻ
soni.
2-rasm elementlarni tartiblash.
3.Insertion sort
Insertion   sort:   Ma'lumotlarni   to'g'ri   joylashtirishda   bir-birini   almashtirish
usuli. 11Insertion   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	
ʻ
Insertion   sort   (Joylab   saralash)   ham   tartibsiz   array   elementlarini   saralash   uchun
mo’ljallangan.   Uning   ishlash   prinsipi   (g’oyasi)   huddi   qo’ldagi   kartani   saralashga
o’xshab   ketadi.   Ya’ni   tartibsiz   turgan   kartalar   ichidan   birini   olasiz   va   uni   o’zi
turishi kerak bo’lgan joyga joylashtirib qo’yasiz. (Yuqoridagi rasmga qarang)
Insertion   sort   ham   shunday   ishlaydi.   Algoritm   oldin   array   boshidagi   ikkita
elementni   saralab   oladida   qolgan   elementlarni   shularga   qarab   o’z   o’rniga
joylashtirib   ketaveradi.   (Ulardan   oldiga,   ularning   orasiga   yoki   ulardan   keyinga).
Har bir element huddi shu tartibda o’z o’rnini topib boraveradi.
Algoritm   qanday   ishlashini   quyidagi   animatsiya   orqali   ham   ko’rishingiz
mumkin:
Algoritm qadamlari
Array boshidagi ikkita element solishtirib, saralab olinadi.
Qolgan elementlar bitta bitta qarab chiqiladi. (Tashqi iteratsiya)
Har bir element ichki takrorlanish orqali o’z joyiga joylashtirib boriladi. Bu yerda
array   chegaralaridan   o’tib   ketib   qolmaslikka   e’tibor   berish   kerak.   Tashqi
takrorlanish tugashi bilan array ham saralangan bo’ladi.
Algoritm murakkabligi
Insertion   sort   ham   Selection   va   Bubble   sort   kabi   O(n²)   vaqt   murakkabligi
bilan   ishlasa   ham,   lekin   ulardan   ko’ra   samaraliroq   algoritm   hisoblanadi.   Aynan,
array   elementlari   deyarli   saralangan   holatda   Insertion   sort   algoritmi   Merge   yoki
Quick   sort   algoritmidan   ham   ko’ra   tezroq   ishlaydi.   Bu   haqida   bo’lim   boshida
gapirib, ko’rsatib o’tgandik.
4.Merge sort
Merge   sort   —   (Birlashtirib   saralash)   algoritmi   asosiy   beshta   saralash
algoritmlari (Bubble sort, Quick sort va boshqalar) dan biri bo lib, chiziqli saralash	
ʻ
algoritmlaridan farqli ravishda „bo lib tashla va hukmronlik qil“ tipidagi algoritm	
ʻ
hisoblanadi.   Bu   turdagi   algoritmlar   katta   hajmdagi   masalalarni   nisbatan   kichik
bo lgan   va   oson   yechiladigan   qismlarga   ajratgan   holda   bajaradi.   Bunday	
ʻ
algoritmlar masalalarni yechishda vaqtdan yutish imkonini beradi.
 Merge Sort funksiyasiga massiv va uning boshlang ich (eng chapdagi element)	
ʻ
va oxirgi nuqtalari (eng o ngdagi element) beriladi.	
ʻ
 Massivning   o rtasi   hisoblanadi:   o rtasi   =   (chap   +   o ng)/2.   Bu   narsa   uni   teng	
ʻ ʻ ʻ
ikkiga bo lish uchun kerak bo ladi.	
ʻ ʻ
 Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi. 12Algoritm   ishlash   tezligi   O(n*log(n))   bo lib   tezligi   O(n2)   bo lgan   oddiyʻ ʻ
Bubble   sort,   Insertion   sort,   Selection   sortlardan   ancha   tez   ishlaydi.   Taqqoslash
asosida   ishlaydigan   algortmlarning   eng   tez   ishlash   holati   O(n*log(n))   bo lishi	
ʻ
isbotlangan
3-rasm Bo’lib tashla va hukumronlik qil .
5.Quicksort
Tez   saralash(quicksort)   algoritmi   -   Charlz   Xoar   tomonidan   yaratilgan   mashxur
saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni  eng uzog i	
ʻ
bilan   O(n2)   vaqtda   saralaydi.   Biroq   algoritm   bajarilish   tezligining   matematik
kutilmasi   O(n   log   n)   ga   teng   va   u   boshqa   shunday   tezlikda   bajariluvchi
algoritmlardan tezroq ishlaydi.
    Ishlash printsipi
1.  Massivda ixtiyoriy tayanch element tanlaymiz.
2.  Keyin   undan   kichik   yoki   teng   elementlarni   uning   chap   tomoniga,   katta
elementlarni o ng tomoniga o tkazamiz.	
ʻ ʻ
3.  1-2-chi   qadamlarni   tayanch   elementning   o ng   va   chap   tomonlaridagi	
ʻ
elementlar uchun qo llaymiz.	
ʻ
Algorimning   2-qadami   turlicha   bo lib   uning   bir   nechta   realizatsiyalari   mavjud.	
ʻ
Ayni shu 2-qadamda elementlarni  joylashtirish algoritmi tufayli  algoritm saralash
algoritmlari ichida eng tez ishlaydiganlaridan biridir.
   
#include <iostream>
using namespace std; 13void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
6.  Heapsort
Heapsort – binary heap ma’lumotlar tuzilmasi asosidagi tartiblash algoritmi.
Biz heap har doim ma’lum bir tartibga rioya qilishini bilganimiz uchun, uning bu
hususiyatidan tartiblashda foydalanishimiz – arrayning eng katta qiymatini olib uni
array’ning ohiriga qo’yib borish orqali array’ni tartiblashimiz mumkin.
Heapsortning ishlash tartibi
1.  Heapify. Tartiblanmagan array’dan max heap yasab olamiz. Binary heap’da
hisoblashni   osonlashtirish   uchun   array[0]   ni   bo’sh   qoldirgan   bo’lsak,   bu   safar
array[0]   ishtirok   etadi.   Sababi   hozirgi   holatda   bizda   array   tayyor   beriladi   va
qo’shimcha   heapni   qo’shimcha   o’zgaruvchiga   yig’masdan   array’ning   o’zida
yasaymiz (in-place).
2.  Swap.   Rootdagi   maksimum   qiymatli   elementni   ohirgi   element   bilan
almashtiramiz va uni heap’dan chiqaramiz.
3.  Reheapify. Ohirgi element root bo’lgach, u albatta o’z joyini topishi kerak.
4. Heap tartibini to’g’rilaymiz.
5.Repeat.   Ikkinchi   va   uchinchi   qadamlarni   heapda   bitta   element   qolguncha
davom ettiramiz.
Bizdagi max heap
[50, 47, 30, 33, 9, 13, 24, 20, 12, 5]
arrayni tartiblashni boshlaymiz.
5- rasm Birinchi va oxirgi elementini almashtirish. 14Arrayning birinchi va ohirgi elementlari – 50 va 5 ning o’rnini almashtiramiz va 50
ni heapdan chiqaramiz. Keyin 5 ni joyiga qo’yish uchun reheapify – qaytadan heap
tartibini to’g’rilaymiz.
5   ikki   childi   –   47   va   30   dan   kichkina.   biz   uni   katta   child   bilan   o’rnini
almashtiramiz.
                                   6-rasm.   
5 endi o’zi childlari 33 va 9 dan kichkina. Katta childi bilan o’rnini almashtiramiz.
                                             7-rasm.
5 o’z childi 20 va 12 dan kichkina. Katta childi – 20 bilan o’rnini almashtiramiz. 158- rasm.
Kichkina element  bo’lgan 5 yana heapning pastiga tushdi, uning childi  yo’q yoki
childlari bo’lganda ham ular 5 dan kichkina bo’lardi. Reheapify yakunlandi.
Yuqoridagi qadamlarni yana qaytaramiz
                                            9-rasm.
7.Radixsort
Radix   sort   -   bu   tartiblash   algoritmi   bo'lib,   elementlarni   raqamlari   yoki
belgilariga   qarab   tartiblash   orqali   ishlaydi.   Bu   qiyosiy   bo'lmagan   tartiblash
algoritmi  bo'lib,  elementlarni  to'g'ridan-to'g'ri   taqqoslash   o'rniga,  ularning  alohida
raqamlari yoki belgilarini qayta ishlash orqali tartiblaydi.
Radix   tartiblashning   asosiy   g'oyasi   elementlarni   eng   kichik   ahamiyatli
raqami bo'yicha, so'ngra ikkinchi eng muhim raqami bo'yicha va barcha raqamlar
qayta ishlanmaguncha guruhlashdan iborat. Saralash jarayoni har bir raqam uchun
takrorlanadi   va   jarayon   oxirida   elementlar   o'sish   yoki   kamayish   tartibida
tartiblanadi.
Radix tartiblashning ikki turi mavjud: LSD (Eng muhim raqam) radix sort va
MSD   (Eng   muhim   raqam)   radix   sort.   LSD   radix   tartiblash   raqamlarni   o'ngdan 16chapga   ishlov   beradi,   MSD   radix   tartiblash   esa   raqamlarni   chapdan   o'ngga   qayta
ishlaydi.
Radix   sortning   vaqt   murakkabligi   O(nk),   bu   yerda   n   saralanadigan
elementlar   soni   va   k   maksimal   elementdagi   raqamlar   soni.   Radix   sort,   agar   k
raqamlar soni n elementlar soniga nisbatan kichik bo'lsa, samarali bo'ladi.
Umuman olganda, radix sort butun sonlar, satrlar va raqamlar yoki belgilar
ketma-ketligi   sifatida   ko'rsatilishi   mumkin   bo'lgan   boshqa   ma'lumotlar   turlarini
saralash uchun foydali algoritmdir.
Radix   tartiblash   turli   xil   ma'lumotlar   tuzilmalari,   jumladan,   massivlar,
navbatlar   va   bog'langan   ro'yxatlar   yordamida   amalga   oshirilishi   mumkin.   Radix
sortning   eng   keng   tarqalgan   qo'llanilishi   har   bir   raqam   uchun   chelakni   tartiblash
algoritmidan foydalanadi, bu erda har bir element o'z raqam qiymatiga asoslangan
chelakka   joylashtiriladi.   Barcha   elementlar   tegishli   chelaklarga   joylashtirilgandan
so'ng, elementlar chelak indekslari tartibida birlashtiriladi.
Radix   sortning   ishlashini   yaxshilashi   mumkin   bo'lgan   ba'zi   o'zgarishlar
mavjud,   masalan,   gibrid   radix   sort,   bu   radix   saralash   va   tezkor   saralash   yoki
birlashtirish   kabi   boshqa   tartiblash   algoritmidan   foydalanadi.   Bu   ma'lumotlar
kichik   sonli   raqamlar   bilan   ko'p   sonli   elementlarni   o'z   ichiga   olganida   foydali
bo'lishi mumkin.
Radix   tartiblashning   bir   cheklovi   shundaki,   u   chelaklarni   saqlash   uchun
qo'shimcha   xotira   talab   qiladi,   bu   katta   ma'lumotlar   to'plamlarini   saralashda
tashvish tug'dirishi mumkin. Bundan tashqari, radix sort barqaror tur emas, ya'ni u
asl ketma-ketlikda teng elementlarning tartibini saqlamaydi.
Cheklovlarga qaramay, radix sort  hali ham  ma'lum  ilovalar  uchun mashhur
algoritm bo'lib qolmoqda, masalan, butun sonlar yoki satrlarning katta ma'lumotlar
to'plamini   saralash.   Bu,   ayniqsa,   qiymatlar   diapazoni   oldindan   ma'lum   bo'lgan
holatlarda, masalan, IP manzillari yoki telefon raqamlarini saralashda foydalidir.
Radix   sort   ham   parallellashtiriladi,   ya'ni   u   bir   nechta   protsessorlar   yoki
iplardan foydalanish uchun amalga oshirilishi mumkin. Bu zamonaviy ko'p yadroli
protsessorlarda uning ish faoliyatini sezilarli darajada yaxshilashi mumkin.
Radix   sortning   yana   bir   afzalligi   shundaki,   uni   ikkilik,   sakkizlik   yoki   o nʻ
oltilik kabi turli radiks asoslari bilan ishlashga oson moslash mumkin. Bu uni turli
xil ilovalarda ishlatilishi mumkin bo'lgan moslashuvchan algoritmga aylantiradi.
Umuman   olganda,   radix   sort   eng   ko'p   qirrali   tartiblash   algoritmi   bo'lmasa-
da,   u   hali   ham   katta   ma'lumotlar   to'plamlarini   tez   va   samarali   saralash   uchun
ishlatilishi mumkin bo'lgan kuchli vositadir, ayniqsa qiymatlar diapazoni oldindan
ma'lum bo'lsa.
Radix   sortining   yana   bir   o'zgarishi   MSD   radix   sort   deb   ataladi,   u
elementlarni   eng   muhim   soniga   qarab   rekursiv   bo'lish   orqali   ishlaydi.   Ushbu
algoritm   odatda   satrlarni   yoki   o'zgaruvchan   uzunlikdagi   belgilar   ketma-ketligiga
ega bo'lgan boshqa ma'lumotlar turlarini saralash uchun ishlatiladi.
MSD   radix   tartiblashi   elementlarni   birinchi   belgi   asosida   bo lishdan	
ʻ
boshlanadi,   so ngra   har   bir   bo lim   ichidagi   elementlarni   ikkinchi   belgiga   qarab	
ʻ ʻ
rekursiv   ravishda   bo linadi   va   hokazo,   barcha   belgilar   qayta   ishlanmaguncha	
ʻ
davom   etadi.   Ushbu   algoritm   umumiy   prefikslar   asosida   samarali   qismlarga 17ajratish   imkonini   beruvchi   trie   ma'lumotlar   strukturasi   yordamida   amalga
oshirilishi mumkin.
Radix   sortning   diqqatga   sazovor   qo'llanilishi   matnni   samarali   qidirish   va
indekslash   uchun   ishlatiladigan   ma'lumotlar   tuzilmalari   bo'lgan   qo'shimchalar
massivlarini   qurishdir.   Suffiks   massivini   qurish   berilgan   qatorning   barcha
qo'shimchalarini   saralashni   o'z   ichiga   oladi,   bu   radix   sort   yordamida   amalga
oshirilishi mumkin.
Bundan   tashqari,   radix   sort   ma'lumotlarni   o'xshash   qiymatlarni   birga
guruhlaydigan tarzda siqish orqali ma'lumotlarni siqish uchun ishlatilishi mumkin.
Bu   ma'lumotlardagi   har   bir   qiymatning   paydo   bo'lish   chastotasiga   asoslangan
Huffman kodlash kabi texnikalar yordamida amalga oshirilishi mumkin.
Umuman olganda, radix sort ko'p qirrali algoritm bo'lib, u kompyuter fanida
ma'lumotlarni   saralashdan   tashqari   ko'plab   muhim   ilovalarga   ega.   Uning
samaradorligi   va   moslashuvchanligidan   foydalanib,   keng   ko'lamli   muammolar
uchun yanada samarali algoritmlarni ishlab chiqish mumkin.
Radix   turining   qiziqarli   qo'llanilishi   kriptografiya   sohasida.   Radix   sort
kriptografik   algoritmlarda   qurilish   bloki   sifatida   ishlatilishi   mumkin,   masalan,
tartiblash   asosidagi   shifrlash   sxemalari,   bu  erda  ochiq   matn   radix   sort   yordamida
tartiblanadi va keyin shifrlangan matnga aylantiriladi.
Radix   sortning   yana   bir   muhim   qo'llanilishi   ma'lumotlarni   yig'ish   va   tahlil
qilish   sohasida   bo'lib,   u   ma'lumotlarni   klasterlash   va   tasniflash   uchun   ishlatilishi
mumkin.   Muayyan   xususiyatlar   yoki   atributlar   asosida   ma'lumotlarni   saralash
orqali ma'lumotlar ichidagi naqsh yoki guruhlarni aniqlash mumkin.
Radix   saralash   parallel   hisoblash   muhitlarida   ham   qo'llanilishi   mumkin,   bu
erda tartiblash jarayoni turli protsessorlar yoki tugunlarda bir vaqtning o'zida qayta
ishlanishi  mumkin bo'lgan  kichikroq kichik muammolarga bo'linishi  mumkin. Bu
katta   ma'lumotlar   to'plamlarini   saralash   uchun   zarur   bo'lgan   vaqtni   sezilarli
darajada qisqartirishi mumkin.
So'nggi   yillarda   maydonda   dasturlashtiriladigan   eshik   massivlari   (FPGA)
yoki grafik ishlov berish bloklari (GPU) kabi  usullardan foydalangan holda radix
turidagi   apparat   dasturlarini   ishlab   chiqishga   qiziqish   ortib   bormoqda.   Ushbu
ilovalar juda yuqori saralash tezligiga erishishi mumkin, bu esa radix sortni yuqori
unumdorlikdagi hisoblash ilovalari uchun qimmatli vositaga aylantiradi.
Umuman   olganda,   radix   sortning   ko'p   qirraliligi   va   samaradorligi   uni
ma'lumotlarni   siqish   va   tahlil   qilishdan   kriptografiya   va   yuqori   unumli
hisoblashgacha bo'lgan keng ko'lamli ilovalar uchun qimmatli vositaga aylantiradi.
Uning   katta   ma'lumotlar   to'plamlari   bilan   ishlash   va   turli   xil   radix   bazalari   va
ma'lumotlar   turlariga   moslashish   qobiliyati   uni   shaxsiy   asboblar   qutisida   bo'lishi
mumkin bo'lgan qimmatli algoritmga aylantiradi.
Shuni ta'kidlash kerakki, radix sort juda samarali tartiblash algoritmi bo'lishi
mumkin   bo'lsa-da,   u   eng   yaxshi   tanlov   bo'lmasligi   mumkin   bo'lgan   ba'zi   holatlar
mavjud.   Misol   uchun,   agar   ma'lumotlar   juda   kichik   qiymatlar   diapazoniga   ega
bo'lsa,   qo'shish   yoki   saralash   kabi   boshqa   tartiblash   algoritmlari   tezroq   bo'lishi
mumkin. 18Bundan   tashqari,   radix   sort   odatda   grafiklar   yoki   daraxtlar   kabi   elementlar
o'rtasida murakkab munosabatlarga ega bo'lgan ma'lumotlarni saralash uchun mos
kelmaydi. Bunday hollarda chuqurlikdan birinchi qidirish yoki kenglikdan birinchi
qidirish kabi boshqa algoritmlar mos kelishi mumkin.
Radix   sortning   yana   bir   cheklovi   shundaki,   uni   amalga   oshirish   yoki
tushunish Quicksort  yoki Mergesort  kabi  boshqa tartiblash algoritmlari  kabi  oson
bo'lmasligi   mumkin.   Bu   ma'lum   ilovalar   uchun   foydalanish   yoki   o'zgartirishni
qiyinlashtirishi mumkin.
Ushbu   cheklovlarga   qaramay,   radix   sort   turli   xil   ilovalarda   ishlatilishi
mumkin   bo'lgan   kuchli   va   ko'p   qirrali   saralash   algoritmi   bo'lib   qolmoqda.   Uning
katta ma'lumotlar to'plamlarini boshqarish va turli xil radix bazalari va ma'lumotlar
turlariga   moslashish   qobiliyati   uni   kompyuter   fanlari   va   ma'lumotlar   qazib
olishdan   kriptografiya   va   yuqori   unumli   hisoblashgacha   bo'lgan   ko'plab   turli
sohalar uchun qimmatli vositaga aylantiradi.
Radix   saralashdan   foydalanishda   muhim   e'tiborga   olish   tartiblash   jarayoni
uchun zarur bo'lgan xotira miqdoridir. Radix sort yordamida n ta elementdan iborat
ma lumotlar   to plamini   saralash   uchun   algoritm   har   bir   raqam   uchun   n   tagachaʼ ʻ
chelak yaratishi kerak, bu esa katta hajmdagi xotirani talab qilishi mumkin.
Biroq,   radix   sortining   xotira   talablarini   kamaytirish   uchun   ishlatilishi
mumkin   bo'lgan   bir   nechta   texnikalar   mavjud.   Yondashuvlardan   biri   -   o'z   joyida
radix tartiblashdan foydalanish, bunda saralash qo'shimcha chelaklar yaratmasdan
to'g'ridan-to'g'ri   asl   ma'lumotlar   to'plamida   amalga   oshiriladi.   Buni   elementlarni
raqamlar   qiymatlari   asosida   guruhlarga   bo'lish   va   keyin   har   bir   guruhni   rekursiv
tartiblash orqali amalga oshirish mumkin.
Yana   bir   usul   -   radix   saralash   samaradorligini   mergesort   kabi   boshqa
saralash   algoritmlarining   past   xotira   talablari   bilan   birlashtirgan   gibrid   radix
saralashdan foydalanish. Buni ma'lumotlarning kichik kichik to'plamlarini saralash
uchun radix sort yordamida va keyin saralangan kichik to'plamlarni birlashtirishga
o'xshash yondashuv yordamida birlashtirish orqali amalga oshirish mumkin.
Radix tartiblashdan foydalanishda yana bir muhim e'tibor algoritmning vaqt
murakkabligi hisoblanadi. Eng yomon holatda, radix sort vaqt murakkabligi O(kn),
bu yerda  k -  ma'lumotlar   to'plamidagi  eng  katta  elementdagi  raqamlar  yoki   bitlar
soni.   Bu   algoritmning   ishlashiga   saralanadigan   ma'lumotlarning   hajmi   va
diapazoni ta'sir qilishi mumkinligini anglatadi.
Biroq,   amalda,   radix   saralash   ko'pincha   tez   saralash   yoki   birlashtirish   kabi
boshqa   tartiblash   algoritmlariga   qaraganda   tezroq   bo'lishi   mumkin,   ayniqsa   katta
ma'lumotlar   to'plamlari   yoki   ko'p   takrorlanadigan   elementlarga   ega   ma'lumotlar
to'plamlari   bilan   ishlashda.   Buning   sababi,   radix   sort   boshqa   algoritmlar   kabi
elementlarni   juft-juft   solishtirishdan   ko'ra,   saralanayotgan   ma'lumotlarning
tuzilishidan foydalanadi.
Shuni   ham   ta'kidlash   joizki,   radix   tartiblashning   vaqt   murakkabligi
chelaklarni   saralash   yoki   pastki   dasturlar   sifatida   saralashni   hisoblash   kabi
usullardan   foydalanish   orqali   kamaytirilishi   mumkin.   Ushbu   usullardan   har   bir
chelakdagi   elementlarni   raqam   qiymatlari   asosida   bo'lingandan   so'ng   saralash 19uchun   foydalanish   mumkin,   bu   umumiy   tartiblash   jarayoni   uchun   zarur   bo'lgan
vaqtni qisqartiradi.
Xulosa   qilib   aytadigan   bo'lsak,   radix   sort   -   bu   keng   doiradagi   ilovalarda
qo'llanilishi mumkin bo'lgan kuchli va ko'p qirrali tartiblash algoritmidir. U boshqa
algoritmlar   kabi   elementlarni   juft-juft   solishtirish   o‘rniga   saralanayotgan
ma’lumotlar   strukturasidan   foydalanadi,   bu   esa   uni   katta   ma’lumotlar   to‘plamlari
yoki ko‘p takrorlanuvchi elementlarga ega ma’lumotlar to‘plamlari uchun ayniqsa
samarali qiladi.
Biroq,   radix   sort   foydalanishda   e'tiborga   olinishi   kerak   bo'lgan   ba'zi
cheklovlar   va   fikrlarga   ega.   Bularga   algoritmning   xotira   talablari,   saralash
jarayonining   vaqt   murakkabligi,   algoritm   barqarorligi   va   radix   bazasi   yoki   radix
qiymatini tanlash kiradi.
Radix   saralashning   to'g'ri   o'zgarishini   tanlash,   samarali   saralash   usullarini
qo'llash va ushbu fikrlarni hisobga olgan holda, keng ko'lamli ilovalarda radix sort
bilan yuqori samarali saralashga erishish mumkin.                                                   20    XULOSA
Bu   kurs   ishida   siz   biror   bir   yordamni   tanlashi,   unda   qo'llaniladigan
algoritmlar   va   tuzilmalarni   izohlashi,   ularga   misollar   keltirishni   o'z   ichiga   oladi.
Ma'lumotlarni saralash usullari to'g'risida teorik bilim va amaliy mashg'ulotlar ham
kiritish yaxshi bo'ladi. Keltirilgan ilovalar ma lumotlarni saralashni tezlashtiradi vaʼ
ish   samaradorligini   ortishiga   sabab   bo ladi.   Biz   bu   mavzularni   o rganishimizdan	
ʻ ʻ
maqsad   ma lumotlarni   tez   va   oson   saralash   yo llarini   ko rib   chiqish   va   uni	
ʼ ʻ ʻ
o rganish. Insoniyatga qulaylik yaratish .Algoritmlarning qulayliklarini tahlil qilish	
ʻ
va   o’zimizga   kerakligini   tanlab   olish   saralash   usullarni   bir   biri   bilan   solishtirish
edi. 21ADABIYOTLAR RO’YXATI
1.  Eshtemirov.S     Nazarov . F   “Algoritm   va   dasturlash   asoslari” :   Qo’llanma.
Samarqand -2019.
2.  Aripov M.M  Otaxonov N.A “ Dasturlash asoslari”:Qo’llanma.   Toshkent-2015.
3.  1. Клейнберг Дж., Тардос Е. К48 Алгоритмы: разработка и  
применение. Классика Computers Science / Пер. с англ. Е.  
4.  Матвеева. — СПб.: Питер, 2016. — 800 с.: ил. — (Серия  
«Классика computer science»).   
5.  Структуры данных и алгоритмы.: Пер. с англ.: Уч. Пос. – М.  
Издательский дом «Вильямс», 2000. – 384 с.: ил. – Парал.  .  
6.   Пышкин Е.В. Структуры данных и алгоритмы: реализация  
на C/C++. - СПб.: ФТК СПБГПУ, 2009.- 200 с., ил. 
7.   Овсянников, А. В. Алгоритмы и структуры данных : учебнометодический
комплекс для специальности 1-31 03 07     
8.   Никлаус Вирт, Алгоритмы и структуры данных. Новая  
  версия для Оберона + CD / Пер. с англ. Ткачев Ф. В. – М.:  ДМК Пресс, 2010.
– 272 с.: ил.
9.   Manba: @AlgorithmUz telegram kanali.
10.  Manba: Online saytlar kanallar.
1 1 .  http://www.stroustrup.com/4th.html 
1 2 .  http://www.cplusplus.com/ 
13 . http://acm.tuit.uz/- дастурий ечим  тўғрилигини автоматик тестловчи
тизим. 
1 4.    http://acm.tuit.uz/forum/ 
1 5.    http://acm.timus.ru/ – дастурларни тестловчи тизим. 
1 6.   http://codeforces.com/   -   дастурий   ечим   тўғрилигини   автоматик
тестловчи  тизим 22ILOVALAR
ILOVA 1.  Quicksort usuli kodi
[64, 25, 12, 22, 11 ] ushbu arrayni Quicksort yordamida sortlang  .
#include <iostream>
using namespace std;
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
void printArray(int arr[], int size) {
    for (int 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]); 23    cout << "1- array: ";
    printArray(arr, n);
    quickSort(arr, 0, n - 1);
    cout << "Sortlangan array: ";
    printArray(arr, n);
    return 0;
}
ILOVA 2.  Megesort usuli kodi
[64, 25, 12, 22, 11 ] ushbu arrayni Megasort yordamida sortlang.
#include <iostream>
using namespace std;
void merge(int arr[], int left, int middle, int right) {
    int i, j, k;
    int n1 = middle - left + 1;
    int n2 = right - middle;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[middle + 1 + j];
     i = 0;   
     j = 0;
     k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }  
 k++;
    }
    while (i < n1) { 24        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}
void printArray(int arr[], int size) {
    for (int 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]);
    cout << "1- array: ";
    printArray(arr, n);
    mergeSort(arr, 0, n - 1);
    cout << "Sortlangan array: ";
    printArray(arr, n);
    return 0;
}

1Ma’lumotlarni saralash usullari MUNDARIJA KIRISH ............................................................................................................ 2 I Bob. Saralash usulining nazariy asoslari. ................................................ 3 1.Tuzilma elementlarini saralash ............................................................... 3 1.qat'iy (to'g'ridan-to'g'ri) usullar; .................................................................... 3 2.Saralash tushunchasi va uning vazifasi ................................................. 4 3. Ma lumotlarni tartiblash usullariʼ ........................................................... 5 4. Guruhlash turlari .................................................................................... 6 1. Maqsad va vazifalarga qarab ....................................................................... 6 2. Guruhlash belgilari soniga qarab ................................................................. 6 3. Manbaiga qarab ........................................................................................... 6 4. Tipologik guruhlash .................................................................................... 6 5. Analitik guruhlash ....................................................................................... 7 6. Tuzilmaviy guruhlash .................................................................................. 7 7. Oddiy guruhlash .......................................................................................... 7 8. Murakkab guruhlash .................................................................................... 7 9. Birlamchi guruhlash .................................................................................... 7 10. Ikkilamchi guruhlash ................................................................................. 7 1. tipologik; .................................................................................................... 7 2. analitik; ....................................................................................................... 7 2.Selection sort ........................................................................................ 10 3.Insertion sort ......................................................................................... 10 4.Merge sort ............................................................................................. 11 5.Quicksort .............................................................................................. 12 6. Heapsort ............................................................................................... 13 7.Radixsort .............................................................................................. 15 XULOSA ...................................................................................................... 20 ADABIYOTLAR RO’YXATI ...................................................................... 21 ILOVALAR ................................................................................................... 22 ILOVA 1. Quicksort usuli kodi ............................................................... 22 ILOVA 2. Megesort usuli kodi ................................................................ 23 i = 0; .............................................................................................................. 23 j = 0; .............................................................................................................. 23 k = left; ......................................................................................................... 23

2 KIRISH Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar qanday saralash usullari va algoritmlari mavjudligini va ularning samaradorliklarini baholashni o'rganishlari kerak. Shu asosda saralash usullarini qiyosiy tahlil qilishlari va ularga oid dasturlar tuzishni o'zlashtirishlari kerak. Qo'yilgan masala: Talabalar topshiriq variantiga mos saralash usuli yordamida masalani yechish dasturini yaratish ko'nikmasiga ega bo'lishlari kerak. Ish tartibi: 1. Tajriba ishi nazariy ma'lumotlarini o'rganish; 2. Berilgan topshiriqniтп algoritmini ishlab chiqish 3. C++ dasturlash muhitida dasturni yaratish; 4. Natijalarni tekshirish; 5. Hisobotni tayyorlash va topshirish

3I Bob. Saralash usulining nazariy asoslari. 1.Tuzilma elementlarini saralash Ma'lumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda ma'lumotlarni saralash amalga oshiriladi. Demak, saralash – bu ma'lumotlarni kalitlari bo'yicha doimiy ko'rinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik ma'lumotlarni massivda kalitlari bo'yicha o'sishi tartibida berilishi tushuniladi. Ma'lumotlarga qayta ishlov berilayotganda ma'lumotning informatsion maydonini hamda uning mashinada joylashishini (adresini) bilish zarur. Saralashning ikkita turi mavjud: ichki va tashqi: 1.ichki saralash bu operativ xotiradagi saralash; 2.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 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: 1. saralashga ketgan vaqt; 2. saralash uchun talab qilingan operativ xotira; 3. 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: dan gacha; – ideal holatda. Saralashning quyidagicha usullari bor: 1.qat'iy (to'g'ridan-to'g'ri) usullar; 2.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.

43. Murakkablashtirilgan usullarda uncha ko'p amallarni bajarish 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). 2.Saralash tushunchasi va uning vazifasi Saralash – bu berilgan to‘plam elementlarini biror bir tartibda (o‘sish yoki kamayish) joylashtirish jarayonidir. Saralash (inglizcha sorting - tasniflash, tartiblash) - tanlangan mezonga qarab biror narsani ketma-ket joylashtirish yoki guruhlarga bo'lish. Saralash– bu massiv elementlarini tartiblash (o’sish, kamayish, oxirgi raqami, bo’luvchilari bo’yicha, …) Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Ma'lumotlarni saralash - uni qandaydir atributga ko'ra tartibga solishdir. Saralashdagi qiyinchiliklar quyidagi hollarda mavjud bo’ladi:  ma'lumotlar massivlari katta bo’lganda - minglab, o'nlab va yuz minglab elementlar;  ma'lumotlarga murojaat qilish qiyin bo'lishi mumkin (masalan, ular ma’lumotlar oqimi bo’lganda);  kompyuterning imkoniyatlari yetarli emas va dasturlash tiliga kiritilganidan ko'ra tejamkorroq algoritmlar kerak. Bunday hollarda saralashning ixtisoslashtirilgan algoritmlarini tanlash kerak, zarurat bo’lsa ularni masalaga qarab optimallashtirish mumkin. Saralashdan maqsad - tartiblangan to‘plamda kerakli elementni topishni osonlashtirishdan iborat. dasturlarni translyasiya qilishda; ma’lumotlar majmuasini tashqi xotirada tashkil qilishda; kutubxonalar, kataloglar, ma’lumotlar bazasini yaratishda va boshqalar. 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

5algoritm 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 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. 3. Ma lumotlarni tartiblash usullariʼ  Alfabetik tartib: Odatda, ma'lumotlar alfabetik tartibda joylashgan holda tartiblanadi. Misol uchun, ismilar ro'yxatini A dan Z gacha joylashgan tartibda joylashtirish mumkin.  Sanash tartibi: Bu tartiblash usuli ma'lumotlarni sonlarga asoslangan tartiblashdir. Misol uchun, telefon raqamlarini yoki o'yinlardagi darajalarni tartiblashda sanash tartibi qo'llaniladi.  Kronologik tartib: Ma'lumotlarni vaqtni yoki yilni asoslashga asoslangan tartiblash usuli. Misol uchun, tarixiy voqealar ro'yxati yoki bir yil davomida sodir bo'lgan tadbirlar ro'yxati kronologik tartibda joylashtiriladi.