Ma'lumotlarni saralash algoritmlari. Tad kafedrasi

1- o’tish:

4

1

5

2

3

1-Misol:

1

4

5

2

3

1

4

5

2

3

1

4

2

5

3

2-o’tish :
3- o’tish :

1

2

4

5

3

1

2

3

4

5

1

2

4

5

3

4- o’tish :

1

2

3

4

5

1

2

3

4

5

1

2

4

3

5

N elementdan iborat massivni saralash uchun N-1 ta o’tish kerak (N-1 ta elementlarni o’z o’rniga qo’yish kerak).
!
2-Misol:
Masalan, bizda butun sonlar massivi mavjud:
Massivdan birinchi o'tishda biz 3 va 7 qiymatlarini taqqoslaymiz. 7 raqami 3 dan katta bo'lgani uchun biz ularni o'z holicha qoldiramiz. Keyin biz 7 va 4 ni solishtiramiz. 4 raqami 7 dan kichik, shuning uchun biz ularni almashtiramiz, 7 ni bir pozitsiyaga massiv oxiriga yaqinlashtiramiz. Endi u shunday ko'rinadi:
3-Misol:
Bu jarayon yetti raqami massivning deyarli oxiriga yetguncha takrorlanadi. Oxirida u 8-element bilan taqqoslanadi, bu kattaroqdir, ya'ni almashinuv yo'q. Massivni bir marta qarab chiqqanimizdan so'ng, u quyidagicha ko'rinadi:
Hech bo'lmaganda bitta qiymat almashinuvi sodir bo'lganligi sababli, biz massivni yana bir marta takroran ko’rib chiqishimiz kerak. Ushbu o'tish natijasida biz 6 raqamini joyiga o'tkazamiz.
Keyingi o’tishda almashish sodir bo’lmaydi, demak, massiv saralangan holga kelganligi uchun algoritm o’z ishini yakunlaydi.
Va yana kamida bitta almashinuv amalga oshirildi, ya'ni biz yana massivni ko’rib chiqamiz.
#include
using namespace std;
int main()
{ setlocale(LC_ALL, "Rus");
int n; // elementlar soni
cout << “ Elementlar soni: ";
cin >> n;
/* Massiv o’lchamini aniqlaymiz */
int mass[n];
for(int i = 0; i < n; ++i)
{ cout << i+1 << "-nchi element: ";
cin >> mass[i];
}
cout << " Berilgan massiv: ";
for(int i = 0; i < n; ++i)
{ cout << mass[i] << " ";
}
cout << endl;
/* Kamayish bo’yicha saralaymiz */
for(int i = 1; i < n; ++i)
{ for(int r = 0; r < n-i; r++)
{if(mass[r] < mass[r+1])
{ // Joyini almashtirish
int temp = mass[r];
mass[r] = mass[r+1];
mass[r+1] = temp;
}
}
}
/* Saralangan massiv */
cout << " Saralangan massiv : ";
for(int i = 0; i < n; ++i)
{ cout << mass[i] << " ";
}
cout << endl;
return 0;
}
Agar biz nafaqat maksimum qiymatga ega elementlarni oxiridan joylashtirib kelsak, balki minimum qiymatga ega bo’lgan elementlarni ham massivning boshlang’ich tomonidan joylashtirib kelsak, unda biz SHEYKER saralash algoritmiga ega bo’lamiz.
Jarayon “pufaksimon saralash" da bo'lgani kabi boshlanadi: Massiv oxiriga maksimal qiymatga ega bo’lgan elementni surib boramiz. Shundan so'ng, biz 180 gradus atrofida aylanamiz va teskari yo'nalishda boramiz, shu bilan birga massivning boshlang’ich qismiga maksimal emas, balki minimal elementni joylashtiramiz. Massivdagi birinchi va oxirgi elementlarni saralab, biz yana jarayonni takrorlaymiz. Massivda bir necha marta oldinga va orqaga qarab yurib, oxirida biz jarayonni yakunlaymiz, bu holda ro'yxatning o'rtasida bo'lamiz.
SHEYKER saralash algoritmi
(aralash saralash yoki kokteyl saralash)
Sheyker saralash pufakchali saralashdan biroz tezroq ishlaydi, chunki maksimum va minimum elementlar navbatma-navbat massiv bo‘ylab kerakli yo‘nalishda o‘tadi.
http://kompy.info