Ma’lumotlarni saralash usullari
![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)
![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)
![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.