Ma’lumotlarni saralash usullari
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_1.png)
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_2.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_3.png)
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_4.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_5.png)
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_6.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_7.png)
![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 .](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_8.png)
![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
ʼ ʼ](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_9.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_10.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_11.png)
![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;](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_12.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_13.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_14.png)
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_15.png)
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_16.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_17.png)
![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](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_18.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_19.png)
![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.](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_20.png)
![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/ - дастурий ечим тўғрилигини автоматик
тестловчи тизим](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_21.png)
![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]);](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_22.png)
![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) {](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_23.png)
![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;
}](/data/documents/08c0e280-8e7e-42ab-be2e-1278880a1bc4/page_24.png)
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.