Reja: Saralash haqida tushuncha va algoritmlari



Download 0.78 Mb.
bet1/2
Sana13.02.2020
Hajmi0.78 Mb.
  1   2
Mavazu: Saralash tushunchasi va algoritmi. Tanlash orqali saralash va uning qo’llanilishi.

Reja:

Mavazu: Saralash tushunchasi va algoritmi. Tanlash orqali saralash va uning qo’llanilishi.



 Nima uchun kerak?

Saralash va izlash amalda juda ko’p qo’llaniladi, fayldagi so’zlarnini izlashdan tortib, internetda ma’lumot izlashgacha.



Saralash

Masalan:

5 8 9 1 5 2 3 9

Saralangandan so’ng

1 2 3 5 5 8 9 9

Saralash algoritmlari

Saralash algoritmlari ikki tipga bo’linadi.

  1. O() vaqtda saralovchi algortimlar.

  2. O(n•log(n)) vaqtda saralovchi algoritmlar.

Algoritmlarda log(n) bu .

n= bo’lganda taqqoslang:

O() = , O(n•log(n)) = 1660964.

Tanlash orqali saralash algoritmi

  • Xar qadamda hali ko’rilmagan elementlar orasidan eng kichigini tanlaymiz.

  • Bu jarayon (n-1) marta davom etadi.


min







20

8

9

1

15

2

3

9

1

8

9

20

15

2

3

9

1

2

9

20

15

8

3

9

1


2

3

20

15

8

9

9

1

2

3

8

15

20

9

9

1

2

3

8

9

20

15

9

1


2

3

8

9

9

15

20

1

2

3

8

9

9

15

20

1

2

3

8

9

9

15

20


Ikki o’zgaruvchining qiymatini almashtirish.

  • a va b ning qiymatlarini almashtirish kerak. Qo’shimcha t o’zgaruvhci kiritamiz.

  • t = a;

  • a = b;

  • b = t;

Qo’shimcha o’zgaruvchi kiritmasdan almashtirish.

  • a = a+b; (a+b, b);

  • b = a-b; (a+b, a);

  • a = a-b; (b, a);

Misol:

#include

using namespace std;

int main() {

int n;

cin>>n;

int a[n];

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

cin>>a[i];

for (int i = 0; i < n-1; i++) {

int minPos = i;

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

if (a[j] < a[minPos])

minPos = j;

int t = a[i];

a[i] = a[minPos];

a[minPos] = t;

}

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

cout<

}

  • Ishlash vatqi ().

  • Taqqoshlashlar soni ().

  • Almashtirishlar soni .

  • Qo’shimcha xotira .

Pufakcha usulida saralash(Bubble sort).

  • Agar ikki qo’shni element noto’g’ri tartibda joylashib qolgan bo’lsa, ularning o’rnini almashtiramiz.

  • Umumiy n-1 marta jarayon bajariladi. Har safar ikkita qo’shni element taqqoslanadi.

  • Elementlar o’z o’rinlariga pufakga o’xshab siljib boradi.


3

5

2

10

9

4

3

2

5

10

9

4

3

2

5

9

10

4

3

2

5

9

4

10

3


2

5

9

4

10

2

3

5

9

4

10

2

3

5

4

9

10

2


3

5

4

9

10

2

3

4

5

9

10

2

3

4

5

9

10

2

3

4

5

9

10

2

3

4

5

9

10


Misol:

#include

using namespace std;

int main() {

int n;

cin>>n;

int a[n];

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

cin>>a[i];

for (int i = n-1; i >= 1; i--) {

for (int j = 0; j < i; j++) {

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

int t = a[j];

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

a[j+1] = t;

}

}

}

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

cout<

return 0;

}

  • Ishlash vatqi ().

  • Taqqoshlashlar soni ().

  • Almashtirishlar soni().

  • Qo’shimcha xotira .

Birlashtirish orqali saralash(Merge Sort) algoritmi.

Bu algoritm Jon fon Neyman tamonidan 1946 yilda taklif qilingan.

Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional

analiz, to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga

munosib hissa qo’shgan.

Algoritmi:




min



5

8

15

29

32

7

18

20

25

8


15

29

32

7

18

20

25

5

5

8

15

29

32

7

18

20

25

5

5

7

8


15

29

32

7

18

20

25

5

5

7

8

15

29

32

7

18

20

25

5

5

7

8



8

15

29

32

7

18

20

25

5

5

7

8

15

8

15

29

32

7

18

20

25

5

5

7

8

15

18

8


15

29

32

7

18

20

25

5

5

7

8

15

18

20

8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

25

29


8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

25

8

15

29

32

7

18

20

25

5

5

7

8

15

18

20

25

29

32



L

R

m


Download 0.78 Mb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
O’zbekiston respublikasi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
nomidagi toshkent
guruh talabasi
davlat pedagogika
texnologiyalari universiteti
xorazmiy nomidagi
toshkent axborot
pedagogika instituti
rivojlantirish vazirligi
toshkent davlat
haqida tushuncha
Toshkent davlat
vazirligi toshkent
samarqand davlat
ta’limi vazirligi
tashkil etish
kommunikatsiyalarini rivojlantirish
matematika fakulteti
navoiy nomidagi
vazirligi muhammad
nomidagi samarqand
bilan ishlash
Darsning maqsadi
fanining predmeti
maxsus ta'lim
ta'lim vazirligi
Ўзбекистон республикаси
pedagogika universiteti
sinflar uchun
fanlar fakulteti
o’rta ta’lim
Toshkent axborot
Alisher navoiy
haqida umumiy
fizika matematika
Ishdan maqsad
moliya instituti
universiteti fizika
Nizomiy nomidagi
таълим вазирлиги
махсус таълим
respublikasi axborot
umumiy o’rta
pedagogika fakulteti
nazorat savollari