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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_7.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_9.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_11.png)
![}
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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_12.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_15.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_19.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_20.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_22.png)
![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](/data/documents/81aa48c7-2945-4883-b35b-32886c939de0/page_23.png)
MAVZU: Ma’lumotlarni saralash. Saralashning o’rniga qo’yish (vstavka) algoritimi. MUNDARIJA KIRISH 1.Bob.SARALASH TUSHUNCHASI 1.1.Saralash tushunchasi. 1.2.Algoritm samaradorligi. 1.3.Quiksort-tez saralash algoritmi. 2.Bob. SARALASHNING O’RNIGA QO’YISH ALGORITIMI 2.1.O’rniga qo’yish bilan saralash algoritmi. 2.2.Birlashtirish bilan saralash algoritmi. 2.3.Diskli xotira qurilmasining tuzilishi. FOYDALANILGAN ADABIYOTLAR RO‘YXATI. 1
KIRISH Biror bir ma’lumotni saralash yoki qandaydir qolipga solish juda ham. Sababi, tartibsiz ma’lumotlar bilan ishlash doimo noqulayliklar keltirib chiqaradi va bunday tizim sekin va xatoliklarga moyil bo’ladi Algoritmlar bir xil ishni bajarsa va ularning aksariyatining ishlash vaqti ham bir xil bo’lsa, unda ularning hammasi nimaga kerak degan haqli savol tug’iladi. Algoritm xilma-xilligiga ikkita asosiy sabab keltirish mumkin: Algoritmlarning ishlash vaqtlari har doim ham bir xil bo’lmaydi va ularning ishlashi qandaydir ma’lum holatlarda o’zgarib turadi. Ya’ni, umumiy holatda biror algoritmdan yomonroq ishlovchi boshqa bir algoritm, aynan, qandaydir holat uchun undan ko’ra yaxshiroq ishlashi mumkin. Ikkinchi sabab sifatida esa, albatta, saralash algoritmining xotiradan qo’shimcha joy egallashi va uning turg’unlik xususiyati inobatga olinadi. Saralash algoritmlarida turg’unlik (stability) deganda, ikkita bir xil elementning ilk holatdagi bir biriga nisbatan o’rninini saralashdan keyin ham saqlab qolishiga aytiladi. Masalan, 3 1 2 4 1 5 sonlari bor deylik, ularni saralmoqchimiz. Agar biz qo’llagan algoritm saraladan keyin doim birinchi 1 sonini ikkinchi 1 sonidan doim oldin joylashtirsa, bu algoritm turg’un saralovchi algoritm deyiladi. Saralash algoritmlari ichidagi Quick Sort ko’p hollarda Merge yoki Heap sortdan tez ishlagani bilan u turg’un saralash algoritmi hisoblanmaydi (Turg’un holga keltirishning iloji bor). Ko’rib turgangizdek har xil algoritmlar ishlash tezliklari bir xil bo’lgani bilan bizga turli holatlarda aynan bir turdagi algoritm kerak bo’lib qolishi va u biz tuzayotgan 2
tizim samaradorligiga ta’sir qilishi mumkin. Shu sababdan, turli xil saralash algoritmlari ishlashini o’rganish va tushunish professional dasturchi uchun muhim hislatlardan biri hisoblanadi. 1.Bob.SARALASH TUSHUNCHASI 1.1.SARALASH TUSHUNCHASI Saralash - tartiblash ( Sorting Algorithms ) 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 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 algoritm 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 3
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. Saralash algoritmi turlari Bubble sort Selection sort Insertion sort Quick sort Merge sort 4
Bubble sort Bubble sort ikki qo'shni elementni solishtirish va ular mo'ljallangan tartibda bo'lmaguncha, ularni almashtiradigan tartiblash algoritmidir. Xuddi suv yuzasiga ko'tarilgan havo pufakchalarining harakati kabi, massivning har bir elementi har bir iteratsiyada oxirigacha harakat qiladi. Shuning uchun u pufakchali saralash deb ataladi. BubbleSort “Bubble sort” bu eng sodda, ketma-ketlikdagi har bir sonni boshqa sonlar bilan solishtirishga asoslangan algoritm hisoblanadi. Unda yonma-yon turgan elementlardan chapdagisi o‘ngdagidan kattaligi aniqlansa, bu ikkala son o`rni almashtiriladi. Bu jarayon almashtirish kerak bo`lmay qolguncha davom etadi, ya`ni barcha elementlar o‘sish tartibida bo‘lib qolguncha. “Bubble sort” nisbatan ko`p vaqt talab qiluvchi saralash algoritmi hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni taqriban n*n ga teng. Bu, n kichik son bo`lsa unchalik sezilmaydi. Sababi, hozirgi zamonaviy kompyuterlar uchun bu takrorlanish soni qiyinchilik tug`dirmaydi. Ammo butun boshli ma`lumotlar bazasidagi ma`lumotlarni saralash talab 5