Birlashtirib saralash algoritmlari

Yuklangan vaqt:

15.08.2023

Ko'chirishlar soni:

0

Hajmi:

716.787109375 KB

Ko'chirib olish

Birlashtirib saralash (Merge sort) –
tartiblashning tezkor bajariladigan algoritmlaridan
biri. Ushbu tartiblash “bo’lib tashla va hukmronlik
qil” prinsipining yaxshi namunasidir. Birinchidan,
vazifa bir nechta kichik topshiriqlarga bo'linadi.
Keyin ushbu vazifalar rekursiv chaqiruv yordamida
yoki to'g'ridan-to'g'ri ularning hajmi yetarlicha kichik
bo'lsa hal qilinadi. Nihoyat, ularning y echimlari
birlashtirilib, asl muammoning echimi olinadi.

•
Algoritmning bajarilishi.
•

•
Saralash muammosini hal qilish uchun uch
bosqich quyidagicha bo’ladi:
•
Saralanadigan massiv taxminan bir xil
o'lchamdagi ikki qismga bo'linadi;
•
Olingan qismlarning har biri alohida saralanadi
(masalan, xuddi shu algoritm bo'yicha
saralanadi);
•
Yarim kattalikdagi ikkita saralangan massivlar
birlashtiriladi.

•
“ Bo’lib t ashla v a huk mronlik qil” st rat egiy asi
•
“ Bo’lib tashla va hukmronlik qil” strategiyasi yordamida
muammoni qismiy jarayonlarga ajratamiz. Har bir
kichik topshiriq uchun yechimga ega bo'lsak, pastki
vazifalarni yechish uchun pastki vazifalardan olingan
natijalarni "birlashtiramiz".
•
Aytaylik, biz A massivni saralashni xohladik. Kichik
vazifa bu p indeksidan boshlanib, r indeksida tugagan,
A [p..r] bilan belgilangan kichik qismini ajratishdir.
•
“ Bo’lib t ashlash”
•
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 .

•
“ Huk mronlik 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
•
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.

Birlasht irib saralash algori t mi
MergeSort funksiyasi massivni ketma-ket ikki qismga ajratadi, biz
1-darajali ichki massivda MergeSort-ga o'tishga harakat qiladigan
bosqichga yetguncha ya’ni p == r bo’lguncha.
Shundan so'ng, birlashtirish funktsiyasi ishga tushadi, bu
tartiblangan massivlarni butun massiv birlashguncha katta
massivlarga birlashtiradi.
MergeSort(A, p, r)
If p > r
return;
q = (p+r)/2;
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)

•
Butun massivni saralash uchun MergeSort (A, 0, length (A) -1) ga
murojaat qilishimiz kerak.
•
Quyidagi rasmda ko'rsatilgandek, birlashtirib saralash algoritmi 1
elementli massivning asosiy holatiga kelgunimizcha massivni
rekursiv ravishda ikkiga bo'ladi. So'ngra birlashtirish funktsiyasi
saralangan ichki massivlarni tanlaydi va butun qatorni asta-sekin
saralash uchun ularni birlashtiradi.
•
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.
•

•
Algoritm uchta ko'rsatgichni saqlaydi, ikkitasi har biri uchun va
bittasi tartiblangan qatorning joriy indeksini saqlab qolish uchun.
•

Birlasht irib saralash algorit mi uchun dast ur k odi

// C++ program for Merge Sort
#include <iostream>
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++;
}
k++;
}
// L [] ning qolgan elementlarini nusxalash,
//agar mavjud bo'lsa
while (i < n1) {
Array[k] = L[i];
i++;
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);
}

$// Massi v ni chop et ish funk siy asi v oi d print A rray a y (int A [], int size) { for (int i = 0; i < si ze; i ++) cout << A [i] << " " ; } int m ain() { int A rra y [] = { 12, 11, 13, 5, 6, 7 }; int A rra y _si ze = sizeof(A rray ) / si zeof(A rray [0]); cout << " Berilgan m assiv \n" ; print A rray a y (A rray, A rray _size); mergeSort (A rray, 0, A rray _size - 1); cout << " \n Tart ibla ngan ma ssiv \n" ; print A rray a y (A rray, A rray _size); ret urn 0; }$ 6 19 3 8 92 15 1 9
6 19 3 8 92 15 1 9
6 19 3 8 92 15 1 9
6 19 3 8 92 15 1 9
6 19 3 8 15 92 1 9
3 6 8 19 1 9 15 92Massivning dastlabki ko’rinishi
Saralash qadamlari

6 19 3 8 92 15 1 9
6 19 3 8 92 15 1 9
6 19 3 8 92 15 1 9
6 19 3 8 92 15 1 9
6 19 3 8 15 92 1 9
3 6 8 19 1 9 15 92Massivning dastlabki ko’rinishi
Saralash qadamlari

Saralash f unk siy asi k odi

void MergeSort (int* x, int first, int last)
{
if (first < last)
{
int split = (first + last) / 2;
MergeSort (x, first, split);
MergeSort (x, split + 1, last);
Merge (x, first, split, last);
}
}

Massivning uzunligi 1dan katta bo'lsa, uning o'rtasi hisoblanadi (split o'zgaruvchi),
so'ngra chap va o'ng tomonlar uchun ikkita rekursiv chaqiruv boshlanadi, ular
funksiya ushbu misoliga qaytganda, ular bog’lanadigan Merge funksiyasi:
void Merge (int* x, int first, int split, int last) { int pos1 = first, pos2 = split + 1, pos3 = 0; int* temp =
new int [last — first + 1]; while (pos1 <= split && pos2 <= last) {
if (x [pos1] < x [pos2])
temp [pos3++] = x [pos1++];
else
temp [pos3++] = x [pos2++];
}
while (pos2 <= last)

temp [pos3++] = x [pos2++]; while (pos1 <= split)
temp [pos3++] = x [pos1++];
for (int i = 0; i < last — first + 1; ++i)
x [first + i] = temp [i];
}

Algorit mning murak k abligini taxmin qilaylik. Har qanday
rekursiv funktsiya chaqiruvi daraxtga o'xshaydi (Izoh:
“Daraxtlar” haqida keyingi ma’ruzalarda to’xtalib o’tiladi).
Bunday daraxtni rekursion daraxt deb ham atashadi.
Daraxtning har bir darajasi bir yoki bir nechta funktsiya
chaqiruvlarini aks ettiradi. Shoxlari bo'lmagan daraxt
tugunlari rekursiyani tugatadigan funktsiya chaqiruvlarini
anglatadi. Birlashtirish tartibida daraxtning balandligi
log
2 n ga teng, chunki har bir qadamda boshlang’ich massiv
n/2 uzunlikdagi ikkita ichki massivga bo'linadi. Ajratishdan
so'ng, birlashtirish operatsiyasi amalga oshiriladi.
Birlashtirish jarayoni n taqqoslashni, navbati bilan log n
marta, ya'ni daraxtning har bir darajasi uchun 1 marta
takrorlashni talab qiladi. Keyin algortim asimptotikasi O
(nlogn) bo'ladi.

Ber ilgan algoritmning turli xil tiplar uchun ishlash vaqti
(elementlar soni 50000 ta)

Birlashtirib saralash algoritmlari.

Birlashtirib saralash (Merge sort) – tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash “bo’lib tashla va hukmronlik qil” prinsipining yaxshi namunasidir. Birinchidan, vazifa bir nechta kichik topshiriqlarga bo'linadi. Keyin ushbu vazifalar rekursiv chaqiruv yordamida yoki to'g'ridan-to'g'ri ularning hajmi yetarlicha kichik bo'lsa hal qilinadi. Nihoyat, ularning y echimlari birlashtirilib, asl muammoning echimi olinadi.

• Algoritmning bajarilishi. • • Saralash muammosini hal qilish uchun uch bosqich quyidagicha bo’ladi: • Saralanadigan massiv taxminan bir xil o'lchamdagi ikki qismga bo'linadi; • Olingan qismlarning har biri alohida saralanadi (masalan, xuddi shu algoritm bo'yicha saralanadi); • Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi.

• “ Bo’lib t ashla v a huk mronlik qil” st rat egiy asi • “ Bo’lib tashla va hukmronlik qil” strategiyasi yordamida muammoni qismiy jarayonlarga ajratamiz. Har bir kichik topshiriq uchun yechimga ega bo'lsak, pastki vazifalarni yechish uchun pastki vazifalardan olingan natijalarni "birlashtiramiz". • Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p indeksidan boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan kichik qismini ajratishdir. • “ Bo’lib t ashlash” • 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 .

• “ Huk mronlik 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 • 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.

O'xshashlar

Markovning normal algoritmlari

MA’LUMOTLARNI SARALASH. SARALASHNI BIRLASHTIRISH(SILYANIE)USULI

M5. TARMOQDA AXBOROT TIZIMLARINI HIMOYALASH ALGORITMLARI

END-TO-END MODELLAR ASOSIDA O‘ZBEK TILIDAGI NUTQNI AVTOMATIK TANIB OLISHNING ALGORITMLARI VA DASTURIY TA’MINOTINI ISHLAB CHIQISH