Saralash va izlash

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

int p1 = L, p2 = m+1;

• int p1 = L, p2 = m+1;
• int p = L;
• while (p1 <= m && p2 <= R) {
• if (a[p1] <= a[p2]) {
• b[p] = a[p1];
• p++;
• p1++;
• }
• else {
• b[p] = a[p2];
• p++;
• p2++;
• }
• }
• while (p1 <= m) {
• b[p] = a[p1];
• p++;
• p1++;
• }
• while (p2 <= R) {
• b[p] = a[p2];
• p++;
• p2++;
• }
• for (int i = L; i <= R; i++)
• a[i] = b[i];

#include

• #include
• #include
• #include
• using namespace std;
• int a[100000], b[100000];
• void mergesort(int L, int R) {
• if (L >= R)
• return;
• else {
• int m = (L+R) / 2;
• mergesort(L, m);
• mergesort(m+1, R);
• //Birlashtirish yoziladi
• }
• }
• int main() {
• int n;
• cin>>n;
• for (int i = 0; i < n; i++)
• cin>>a[i];
• mergesort(0, n-1);
• for (int i = 0; i < n; i++)
• cout<
• return 0;
• }

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?