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);}
}
2-usul esa faqat main funksiyaning ichida yozishga asoslangan.
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.
Tez saralash algoritmi
Algoritm g`oyasi massivni rekursiv asosda ikkiga ajratish va tartiblash amalini ularning har biri uchun bajarishni o`z ichiga oladi. Ajratish chegaraviy deb ataladigan biror elementni tanlash orqali amalga oshiriladi. Massiv ikkiga ajratilgandan so`ng, ular shunday qayta ishlanadiki,chegaraviy elementning bir tomonida undan kichik elementlar, ikkinchi tomonida undan katta yoki teng bo`lgan elementlar joylashadi.
0
15
8
2
4
12
9
23
15
17
5
6
Faraz qilaylik, massivning 13 elementi quyidagicha joylashgan bo`lsin
a[0] a[11]
Agar chegaraviy element sifatida 9 ni tanlasak, birinchi tartiblashdan keyin quyidagi holga keladi:
0
4
8
2
15
6
5
15
17
9
12
23
a[0] a[11]
Massivning qismlarga ajratish va ularda tartiblash amalini rekursiv mexanizm
yordamida bajarish mumkin. Buning uchun chegaraviy element indeksi o`rtadagi element indeksi shaklida hisoblanadi. Bunda “first” va “last” lar massiv qismining birinchi va oxirgi elementlarining indekslarini anglatadi.
Massivning qayta ishlanayotgan qismi chetki elementlari indekslarini “chap qanot”(“ch_q”) hamda “o`ng qanot”(“o_q”) orqali belgilaymiz.
0
15
8
2
4
12
9
23
15
17
5
6
Pivot(chegara)
9
Chap qanot o`ng qanot
Tartiblash jarayonida “ch_q” va “o_q” indekslari chegaviy element tomon surilib boradi. Masalan, “o_q” indeksli element chegaraviy elementdan kichik yoki teng bo`lib qolmaguncha chapga suriladi. Xuddi shuningdek, “ch_q” indeksli element chegaraviy elementdan katta yoki teng bo`lib qolmaguncha o`ngga surilib boradi. Biz qarayotgan holda bu element massiv boshida joylashgan.
0
15
8
2
4
12
9
23
15
17
5
6
Pivot(chegara)
9
Chap qanot o`ng qanot
Almashtirish uchun chap va o`ng elementlarini izlash.
Shundan keyin bu elementlar o`zaro o`rin almashadi.
Massivni tartiblash “ch_q” > “o_q” sharti bajarilgunga qadar davom etadi.
So`nggi holatda bu shart yolg`on. Shuning uchun “ch_q” o`ngga, “o_q” chap tomonga surilib boradi.
0
4
8
2
15
12
9
23
15
17
5
6
Pivot(chegara)
9
Chap qanot o`ng qanot
Almashuvdan so`ng, “o`ng qanot” chap tomonga to pivotdan kichik element chiqquncha, “chap qanot” pivotdan katta element chiquncha o`ngga surilib boradi.
Chap qanotning surilishi chegaraviy elementgacha davom etadi
0
4
8
2
15
6
9
23
15
17
5
12
Pivot(chegara)
9
Chap qanot o`ng qanot
Bu holda “chap qanot” indeksi pivot indeksi bilan ustma-ust tushadi. Pivotdan kichik element 5. Endi 9 va 5 o`rni almashadi va “ch_q” o`ngga “o_q” chapga suriladi.
0
4
8
2
15
6
9
23
15
17
9
12
Pivot(chegara)
5
chap qanot o`ng qanot
0
4
8
2
15
6
9
23
15
17
9
12
Pivot(chegara)
5
o`ng qanot chap qanot
Bu holda tartiblash sharti “ch_q” > “o_q” o`rinli bo`lgan shart ko`rsatilgan. Shuning uchun massivni ikkiga ajratish va qayta tartiblash jarayonini tugatilgan deb hisoblash mumkin.
Quyida tez saralash algoritmi QuickSort amalga oshiruvchi funksiya keltirilgan.
Do'stlaringiz bilan baham: |