Ko’p oqimli birlashtirish saralash
![I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi.
1.1. Saralash tarixi
Uch kishini bir necha yillardan buyon uzoq kosmosda olis sayyoralar tomon
olib ketayotgan kosmik kema g‘alati oltinrang bulut orasidan uchib o‘tdi. Kemada
tug‘ilgan va bir yosh bo‘lgan Век ismli bola hali yurishni o‘rganmagani uchun
g‘ildirakli aravachasida katta doira shaklidagi xonasida bir o‘zi aylanib yurishni
yoqtirardi. U aravachasini g‘ildiratib borib o‘yinchoqlarini egilib olar, o‘ynab yana
otib yuborar edi. Век oltinrang bulut ta‘sirida o‘zida bir necha xil o‘zgarishlami
sezdi. Birinchi o‘zgarish zehni bilan bog‘liq bo‘lib, u endi bola bo‘lsa ham
arifmetik amaUarni juda tez bajarar, har xil narsalarni turli ko‘rinishdagi miqdorini
bir qarashda juda tez aniqlab, taqqoslay olardi. Ikkinchisi, u tajanglashganligi va
endi bolalar o‘yinchoqlarini o‘ynagisi kelmay qolganligi edi. Xonada bir o‘zi
zerikib qolganligidan chinqirib yig‘lay boshladi. 0 ‘g‘lini ovutishga kelgan ota-ona
bolani qunt bilan ota-onasining suhbatini tinglayotganiga e’tibor berishdi. 0
‘g'lidagi o‘zgarish]arni sezgach, zehni o‘tkir o‘g‘lini ovutish uchun ota-onasi
xonani boshqacha jihozlab, faqat bir qo‘li bor hamda g'ildirakda yiiradigan sodda
dasturli Saralovchi I nomli robot yasab berishdi. Keyin robotni boshqarishga
mo‘Ijallangan dastur tuzishga yo‘naltirilgan turli boshqotirmali masalalami ayta
boshlashdi. Biz endi Век bilan birga shu masalalarni ko’rib chiqamiz. Avval xona
haqida. Aytganimizdek, doira shakJidagi devorlari bo‘ylab bir xil balandlikda
tokchalar o'rnatildi. Har bir tokchaga tartib raqami berildi, xonani bir qismining
ko‘rinishi 8.1-rasmda ifodalangan.
Kerak boisa, tokchalarni bir nechtasini qoldirib, qolganlarini yopib q o ‘yish
mumkin edi. Har bir tokchani qulaylik uchun quyidagicha nom bilan belgilab
olamiz: tokcha(I), tokcha(2), ..., tokcha(7), tokcha(21), ..., tokcha(1963), ... va shu
asosida ixtiyoriy A tokchadagi buyumni tokcha(A) orqali belgilay olamiz. Ya’ni,
tokcha(A) deganda Век va Saralovchi I tokchani emas, shu tartib raqamli tokcha
buyumni tushunadi. Tokchalar sonining quyi chegarasi — INF, yuqori
chegarasi — SUP kabi belgilanadi. Yuqoridagi belgilashlarga ko‘ra INF=1, SUP
2](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_4.png)
![qandaydir qolipga solish juda ham muhim. Sababi, tartibsiz ma’lumotlar bilan
ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va
xatoliklarga moyil bo’ladi. Tartiblangan ma'lumotlar hammaga yoqadi. Saralash
ma'lumotlarni kerakli ketma-ketlikda tartibga solish imkonini beradi, masalan,
o'sish yoki kamayish tartibida. Tasavvur qiling-a, siz yirik kompaniyada ishlaysiz
va siz xodimlarning ismlarini maoshiga qarab tartiblashingiz kerak. Buning uchun
saralash algoritmlari qo'llaniladi. Quyida saralash algoritmlarining asosiy turlarini
ko'rib chiqiladi. Avvalambor saralash algoritmi nima ekanligini aniqlab olaylik.
Saralash algoritmlari taqqoslash operatorlari yordamida ro'yxatlar va massivlarda
berilgan ma'lumotlarni tartiblab beradi. Bu operatorlar massiv elementlariga
qo’llaniladi va ularning ma’lumotlar strukturasidagi tartibini belgilaydi. Misol
uchun, quyidagi belgilar (1-rasm) ASCII kodi bo'yicha o'sish tartibida saralangan.
Saralash jarayonida elementlar bir-biri bilan taqqoslanadi. ASCII jadvalidagi
belgining qiymati qanchalik katta bo'lsa, u ro'yxat boshidan shunchalik uzoqroqda
joylashgan bo'ladi. [1] Dasturlashda turli xil saralash algoritmlar mavjud. Masalani
turi mazmuniga qarab turib saralash algoritmlarning biri qo’llaniladi. Keling eng
ko’p qo’llaniladigan saralash algoritmlarini ko'rib chiqamiz.
1.3. Birlashtirish saralash
Birlashtirish saralash – massivni kichikroq kichik massivlarga bo‘lish, har
bir kichik massivni saralash va so‘ng saralangan pastki massivlarni birlashtirib,
yakuniy tartiblangan massivni hosil qilish orqali ishlaydigan tartiblash algoritmi.
Oddiy qilib aytganda, birlashtirish tartiblash jarayoni massivni ikki yarmiga
bo'lish, har bir yarmini tartiblash va keyin tartiblangan yarmini yana
birlashtirishdir. Bu jarayon butun massiv saralanmaguncha takrorlanadi.
Sizni qiziqtirgan narsa bu algoritmning o'ziga xosligi nimada. Bizda
allaqachon bir qator tartiblash algoritmlari bor, nega bizga bu algoritm
kerak? Birlashtirishning asosiy afzalliklaridan biri shundaki, u vaqt murakkabligi
O(n log n)ga ega, ya’ni u katta massivlarni nisbatan tez saralay oladi. Bu turg'un
tartibdir, ya'ni tartiblash jarayonida teng qiymatli elementlarning tartibi saqlanib
qoladi.
4](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_6.png)
![indeksidan boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan kichik
qismini ajratishdir.
“Bo lib tashlash”ʻ
Agar q qiymati p va r orasida bo lsa, biz A [p..r] massivni ikkita A [p..q] va
ʻ
A [q + 1, r] kichik massivlarga bo lishimiz mumkin.
ʻ
“Hukmronlik qilish”
Hukmronlik qilish bosqichida biz ikkala A [p..q] va A [q + 1, r] kichik
massivlarni saralashga harakat qilamiz. Agar hali ham boshlang ich darajaga yetib
ʻ
bormagan bo lsak, yana ikkala quyi qismni ajratib, ularni saralashga harakat
ʻ
qilamiz.
“Birlashtirish bosqichi”.
Birlashtirish bosqichi asosiy pog onaga yetib borganida va biz A [p..r]
ʻ
massivi uchun ikkita tartiblangan A [p..q] va A [q + 1, r] kichik massivlarni olsak,
natijalarni A [p..r] massiviga birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q
+ 1, r] massivlarning birlashmasidir
2.3. Merge Sort algoritmining ishlash prinsipi
Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda
saralovchi algoritm bo'lib, uning ishlash prinsipida to'liq bo'lib tashla va
hukmronlik qil g'oyasini uchratish mumkin. Demak, merge sort asosiy ikkita
qismdan iborat:
1. Berilgan arrayni rekursiv holda teng ikkita qismlarga bo'lib chiqish. Bu
qadam, qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo'lib qolguncha
davom etadi.
2.Hosil bo'lgan arraylarni qaytib birlashtirib chiqish va bir vaqtni o'zida hosil
bo'luvchi array saralangan bo'lishini ta'minlash.
Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga
e'tiboringizni qaratmoqchiman. Unda amallar tartibi ham ko'rsatib qo'yilgan
6](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_8.png)
![Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir. Birlashish
bosqichi - ikkita katta ro yxat (massiv) yaratish uchun ikkita tartiblangan ro yxatniʻ ʻ
(massivlarni) birlashtirish bo yicha oddiy muammoning yechimi.
ʻ
Ikkinchi massivda boshqa elementlar qolmaganligi va ikkala massiv ham
ishga tushirilganda saralanganligini bilganimiz uchun qolgan massivlarni
to g ridan-to g ri birinchi massivdan nusxalashimiz mumkin.
ʻ ʻ ʻ ʻ
#include using namespace std;
// Array[] ikkita ichki massivni birlashtiradi.
//Birinchi ichki massiv - Array[l..m]
// Ikkinchi ichki massiv Array[m+1..r]
void merge(int Array[], int l, int m, int r) {
int n1 = m - l + 1; int n2 = r - m;
// Vaqtinchalik massivlarni yaratish int L[n1], R[n2];
// Ma lumotlarni vaqtinchalik L[] va R[] massivlariga nusxalash
‟
for (int i = 0; i < n1; i++) L[i] = Array[l + i];
for (int j = 0; j < n2; j++) R[j] = Array[m + 1 + j];
// Vaqtinchalik massivlarni yana arr [l..r] ga birlashtirish.
// Birinchi ichki massivning boshlang ich ko rsatkichi
ʻ ʻ
int i = 0;
// Ikkinchi kichik massivning boshlang ich ko rsatkichi
ʻ ʻ
int j = 0;
// Birlashtirilgan ichki massivning dastlabki ko rsatkichi
ʻ
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
Array[k] = L[i];
10](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_12.png)
![i++;
}
else {
Array[k] = R[j];
j++;
}
k++;
}
// Agar mavjud bo lsa, R [] ning ʻ
//qolgan elementlarini nusxalash
while (j < n2) {
Array[k] = R[j];
j++;
k++;
}
}
// l chap indeks uchun,
//r esa tartiblangan ichki massivning o ng indeksidir
ʻ
void mergeSort(int Array[],int l,int r){
if(l>=r){
return;//rekursiv ravishda qaytadi
}
int m =l+ (r-l)/2;
mergeSort(Array,l,m);
mergeSort(Array,m+1,r);
merge(Array,l,m,r);
}
// Massivni chop etish funksiyasi
void printArrayay(int A[], int size)
{
11](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_13.png)
![for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
int main() {
int Array[] = { 12, 11, 13, 5, 6, 7 };
int Array_size = sizeof(Array) / sizeof(Array[0]);
cout << "Berilgan massiv \n";
printArrayay(Array, Array_size);
mergeSort(Array, 0, Array_size - 1);
cout << "\n Tartiblangan massiv \n";
printArrayay(Array, Array_size);
return 0;
}
12](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_14.png)
![#include <iostream>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays L[] and R[]
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temp arrays back into arr[l..r]
// Initial index of first subarray
int i = 0;
// Initial index of second subarray
int j = 0;
// Initial index of merged subarray
13](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_15.png)
![int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
14](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_16.png)
![}
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
15](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_17.png)
![ILOVALAR
ILOVA 1. Modul N1 boshlang’ich kod.
#include using namespace std;
// Array[] ikkita ichki massivni birlashtiradi.
//Birinchi ichki massiv - Array[l..m]
// Ikkinchi ichki massiv Array[m+1..r]
void merge(int Array[], int l, int m, int r) {
int n1 = m - l + 1; int n2 = r - m;
// Vaqtinchalik massivlarni yaratish int L[n1], R[n2];
// Ma lumotlarni vaqtinchalik L[] va R[] massivlariga nusxalash ‟
for (int i = 0; i < n1; i++) L[i] = Array[l + i];
for (int j = 0; j < n2; j++) R[j] = Array[m + 1 + j];
// Vaqtinchalik massivlarni yana arr [l..r] ga birlashtirish.
// Birinchi ichki massivning boshlang ich ko rsatkichi
ʻ ʻ
int i = 0;
// Ikkinchi kichik massivning boshlang ich ko rsatkichi
ʻ ʻ
int j = 0;
// Birlashtirilgan ichki massivning dastlabki ko rsatkichi
ʻ
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
Array[k] = L[i];
i++;
}
else {
Array[k] = R[j];
j++;
21](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_23.png)
![}
k++;
}
// Agar mavjud bo lsa, R [] ning ʻ
//qolgan elementlarini nusxalash
while (j < n2) {
Array[k] = R[j];
j++;
k++;
}
}
// l chap indeks uchun,
//r esa tartiblangan ichki massivning o ng indeksidir
ʻ
void mergeSort(int Array[],int l,int r){
if(l>=r){
return;//rekursiv ravishda qaytadi
}
int m =l+ (r-l)/2;
mergeSort(Array,l,m);
mergeSort(Array,m+1,r);
merge(Array,l,m,r);
}
// Massivni chop etish funksiyasi
void printArrayay(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
int main() {
int Array[] = { 12, 11, 13, 5, 6, 7 };
22](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_24.png)
![int Array_size = sizeof(Array) / sizeof(Array[0]);
cout << "Berilgan massiv \n";
printArrayay(Array, Array_size);
mergeSort(Array, 0, Array_size - 1);
cout << "\n Tartiblangan massiv \n";
printArrayay(Array, Array_size);
return 0;
}
23](/data/documents/73cc84e2-1766-4073-b1e8-c02e85208f8c/page_25.png)
Ko’p oqimli birlashtirish saralash
Ko’p oqimli birlashtirish saralash ................................................................... 1 I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi. ........................... 2 1.2. Saralash tushunchasi ................................................................................. 3 1.3.Birlashtirish saralash ish jarayoni: ............................................................ 5 ADABIYOTLAR RO’YXATI ...................................................................... 20 ILOVA 1. Modul N1 boshlang’ich kod. ....................................................... 21
KIRISH Saralash algoritmlari hozirgi kunda hayotimizda juda ko’p qo’llaniladi. Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktabda jismoniy tarbiya dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familiyalar ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalida alvabit tartibida saralanadi. Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham muhim. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi. Tartiblangan ma'lumotlar hammaga yoqadi. Saralash ma'lumotlarni kerakli ketma-ketlikda tartibga solish imkonini beradi, masalan, o'sish yoki kamayish tartibida. Tasavvur qiling-a, siz yirik kompaniyada ishlaysiz va siz xodimlarning ismlarini maoshiga qarab tartiblashingiz kerak. Buning uchun saralash algoritmlari qo'llaniladi. 1
I Bob. Ko’p oqimli birlashtirib saralashning nazariy qismi. 1.1. Saralash tarixi Uch kishini bir necha yillardan buyon uzoq kosmosda olis sayyoralar tomon olib ketayotgan kosmik kema g‘alati oltinrang bulut orasidan uchib o‘tdi. Kemada tug‘ilgan va bir yosh bo‘lgan Век ismli bola hali yurishni o‘rganmagani uchun g‘ildirakli aravachasida katta doira shaklidagi xonasida bir o‘zi aylanib yurishni yoqtirardi. U aravachasini g‘ildiratib borib o‘yinchoqlarini egilib olar, o‘ynab yana otib yuborar edi. Век oltinrang bulut ta‘sirida o‘zida bir necha xil o‘zgarishlami sezdi. Birinchi o‘zgarish zehni bilan bog‘liq bo‘lib, u endi bola bo‘lsa ham arifmetik amaUarni juda tez bajarar, har xil narsalarni turli ko‘rinishdagi miqdorini bir qarashda juda tez aniqlab, taqqoslay olardi. Ikkinchisi, u tajanglashganligi va endi bolalar o‘yinchoqlarini o‘ynagisi kelmay qolganligi edi. Xonada bir o‘zi zerikib qolganligidan chinqirib yig‘lay boshladi. 0 ‘g‘lini ovutishga kelgan ota-ona bolani qunt bilan ota-onasining suhbatini tinglayotganiga e’tibor berishdi. 0 ‘g'lidagi o‘zgarish]arni sezgach, zehni o‘tkir o‘g‘lini ovutish uchun ota-onasi xonani boshqacha jihozlab, faqat bir qo‘li bor hamda g'ildirakda yiiradigan sodda dasturli Saralovchi I nomli robot yasab berishdi. Keyin robotni boshqarishga mo‘Ijallangan dastur tuzishga yo‘naltirilgan turli boshqotirmali masalalami ayta boshlashdi. Biz endi Век bilan birga shu masalalarni ko’rib chiqamiz. Avval xona haqida. Aytganimizdek, doira shakJidagi devorlari bo‘ylab bir xil balandlikda tokchalar o'rnatildi. Har bir tokchaga tartib raqami berildi, xonani bir qismining ko‘rinishi 8.1-rasmda ifodalangan. Kerak boisa, tokchalarni bir nechtasini qoldirib, qolganlarini yopib q o ‘yish mumkin edi. Har bir tokchani qulaylik uchun quyidagicha nom bilan belgilab olamiz: tokcha(I), tokcha(2), ..., tokcha(7), tokcha(21), ..., tokcha(1963), ... va shu asosida ixtiyoriy A tokchadagi buyumni tokcha(A) orqali belgilay olamiz. Ya’ni, tokcha(A) deganda Век va Saralovchi I tokchani emas, shu tartib raqamli tokcha buyumni tushunadi. Tokchalar sonining quyi chegarasi — INF, yuqori chegarasi — SUP kabi belgilanadi. Yuqoridagi belgilashlarga ko‘ra INF=1, SUP 2
esa masala shartlarida aniqlab boriladi. Avval, tokchalarni alifbo bo‘yicha А, B, D kabi belgilamoqchi boMdik. Lekin tokchalar soni ko‘payganda harflar ikkitalab, uchtalab va shu kabi qo‘shib yozilishi anchagina qiyinchilik keltirib chiqarishi noqulaylikka sabab boMardi. Shuning uchun tokchalar soni 10 tadan kam bo‘lsa, biz haflardan ham foydalanaveramiz. Ya’ni, A harfi tokcha(l) ni, В harfi tokcha (2) ni va shu kabi tushunilaveradi. Bu ma’lumotlarning hammasi Век va Saralovchi I ga tushunarli ekan. Yangi Ijrochimiz Saralovchi 1 sonlar ustida arifmetik amallarni bajara oladi va tekshirilayotgan quyidagi shartlami ROST yoki YOLG‘ON ekanligini biladi, ya'ni bu shartlarni tekshira oladi hamda shu asosida mantiqiy xulosa chiqara oladi: = (teng), O (tengem as), < = (katta emas), >(katta). > = (kichik emas). Sodda dasturli Ijrochi Saralovchi I ning ko‘rsatmasi faqatbitta: o‘tkaz tokcha(N), tokcha (M) Bu amalni bajarganda Saralovchi I qoMi bilan tokcha (N) dagi buyumni ko‘tarib, tokcha (M) ga olib qo‘ya oladi. Agar bu jarayonda tokcha(M) bo‘sh bo‘lmasa, undagi buyumni surib tushirib yuborib, bo‘shatadi va so‘ng tokcha (N) dagi buyumni q °‘ya oladi. Umuman, buyum qo‘yilayotgan tokchani bo‘sh deb hisoblash mumkin, baribir undagi buyumlar tashlab yuboriladi. Век faqat shu axborotlar asosida Saralovchi 1 ni boshqarish dastunni tuzishi kerak. Bu yerda qiziq bir usulni ko‘rish mumkin miqdorni o‘zgartinb uning awalgi nomini saqlab qoldik. Bundan qiymati o ‘zgaradigan miqdor tushunchasi paydo bo‘ladi 1.2. Saralash tushunchasi Saralash deb, berilgan obyektlar ketma-ketligini ma`lum mantiqiy tartibda qayta joylashtirish jarayoniga aytiladi. Saralash bir necha ko`rsatkichlarga bog`liq bo`lishi mumkin. Misol uchun maktabda jismoniy tarbiya dars boshida bolalar bo`ylariga qarab safda turishadi. Me`yor topshirish jarayonida esa sinf jurnalidagi familiyalar ketmaketligiga qarab topshirishadi. Shu yerning o`zida 2 ta saralashdan foydalaniladi. Birinchisi bo`y uzunligi bo`yicha, ikkinchisi sinf jurnalida alvabit tartibida saralanadi. Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Biror bir ma’lumotni saralash yoki 3