Saralash va izlash

Saralash va qidiruv.

Guruh 219- 21

Bajardi:Ishdavlatov Farrux

Nima uchun kerak?

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

Saralash

• a[0], a[1], a[2] .. a[n-1] massiv elementlari berilgan.
• Ularni shunday joylashtirish kerakki, ular kamaymaslik tartibida bo’lib qolsin.

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.

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

Algoritmlarda log(n) bu .

n= bo’lganda taqqoslang:

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

•  

Tanlash orqali saralash

• 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);

• #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

• #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 ma-

tematika, kvant fizikasi, funksional

analiz, to’plamlar nazariyasi, eko-

nomika, informatika kabi fanlarga munosib hissa qo’shgan.

Bo’lib tashla va hukmronlik qil metodi.

• Algoritmlarni qurishning asosiy metodlaridan biri.
• Murakkab masalani yechish uchun, uni oddiyroq bo’laklarga ajratish kerak.
• Massivni ham huddi shunday saralash mumkin:
• Uni ikkita bo’lakga ajratamiz.
• Bo’laklarni alohida saralaymiz.
• Saralangan massivlarni birlashtiramiz.

Saralangan massivlarni birlashtirish.

• Ikkita saralangan massiv berilgan. Ularni birlashtirib shunday massiv hosil qilish qilish kerakki, u yana saralangan bo’lsin.
• Xar safar hali ikki massivning hali ko’rilmagan qismlaridagi birinchi ikki elementni taqqoslaymiz. Ulardan kichigini olamiz.

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

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] oraliq m=(L+R) / 2 o’rtasi orqali ikkita [L, m] va [m+1, R] oraliqqa ajratiladi va ular alohida saralanadi.

L
R
m

10 – variant :"Mersedes" markasidagi mashinalarni raqamlari bo‘yicha kamayish tartibida joylashtiring.

• 10 – variant :"Mersedes" markasidagi mashinalarni raqamlari bo‘yicha kamayish tartibida joylashtiring.

Dastur natijasi

Tezkor saralash(Quick Sort) algoritmi.

• 1964 yilda Charlz Hoar tamonidan taklif qilingan.

Charlz Hoar ingliz olimi, infor-

matika va hisoblash texnikasi

sohasida yetuk mutaxassis.

Uning “Tezkor saralash” algorit-

mi saralash bo’yicha eng ommobop algoritm.

Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.

• Bu algoritm ham “Bo’lib tashla va hukmronlik qil” metodiga asoslanadi.
• Algoritmning g’oyasi:
• Massivda bo’luvchi element X tanlanadi.
• Elementlarni shunday joylashtiramizki, dastlab X dan kichik yoki teng bo’lgan elementlar joylashsin, keyin undan katta bo’lgan elementlar joylashsin.
• Keyin ularni alohida saralaymiz.

• [L, R] saralanishi kerak bo’lgan oraliq.
• m = (L+R) / 2 – kesmanig o’rtasi.
• X=a[m] - bo’luvchi element.

10
5
9
3
7
6
1
12
3
17
2
L
R
m

• Chap tamondan X dan kichik katta yoki teng bo’lgan birinchi elementni topamiz.
• O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz.
• Ikkalasining qiymatini almashtirzmiz.

10
5
9
10
7
6
1
12
3
17
2
i
j
3
5
9
10
7
6
1
12
10
17
2
i
j
3
5
9
10
7
6
1
12
10
17
2
i
j
3
5
2
10
7
6
1
12
10
17
9
i
j
3
5
2
10
7
6
1
12
10
17
9
i
j
3
5
2
1
7
6
10
12
10
17
9
i
j
3
5
2
1
7
6
10
12
10
17
9
i
j
3
5
2
1
6
7
10
12
10
17
9
i
j
3
5
2
1
6
7
10
12
10
17
9
j
i
3
5
2
1
6
7
10
12
10
17
9
j
i
L
R

#include

• #include
• using namespace std;
• int a[100001];
• void qsort(int L, int R) {
• int m = (L+R) / 2;
• int X = a[m];
• int i = L;
• int j = R;
• while (i <= j) {
• while (a[i] < X) i++;
• while (a[j] > X) j--;
• if (i <= j) {
• int t = a[i]; a[i] = a[j]; a[j] = t;
• i++;
• j--;
• }
• }
• if (L < j) qsort(L, j);
• if (i < R) qsort(i, R);
• }

• int main() {
• int n;
• cin>>n;
• for (int i = 0; i < n; i++)
• cin>>a[i];
• qsort(0, n-1);
• for (int i = 0; i < n; i++)
• cout<
• return 0;
• }

• Agar bo’luvchi elementni o’rtadan emas, balki [L, R] kesmadan ixtiyoriy tanlab olinsa ishlash vaqti O(nlong(n)).

C++ dasturlash tilida saralash.

• C++ da saralash juda oddiy Quick Sort bo’yicha saralaydi:
• #include
• #include
• using namespace std;
• int main() {
• int n;
• cin>>n;
• int a[n];
• for (int i = 0; i < n; i++)
• cin>>a[i];
• sort(a, a+n);
• for (int i = 0; i < n; i++)
• cout<
• return 0;
• }

Masalalar

• 172.20.27.98 dan:
• 1. “Saralash”. Tanlash va Pufakcha usulida saralash algoritmlarini qo’llab ko’rish uchun.
• 2. “Saralash-2”. Merge va Quick sort algoritmlarini qo’llab ko’rish uchun.

• E’tiboringiz uchun raxmat.
• Savollar?