Reja: Saralash haqida tushuncha va algoritmlari
Download 0.68 Mb.
|
2-labaratoriya. Saralash
- Bu sahifa navigatsiya:
- Misol: include using namespace std; int main() { int n; cin>>n;
- [L, R] oraliq m=(L+R) / 2 o’rtasi orqali ikkita [L, m] va [m+1, R] oraliqqa ajratiladi va ular alohida saralanadi.
- Misol: include include include using namespace std;
- Misol: include using namespace std; int a[100001]; void qsort(int L, int R) {
- C++ dasturlash tilida saralash.
|
Reja: Saralash haqida tushuncha va algoritmlari Tanlash orqali saralash Pufakcha orqali saralsh (buble sort) Birlashtirish orqali saralsh Tezkor saralsh (quick sort) 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 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 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;'>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 
[L, R] oraliq m=(L+R) / 2 o’rtasi orqali ikkita [L, m] va [m+1, R] oraliqqa ajratiladi va ular alohida saralanadi. 
Misol: #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, informatika 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. 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. 10 5 9 3 7 6 1 12 3 17 2 L R m [L, R] saralanishi kerak bo’lgan oraliq. m = (L+R) / 2 – kesmanig o’rtasi. X=a[m] - bo’luvchi element. Chap tamondan X dan kichik katta yoki teng bo’lgan birinchi elementni topamiz. O’ng tamondan X dan katta bo’lmagan birinchi elementni topamiz. 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
Ikkalasining qiymatini almashtirzmiz. 10 5 9 10 7 6 1 12 3 17 2 i j 
3 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 
Misol: #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 n; cin>>n;
for (int i = 0; i < n; i++) cin>>a[i]; qsort(0, n-1);
cout< }
Agar bo’luvchi elementni o’rtadan emas, balki [L, R] kesmadan ixtiyoriy tanlab olinsa ishlash vaqti O(nlong(n)). 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);
cout< }
|
