Ko‘p oqimli birlashtirish saralash algoritimi
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_3.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_5.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_7.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_11.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_12.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_13.png?v=1)
![#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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_14.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_15.png?v=1)
![}
// 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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_16.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_22.png?v=1)
![}
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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_23.png?v=1)
![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](https://docx.uz/documents/9aabebb7-e33d-4801-84d3-b1112ef6dd5e/page_24.png?v=1)
Ko‘p oqimli birlashtirish saralash algoritimi