3-Laboratoriya ishi

Pufakli saralash (Bubble sort )

Usulning g'oyasi: saralash bosqichi ketma-ket yuqoriga ko'tarilishdan iborat. Yo'lda qo'shni elementlarning juftlari tekshiriladi. Agar ma'lum bir juftlikning elementlari noto'g'ri tartibda bo'lsa, biz ularni almashtiramiz.

public static void InnerSort (int []a) {

int n = a.length;

for(int i=1; i

{System.out.println("i= "+ i);

for(int j=0; j

{ System.out.println("j= "+ j);

if(a[j] > a[j+1] )

{ int x = a[j];

a[j] = a[j+1];

a[j+1] = x;

System.out.println(Arrays.toString(a)); }}}

System.out.println(Arrays.toString(a)); }

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n;

n = in.nextInt();

int []a = new int [n];

for(int i=0; i

{ a[i] = (int)(Math.random()*50); }

System.out.println(Arrays.toString(a));

InnerSort (a);

Topshiriqlar

Pufaksimon saralash usulidan foydalanib, saralashni amalga oshirish dasturini ishlab chiqish (variantga mos ravishda):

1.A massivning eng katta (eng kichik) elementini ekranga chiqarish dasturini tuzing.

2. A massiv elementlari qiymatlarini kamayish tartibida saralash dasturini tuzing.

3. A massivda elementlar berilgan. Mazkur massiv elementlaridan shunday V massiv shakllantiruvchi shunday dastur tuzingki, V massiv elementlari kamayish tartibida saralangan bo’lsin.

4. Elementlari o’sish tartibida joylashgan A sonli massiv va a soni berilgan. a ni A massivga shunday qo’shingki, tartiblanganlik buzilmasin.

5. Elementlari o’sish tartibida joylashgan A massivni, elementlari kamayish tartibida joylashgan massiv ko’rinishida tez quruvchi dastur tuzing.

6. Manfiy va musbat sonlardan tashkil topgan A massiv berilgan. Barcha manfiy sonlarni chiqarib, musbatlarini o’sish tartibda joylashtiruvchi dastur tuzing.

7. Berilgan A massivdan ketma-ket sonlar olib, ulardan o’sish tartibida shakllantirilgan V massiv hosil qiluvchi dastur tuzing.

8. Mualliflar ro’yhati A massiv shaklida berilgan. Mualliflarni alifbo tartibida shakllantirish va shakllangan ro’yhatni ekranga chiqarish dasturini tuzing.

9. Telefon stansiyasida n ta mijoz bor. Quyidagi shaklda ro’yhat hosil qiluvchi dastur tuzing: telefon raqami, mijoz familiyasi (telefon raqamlari o’sish tartibida joylashadi).

10. A massivni uzunliklari har xil bo’lgan n ta so’z tashkil qiladi. So’zlarni uzunliklari bo’yicha o’sish tartibida joylashtiruvchi dastur tuzing.

Bеrilgan A(N) massiv elеmеntlarini B(N) massivga tеskari tartib bilan yozing.

11. A(N) massiv bеrilgan. B(N) massivni quyidagi formula yordamida hosil qiling:

bi = (a1 + a2 + ... + ai ) / i.

12. Bеrilgan X(N) massivning maksimal kompanеntdan (agar ular bir nеchta bo’lsa, maksimal kompanеntni tartibi bo’yicha birinchisini oling) oldingi barcha manfiy kompanеntlarni nol bilan almashtiring.

13. Bеrilgan X(N) massivning bеshga karrali bo’lmagan barcha elеmеntlari kvadratlari yig’indisini hisoblang.

14. Bеrilgan X(N) massivda eng kichik va eng katta elеmеntlar o’rnini almashtiring.

15. Bеrilgan X(N) massivdagi bеrilgan qiymatdan kichiklarning sonini aniqlang.

16. N –natural son bеrilgan . U nеchta raqamdan tuzilgan tеkshiring

17. Bеrilgan natural sonning raqamlar yig’indisini toping.

18. Bеrilgan natural sonning raqamlarini tеskari tartibda yozing.

19. Bеrilgan A(N) vеktorda ikkita kеtma-kеt kеluvchi nol elеmеnt mavjudmi

tеkshiring.

20. Bеrilgan A(N) vеktorda uchta kеtma-kеt kеluvchi bir xil ishorali elеmеnt mavjudmi tеkshiring.

Shell saralash usuli.

Qisqichbaqasimon saralash Donald L. Shell tomonidan ixtiro qilingan. Uning o'ziga xosligi shundaki, u butun ro'yxatni aralash sub-ro'yxatlar to'plami sifatida ko'rib chiqadi. Birinchi bosqichda ushbu pastki ro'yxatlar shunchaki elementlarning juftlari. Ikkinchi bosqichda har bir guruhda to'rtta element mavjud. Jarayon takrorlanganda, har bir kichik ro'yxatdagi elementlar soni ko'payadi va pastki ro'yxatlar soni mos ravishda kamayadi.

Shaklda 3.1 ro'yxat 16 ta elementni saralashda ishlatilishi mumkin bo'lgan ichki ro'yxatni ko'rsatadi.

Shaklda 3.1 (a) sakkizta pastki ro'yxatni ko'rsatadi, ularning har ikkitasida ikkita element mavjud bo'lib, unda birinchi pastki ro'yxat birinchi va to'qqizinchi elementlarni, ikkinchi pastki ro'yxat ikkinchi va o'ninchi elementlarni o'z ichiga oladi va hokazo.

Shaklda 3.1 (b) biz allaqachon har birida to'rtta elementning to'rtta pastki ro'yxatini ko'rmoqdamiz. Bu safar birinchi pastki ro'yxat birinchi, beshinchi, to'qqizinchi va o'n uchinchi elementlarni o'z ichiga oladi. Ikkinchi pastki ro'yxat ikkinchi, oltinchi, o'ninchi va o'n to'rtinchi elementlardan iborat. Shaklda

3.1 (c) mos ravishda juft va juft raqamlardan iborat ikkita ichki ro'yxatni ko'rsatadi. Shaklda 3.1 (d), biz yana bitta ro'yxatga qaytamiz.

Dastur kodi :

public static void sort (int[] arr)

{

for (int inc = arr.length / 2; inc >= 1; inc = inc / 2)

for (int step = 0; step < inc; step++)

insertionSort (arr, step, inc);

System.out.println(Arrays.toString(arr));

}
private static void insertionSort (int[] arr, int start, int inc)

{

int tmp;

for (int i = start; i < arr.length - 1; i += inc)

for (int j = Math.min(i+inc, arr.length-1); j-inc >= 0; j = j-inc)

if (arr[j - inc] > arr[j])

{

tmp = arr[j];

arr[j] = arr[j-inc];

arr[j-inc] = tmp;

}

else break;

}

Algoritm tahlili

Biz tahlilni InsertionSort funktsiyasiga qo'ng'iroqlar soni va ushbu qo'ng'iroqlarning har biri uchun ro'yxatdagi elementlar sonini hisoblashdan boshlaymiz. Biz uzunlik ro'yxatining alohida holatiga murojaat qilamiz. Birinchi o'tish ortish qiymatini 7 ga ko'paytiradi, shuning uchun uzunlik ro'yxatlarida ettita qo'ng'iroqlar amalga oshiriladi. Ikkinchi o'tish, kattalashtirish qiymati 3 ga teng, shuning uchun 5 uzunlik ro'yxatlarida uchta qo'ng'iroq bo'ladi. Uchinchisida va oxirgisida, Biz 15 uzunlik ro'yxatiga bitta qo'ng'iroq qilamiz. Oldingi natijalardan kelib chiqqan holda, ikkita elementning ro'yxatida InsertionSort algoritmi eng yomon holatlarda bitta taqqoslash amalga oshirilishini bilamiz. 5 elementlar ro'yxatidagi eng yomon holatlardagi taqqoslashlar soni 10tani tashkil qiladi. Eng yomon holatlarda 15 elementlar ro'yxatidagi taqqoslashlar soni 105 tani tashkil etadi. Ushbu raqamlarni qo'shgandan so'ng, biz atigi 142 ta taqqoslashni olamiz (7 • 1 + 3 • 10 + 1 • 105). Saralash algoritmlarini tahlil qilayotganda biz ba'zan ro'yxatdagi teskari siljishlar sonini hisoblaymiz. Inversiya - bu noto'g'ri tartibda ketayotgan juft elementlar ro'yxati. Masalan, [3,2,4,1] ro'yxatda to'rtta inversiya mavjud, ya'ni (3,2), (3,1), (2,1) va (4,1). Ko'zga ko'rinadigan darajada eng ko'p burilishlar, ularning elementlari teskari tartibda ketadiganlar ro'yxatidadir; ularning soni (N2 - N) / 1.

Topshiriqlar:

1) ShellSort algoritmining barcha o'tishlari natijalarini ro'yxatga 7, 5, 3 va 1-bosqichlar bilan yozing [16,15,14,13,12,11,10,9, 8, 7,6, 5,4, 3, 2, 1].

Qancha taqqoslash amalga oshirildi?

2) 8, 4, 2 va 1-bosqichlar bilan ShellSort algoritmining barcha o'tishlari natijalarini ro'yxatga yozing [16,15,14,13,12,11,10,9, 8, 7, 6, 5,4, 3, 2, 1].

Qancha taqqoslash amalga oshirildi?

3) ShellSort algoritmining 5, 2 va 1-bosqichlari bo'yicha barcha o'tish natijalarini ro'yxatga yozing [7,3,9,4,2,5,6,1,8]. Qancha taqqoslash amalga oshirildi?

4) ShellSort algoritmining 5, 2 va 1 bosqichlari bilan barcha o'tish natijalarini ro'yxatga yozing [3,5,2,9,8,1,6,4,7]. Qancha taqqoslash amalga oshirildi?

5) Ushbu bo'limda ishlatiladigan InsertSort algoritmining yangi versiyasini yozing.

6) Ushbu bo'limda biz tartiblashni inversiyalarni olib tashlash sifatida ko'rib chiqamiz. Ro'yxatdagi ikkita qo'shni bo'lmagan narsalarni qayta tartiblash orqali olib tashlanishi mumkin bo'lgan N elementlar ro'yxatidagi teskari o'zgarishlarning maksimal soni qancha? 10 uzunlik ro'yxatiga bunday almashtirishga misol keltiring.

Ildizli saralash
Ildizlarni saralashda ro'yxat kalit qiymatlarni bir-biri bilan to'g'ridan-to'g'ri taqqoslamasdan buyurtma qilinadi. Bunday holda, "vayronalar" to'plami yaratiladi va elementlar kalitlarning qiymatlariga qarab staklarga taqsimlanadi. Keyingi qiymatlarni yig'ib, kalitning ketma-ket qismlari uchun butun protsedurani takrorlab, biz tartiblangan ro'yxatni olamiz. Ushbu protsedura ishlashi uchun stacking va keyingi montaj juda ehtiyotkorlik bilan bajarilishi kerak.

Shunga o'xshash tartib kartalarni qo'lda tartiblashda qo'llaniladi. Ba'zi kutubxonalarda, kompyuterdan oldingi paytlarda, kitobni chiqarishda, kartochka to'ldirilgan. Chiqarilgan kartalar raqamlangan va karta raqamiga qarab ularning yon tomonida bir qator chuqurchalar qilingan. Kitob qaytarib berilganda, ekstraditsiya kartasi o'chirildi va qoziqqa tashlandi. So'ngra butun chuqurchaga birinchi chuqurchalar joyida uzun igna nayzalangan va igna ko'tarilgan. O'chirilgan belgi bilan kartalar stolda qoldi, qolganlari ignaga mixlab qo'yildi. Keyin paydo bo'lgan ikkita qoziqlar qayta joylashtirildi, shunda ignalardagi kartalar teshiklari bo'lgan kartalarning orqasida qoldi. Keyin igna ikkinchi chuqurchaga yopishtirilgan va butun jarayon takrorlangan. Barcha pozitsiyalarni teshib chiqqandan so'ng, kartalar raqamlar ketma-ketligida paydo bo'ldi.

Qo'lda ishlov berishning ushbu protsedurasi kartochkalarni birinchi bosqichdagi raqamning ahamiyatsiz raqamining qiymatiga va oxiridagi eng yuqori raqamga qarab ajratadi.

package koren_sort;

import java.util.Arrays;

public class Koren_sort {

void countingSort(int array[], int size, int place) {

int[] output = new int[size + 1];

int max = array[0];

for (int i = 1; i < size; i++) {

if (array[i] > max)

max = array[i]; }

int[] count = new int[max + 1];

for (int i = 0; i < max; ++i)

count[i] = 0;

for (int i = 0; i < size; i++)

count[(array[i] / place) % 10]++;

for (int i = 1; i < 10; i++)

count[i] += count[i - 1];

for (int i = size - 1; i >= 0; i--) {

output[count[(array[i] / place) % 10] - 1] = array[i];

count[(array[i] / place) % 10]--; }

for (int i = 0; i < size; i++)

array[i] = output[i]; }

int getMax(int array[], int n) {

int max = array[0];

for (int i = 1; i < n; i++)

if (array[i] > max)

max = array[i];

return max; }

void radixSort(int array[], int size) {

int max = getMax(array, size);

for (int place = 1; max / place > 0; place *= 10)

countingSort(array, size, place); }

public static void main(String args[]) {

int[] data = { 121, 432, 564, 23, 1, 45, 788 };

int size = data.length;

Koren_sort rs = new Koren_sort ();

rs.radixSort(data, size);

System.out.println(Arrays.toString(data)); } }

310 213 023 130 013 301 222 032 201 111 323 002 330 102 231 120

Berilgan tizim Berilganlar

0 310 130 330 120

1 301 201 111 231

2 222 032 002 102

3 213 023 013 323

(а) Birinshi bosqish, birlik razryad

Birinchi bosqishdan olingan tizim

310 130 330 120 301 201 111 231 222 032 002 102 213 023 013 323

Berilgan tizim Berilganlar

0 301 201 002 102

1 310 111 213 013

2 120 222 023 323

3 130 330 231 032

(б) Ikkinchi bosqish, onlik razryad

Ikkinchi bosqishdan olingan tizim

301 201 002 102 310 111 213 013 120 222 023 323 130 330 231 032

Berilgan tizim Berilganlar

0 002 013 023 032

1 102 111 120 130

2 201 213 222 231

3 301 310 323 330

(в) Uchunchi bosqish, yuzlik razryad

Uchunchi bosqishdan olingan tizim

Topshiriqlar:

1) RadixSort algoritmidan foydalanib, ro'yxatni tartiblang [1405,975, 23, 9803, 4835, 2082, 7368, 573, 804, 746, 4703, 1421, 4273, 1208, 521, 2050]. Har bir o'tish joyi va har bir ro'yxat yig'ilgandan keyin ro'yxat holatini yozib qo'ying.

2) RadixSort algoritmidan foydalanib, ro'yxatni tartiblang [117,383, 4929,144,462,1365,9726,241,1498,82,1234,8427,237, 2349,127,462].

Har bir o'tish joyi va har bir ro'yxat yig'ilgandan keyin ro'yxat holatini yozib qo'ying.

3) Ildizlarni saralashda kalit bitlarning ketma-ketligi sifatida ham ko'rib chiqilishi mumkin. Shunday qilib, siz 4 baytli butun sonni 32 bit ketma-ketligi, 15 bitli (15 baytdan iborat) tugmalarni esa 120 bitlar ketma-ketligi sifatida ko'rishingiz mumkin. Keyin bu bitlarning ketma-ketligi qismlarga bo'linadi; qism o'tish joylari va vayronalar sonini belgilaydi. Shunday qilib, masalan, 120 bitli tugmachani har biriga 10 bitning 12 qismiga yoki har birida 12 bitning 10 qismiga yoki har birining 24 qismidan 5 qismga bo'lish mumkin.

a) kalit 0 dan 264 gacha bo'lgan raqam deb faraz qiling; Har bir pasda ishlatiladigan bitlar sonining ikkita mumkin bo'lgan (kichik va kattaroq) qiymatini tanlang va mos keladigan ustunlar soni va o'tish sonini belgilang.

4 b) kalit 40 baytlik belgilar qatori deb faraz qiling; Har bir pasda ishlatiladigan bitlar sonining ikkita mumkin bo'lgan (kichik va kattaroq) qiymatini tanlang va mos keladigan ustunlar soni va o'tish sonini belgilang.