Insertion sort => oltita elementdan iborat massivda : insertion-sort ning ishlash vaqti haqida nima deymiz? Merge sort

Mavzu : Saralash algoritmlari
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 asosiy algoritmlari :

1. 
   Selection sort.
   
2. 
   Insertion sort.
   
3. 
   Merge sort.
   
4. 
   Quick sort.
   

Selection sort
Esda tuting: Har bir element massivdagi quyidagi elementdan kichik yoki unga teng.

Selection sort => oltita elementdan iborat massivda :

SELECTION-SORT ning ishlash vaqti qancha?

Ichki halqa necha marta takrorlanadi? Esda tuting: har bir iteratsiya Ѳ(1) vaqt oladi.

Ichki halqa iteratsiyasining umumiy soni (n-1)+(n-2)+(n-3)+…+2+1

n+(n-1)+(n-2)+(n-3)+…+2+1=n(n+1)/2
(n-1)+(n-2)+(n-3)+…+2+1=n(n-1)/2=(n²-n)/2
Bu arifmetik qatorlarning yig'indisidir. Shuning uchun SELECTION-SORT ning ishlash vaqti Ѳ(n2) ga teng.
Insertion sort


Insertion sort => oltita elementdan iborat massivda :

INSERTION-SORT ning ishlash vaqti haqida nima deymiz?

Merge sort
Ishlash vaqtlari tanlash tartiblash va kiritish tartiblash t(n2) dir. Birlashtirishning ishlash vaqti t(nlgn) dir. D(nlgn) yaxshiroq, chunki lgn ko'proq o'sadi n ga qaraganda sekin.
Kamchiliklari:
Asimptotik yozuvdagi doimiy omil boshqa ikkita algoritmga qaraganda yuqori.
Agar massiv o'lchami n katta bo'lmasa, birlashtirish tartibi ishlatilmaydi.
2. Birlashtirish tartibi to'liq nusxalarini yaratishi kerak barcha kirish massivi.
Agar kompyuter xotirasi muhim bo'lsa,birlashtirish tartibi ham ishlatilmaydi.

Dastlabki qo'ng'iroq - MERGE-SORT(A, 1, 10).

2A qadam q ni 5 deb hisoblaydi,2B va 2C bosqichlarida MERGE-SORT (A, 1, 5)
va MERGE-SORT (A, 6, 10).

Ikki rekursiv qo'ng'iroq qaytgandan so'ng, bu ikkita pastki qatorlar tartiblanadi.

Nihoyat, 2D bosqichida MERGE (A, 1, 5, 10) chaqiruvi

MERGE protsedurasi tartiblangan pastki qatorlarni bitta tartiblangan pastki qatorga birlashtirish uchun ishlatiladi.

Keling, kitob javonining 9-uyadan 14-uyagacha bo'lgan qismini ko'rib chiqaylik.
Biz kitoblarni 9-11-uyalarga va 12-14-uyalarga kitoblarni saralab oldik.

Biz 9–11-uyalardagi kitoblarni chiqaramiz va muallifi alifbo tartibida birinchi bo'lgan kitob bilan bir to'plam hosil qilamiz va biz 12-14-uyalardagi kitoblar bilan ham xuddi shunday qilamiz.

Ikkita to'plam allaqachon saralanganligi sababli, 9-uyaga qaytishi kerak bo'lgan kitob uning stekidagi kitoblardan biri bo'lishi kerak.Biz Dikkens kitobi Flober kitobidan oldin kelganini ko'ramiz va shuning uchun uni 9-uyaga o'tkazamiz.

10-uyaga Floberning birinchi kitobi yoki Jek Londonning ikkinchi stek ustidagi kitobi bo'lishi kerak. Biz Flaubert kitobini 10-uyaga o'tkazamiz.

Va shu tariqa saralash davom etadi.
Quick sort
Quicksort bo‘l va zabt et paradigmasidan foydalanadi va rekursiyadan foydalanadi.
Birlashtirish tartibidan ba'zi farqlar mavjud:
Quicksort joyida ishlaydi.
Quicksortning eng yomon ish vaqti D(n2), lekin uning oʻrtacha ish vaqti yaxshiroq: D(nlg n).
Quicksort ko'pincha amalda foydalanish uchun yaxshi tartiblash algoritmidir.
Avval p dan r gacha bo'lgan oraliqlarda joylashgan har qanday kitobni tanlash orqali bo'ling. Ushbu kitobni asosiy deb nomlang.
Tokchadagi kitoblarni shunday tuzingki, muallif ismlari pivot muallifidan oldin kelgan barcha boshqa kitoblar pivotning chap tomonida, muallif ismlari pivot muallifidan keyin keladigan barcha kitoblar esa pivotning o‘ng tomonida bo‘lsin.
London kitobining chap tomonidagi kitoblar alohida tartibda emas va o'ngdagi kitoblar uchun ham xuddi shunday.
Kitoblarni aylanmaning chap va o'ng tomonidagi rekursiv tartiblash orqali zabt eting.
Birlashtiring - hech narsa qilmasdan!


Yaxshiroq holatda, quicksort ish vaqti D (nlgn) ga ega.Eng yomon holatda, tezkor saralashning ishlash vaqti D (n2) ga ega.
MISOL :
public class BubbleSort {
public static void bubble_srt(int massiv[]) {// funksiyamizga saralash uchun saralanmagan bir o`lchamli massiv kiritiladi
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]) {
almashtirish(i, k, massiv);//almashtirish uchun alohida funksiya
}}chiqarish(massiv);//chop etish uchun alohida funksiya
} } private static void almashtirish(int i, int j, int[] massiv) {
int temp;
temp = massiv[i];
massiv[i] = massiv[j];
massiv[j] = temp; }
private static void chiqarish(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n"); }
public static void main(String[] args) {
int[] saralanmagan = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
bubble_srt(saralanmagan); }
}