Ma’lumotlarni saralash. Saralashning o‘rniga qo‘yish (vstavka) algoritimi
![ ( 1 2 4 5 8) → ( 1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8 ) → (1 2 4 5 8 )
Algoritmi va dasturi
public class BubbleSort {
public static void main(String[] args) {
int[] massiv = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
int n = massiv.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (massiv[i] > massiv[k]) {
int temp;
temp = massiv[i];
massiv[i] = massiv[k];
massiv[k] = temp;
}
}
for (int i = 0; i < massiv.length; i++) {
System.out.print(massiv[i] + ", ");
}
System.out.println("\n");
}
}
}
Chiqariluvchi natijamiz esa:
2, 4, 6, 9, 12, 23, 0, 1, 34, // 1-qadam.
2, 4, 6, 9, 12, 0, 1, 23, 34, //2-qadam.
2, 4, 6, 9, 0, 1, 12, 23, 34,//3-qadam.
2, 4, 6, 0, 1, 9, 12, 23, 34,//4-qadam.
2, 4, 0, 1, 6, 9, 12, 23, 34,//5-qadam.
7](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_7.png?v=1)
![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 (n
ʻ 2
), bu yerda n —
elementlar soni.
Tanlab saralash qanday ishlaydi?
Misol tariqasida quyidagi massivni ko rib chiqamiz: arr[] = {64, 25, 12, 22,
ʻ
11}
Birinchi o tish:
ʻ Saralangan massivdagi birinchi o rin uchun butun ʻ massiv 0
dan 4 gacha bo lgan indeksdan ketma-ket o tkaziladi. Hozirgi vaqtda 64
ʻ ʻ
saqlanadigan birinchi pozitsiya, butun massivni aylanib o tgandan so ng, 11
ʻ ʻ
eng past qiymat ekanligi ayon bo ladi.
ʻ
64 25 12 22 11
Shunday qilib, 64 ni 11 bilan almashtiring. Bir iteratsiyadan so ng
ʻ
massivdagi eng kam qiymat bo lgan 11 , tartiblangan ro yxatning birinchi
ʻ ʻ
pozitsiyasida paydo bo ladi.
ʻ
11 25 12 22 64
Ikkinchi o tish:
ʻ 25 mavjud bo lgan ikkinchi pozitsiya uchun massivning ʻ
qolgan qismini yana ketma-ketlikda aylantiring.
11 25 12 22 64
Ketishdan so ng biz 12 massivdagi ikkinchi eng past qiymat ekanligini va u
ʻ
massivda ikkinchi o rinda paydo bo lishi kerakligini aniqladik, shuning uchun
ʻ ʻ
bu qiymatlarni almashtiring.
11 12 25 22 64
9](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_9.png?v=1)
![Dasturi
# include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
void printArray(int arr[], int size)
{
int i;
for (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]);
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
11](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_11.png?v=1)
![}
Insertion sort
Insertion 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.
ʻ ʻ
Dark inverted insertion sorting
Joylab saralashning xususiyatlari
Bu algoritm oddiy amalga oshirilgani uchun eng oddiy algoritmlardan biridir.
Insertion sort kichik ma lumotlarni saralash uchun samarali. Joylab saralash
ʼ
tabiatan moslashuvchan, ya ni qisman saralangan ma lumotlar to plamlari
ʼ ʼ ʻ
uchun mos keladi.
Insertion sort ham Selection sort va Bubble sort kabi O(n 2
) vaqt
murakkabligi bilan ishlasa ham, lekin ulardan ko ra samaraliroq algoritm
ʻ
hisoblanadi. Aynan, massiv elementlari deyarli saralangan holatda Insertion
sort algoritmi Merge sort yoki Quick sort algoritmidan ham ko ra tezroq
ʻ
ishlaydi.
Joylab saralash algoritmining ishlashi
Misolni ko rib chiqing: arr[]: {12, 11, 13, 5, 6}
ʻ
12](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_12.png?v=1)
![using namespace std;
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, N);
printArray(arr, N);
return 0;
}
Saralash tushunchasi;
Saralash algoritmlari:
Qo’shish orqali saralash;
Tanlash orqali saralash;
15](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_15.png?v=1)
![bir qadamda ( i=2 dan boshlanib, har bir qadamda bir birlikka oshirib boriladi)
boshlang’ich ketma-ketlikdan
i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo’yiladi.
To’g’ridan-to’g’ri qo’shish orqali saralash algoritmi quyidagicha
bo’ladi:
for(inti=1;i i="">
x=a[i];
x ni a[0]...a[i]oraliqning mos joyiga qo‘shish
}
Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo’ladi.
2-elementdan
boshlab har bir elementni qarab chiqamiz, ya ni har bir element o’zidan oldin‟
turgan
element bilan solishtiriladi. Agar qaralayotgan element kichik bo’lsa, oldinda
turgan element bilan o’rin almashadi va yana o’zidan oldinda turgan element bilan
solishtiriladi, jarayon shu kabi davom etadi. Bu jarayon quyidagi shartlarning
birortasi bajarilganda to’xtatiladi:
1. x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda.
2. x elementi oldida element qolmaganda.
for(inti=1;i<="" i="">
while(a[j]<="" i="">
19](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_19.png?v=1)
![int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Algoritm samaradorligi
Faraz qilaylik, taqqoslashlar soni C , o’rinlashtirishlar soni M bo’lsin. Agar
massiv elementlari kamayish tartibida bo’lsa, u holda taqqoslashlar soni eng
katta bo’lib, u ga teng bo’ladi, ya ni . O’rinlashtirishlar soni esa ga teng
‟
bo’ladi, ya ni . Agar berilgan massiv o’sish tartibida saralangan bo’lsa,
‟
u holda taqqoslashlar va o’rinlashtirishlar soni eng kichik
bo’ladi, ya ni , .
‟
1.3.QUIKSORT-TEZ SARALASH ALGORITMI
Bu algoritm “bo’lib ol va egalik qil” tamoyilining yaqqol misolidir. Bu
algotirm rekursiv bo’lib, o’rtacha N*log2N
ta solishtirish natijasida saralaydi.
Algoritm berilgan massivni saralash uchun uni 2taga bo’lib oladi. Bo’lib olish
uchun ixtiyoriy elementni tanlab undan 2ta qismga ajratiladi. Lekin o’rtadagi
20](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_20.png?v=1)
![Agar i<=j bo’lsa,
3-qadamga o’tiladi.
Birinchi o’tishdan keyin tanlangan element o’zining joyiga kelib joylashadi.
6. Endi shu ko’rilayotgan oraliqda key kalitning chap tomonida elementlar mavjud
bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya’ni ko’riladigan
oraliq 0 dan key-1 gacha deb belgilanadi va 2-qadamga. Aks holda keyingi
qadamga o’tiladi.
7. Endi shu ko’rilayotgan oraliqda key kalitning o’ng tomonida elementlar mavjud
bo’lsa, ular ustida yuqoridagi amallarni bajarish lozim, ya ni ko’riladigan
‟
oraliq key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks
holda algoritm tugaydi.
2.Bob. SARALASHNING O’RNIGA QO’YISH ALGORITIMI
2.1. O'rniga qo'yish bilan saralash algoritmi
Ushbu saralash algoritmining asosiy mohiyati saralangan ro'yxatga yangi el е m е nt
qo'shishda uni “o'z joyiga” joylashtirishdan iboratdir. Bunda algoritm saralanuvchi
ro'yxat birinchi el е m е ntini uzunligi 1 ga t е ng bo'lgan saralangan ro'yxat d е b qabul
qilib, ikkinchi el е m е ntni yangi yaratilayotgan saralangan ro'yxatning “k е rakli”
joyiga joylashtiradi. So'ngra b е rilgan ro'yxatning uchinchi el е m е nti ham
saralangan ikki el е m е ntli ro'yxatdagi o'z joyiga joylashtiriladi va hokazo. Ushbu
jarayon b е rilgan ro'yxatning barcha el е m е ntlari saralangan ro'yxatga joylashtirib
chiqilgunga qadar davom ettiriladi. O'rniga qo'yish algoritmining ifodasi
quyidagidan iborat: InsertSort(List,N) For i=2 to N do newElement=list[i]
l о cation=i-1 while (location) >=1) and(list[location]> newElement) do
22](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_22.png?v=1)
![list[location+1] = list[location] location= location-1 end while list[location+1] =
newElement end For Ushbu algoritm newElement o'zgaruvchisiga yangi o'rniga
qo'yiluvchi qiymatni kiritadi. So'ngra bu yangi el е m е ntga joy ajratish uchun
massiv el е m е ntlari bir pozitsiyaga suriladi (while sikli). Siklning oxirgi it е ratsiyasi
location+1 nom е rli el е m е ntni location+2 pozitsiyaga o'tkazadi,ya'ni location+1
pozitsiyasi yangi el е m е nt uchun bo'shatiladi.
2.2.Birlashtirish bilan saralash algoritmi
Ushbu saralash algoritmi r е kursiv xarakt е rga egadir. Bitta el е m е ntdan iborat
bo’lgan ro’yxat saralangan bo’lganligi uchun algoritm ro’yxatni bir el е m е ntli
ro’yxatlarga ajratib, so’ngra ularni k е tma-k е t birlashtiradi.Bunda ro’yxat k е tma-k е t
ikki qismga ajratib boriladi. Ikkiga bo’lish jarayoni bo’lak ro’yxat birinchi
el е m е ntining nom е ri shu bo’lakdagi oxirgi el е m е nti nom е ridan kichik bo’lgunga
qadar davom etadi. Agar navbatdagi bo’lakda bu shart bajarilmasa, bitta el е m е ntli
bo’laklar hosil bo’lgan d е b hisoblanadi. Uzunligi birga t е ng bo’lgan ro’yxatlar
uchun ikkita murojaatdan so’ng ushbu ikki ro’yxatni birlashtiruvchi prots е dura
chaqiriladi. Buning natijasida uzunligi ikkiga t е ng bo’lgan saralangan ro’yxat hosil
bo’ladi. K е yingi bosqichda ikkiga t е ng uzunlikdagi saralangan ro’yxatlar uzunligi
to’rtgat е ng bo’lgan saralangan ro’yxatlarga birlashadi. Bu jarayon ikkita
saralangan yarim ro’yxatlar birlashuvchi qadamgacha davom etadi.
2.3.Diskli хо tir а qurilm а sining tuzilishi
T а shqi s а r а l а sh j а r а yoni t а shqi хо tir а d а s а ql а nuvchi ах b о r о tl а rni s а r а l а sh
v а zif а sini b а j а r а di. T а shqi s а r а l а sh j а r а yoni ichki s а r а l а shd а n k а tt а f а rq qil а di.
Chunki t а shqi f а yll а rg а mur о j аа t to’g’rid а n – to’g’ri em а s, k е tm а -k е t usuld а
а m а lg а о shiril а di. Bund а ах b о r о tl а rni f а q а t bl о kl а b o’qish mumkin. T а shqi
s а r а l а sh j а r а yonini tushunish uchun diskl а rning fizik tuzilishi bil а n umumiy
t а nishib chiqish k е r а k bo’l а di. Diskl а rning t а shqi sirti m а gnitli q о pl а mg а eg а
bo’lib, ul а r d о imiy k а tt а t е zlik bil а n o’z o’qi а tr о fid а а yl а n а di. Diskl а rning h а r bir
ish s о h а sig а bitt а o’qish-yozish qurilm а si o’rn а tilg а n. Ах b о r о tl а rg а mur о j аа t
v а qtid а o’qish-yozish qurilm а si t о m о nid а n tr е kl а r d е b а t а luvchi diskd а gi
m а ’lum о tl а r yozilg а n yo’l а kch а l а rd а n b е rilg а nl а r o’qil а di. Bu tr е kl а r yig’indisi
j о riy silindr d е b а t а l а di.O’qish-yozish qurilm а l а ri m ах sus sht а ng а g а o’rn а tilg а n
bo’lib, bu sht а ng а burilg а nd а o’qish-yozish qurilm а si b о shq а silindrg а o’tq а zil а di.
Silindrl а r sht а ng а ning bir t о m о ng а h а r а k а ti v а qtid а o’qish-yozish qurilm а l а ri
bl о kining ul а rg а mur о j аа t qilish t а rtibid а n о m е rl а n а di. B е rilg а nl а r el е m е ntl а ri
23](https://docx.uz/documents/f490ce4f-1532-4730-8b40-8d8aa891a729/page_23.png?v=1)
Ma’lumotlarni saralash. Saralashning o‘rniga qo‘yish (vstavka) algoritimi