|
Saralash va qidiruv algoritmlari ustida amallar
|
| bet | 3/4 | | Sana | 24.09.2024 | | Hajmi | 130,84 Kb. | | #272194 |
Bog'liq arslon kuurs ishi (2)Saralash va qidiruv algoritmlari ustida amallar
Saralash algoritmlari, massiv (array) elementlarini tartibga solish uchun ishlatiladi. Bu algoritmlar ma'lum bir tartibda joylashtirilgan massivni boshqa bir tartibda joylashtirish uchun foydalaniladi. Keling, eng mashhur saralash algoritmlariga va ularning qismlariga qaraymiz:
. Bubble Sort:
- Ishlash prinsipi: Elementlarni ikki ikki solishtirib, agar katta element quyidagi elementdan kichik bo'lsa, ularni almashtiradi.
- Misol: [5, 3, 8, 4, 2] massivini saralash:
1. [3, 5, 8, 4, 2]
2. [3, 5, 4, 8, 2]
3. [3, 5, 4, 2, 8]
4. [3, 4, 5, 2, 8]
5. [3, 4, 2, 5, 8]
6. [3, 2, 4, 5, 8]
7. [2, 3, 4, 5, 8]
Selection Sort:
- Ishlash prinsipi: Massivdan eng kichik elementni topib, uning joyini o'zlashtiradi. Keyin qoldiq massivni qarziga olishni takrorlaydi.
- Misol: [5, 3, 8, 4, 2] massivini saralash:
1. [2, 3, 8, 4, 5]
2. [2, 3, 8, 4, 5]
3. [2, 3, 4, 8, 5]
4. [2, 3, 4, 5, 8]
Insertion Sort:
- Ishlash prinsipi: Har bir elementni o'zidan oldingi tartiblangan qismga joylashtiradi.
- Misol: [5, 3, 8, 4, 2] massivini saralash:
1. [3, 5, 8, 4, 2]
2. [3, 5, 8, 4, 2]
3. [3, 4, 5, 8, 2]
4. [2, 3, 4, 5, 8]
Merge Sort:
- Ishlash prinsipi: Massivni bo'lib, har bir bo'lakni alohida saralab, keyin ularni birlashtiradi.
- Misol: [5, 3, 8, 4, 2] massivini saralash:
- Step 1: [3, 5], [4, 8], [2]
- Step 2: [3, 5], [4, 8], [2]
- Step 3: [3, 4, 5, 8], [2]
- Step 4: [2, 3, 4, 5, 8]
Quick Sort:
- Ishlash prinsipi: Pivot element tanlab, kichik va katta elementlarni uning atrofida joylashtiradi, so'ng bo'laklarni rekursiv ravishda saralaydi.
- Misol: [5, 3, 8, 4, 2] massivini saralash:
- Step 1: [3, 4, 2], [5], [8]
- Step 2: [2], [3, 4], [5], [8]
- Step 3: [2], [3], [4], [5], [8]
Har bir algoritmda tartiblashning murakkablik darajasi va faqat tartiblangan massivlar uchun qo'llanish mumkinligi bor. Farqi bu yuqoridagi misollarda ko'rsatilgan.
Qidiruv algoritmlari, massiv (array) yoki qatorning ichida kerakli elementni topish uchun ishlatiladi. Bu algoritmlar massivni o'zida tartiblangan yoki tartiblanmagan bo'lishiga qarab turli usullarda ishlaydi. Keling, eng mashhur qidiruv algoritmlariga va ularning qismlariga qaraymiz:
Linear Search:
- Ishlash prinsipi: Massivni boshidan oxirigacha yoki oxiridan boshigacha tekshiradi va qidirilayotgan elementni topish.
- Misol: [5, 3, 8, 4, 2] massivida 4 elementini qidirish:
- 5 != 4
- 3 != 4
- 8 != 4
- 4 == 4 (Topildi)
Binary Search:
- Ishlash prinsipi: Tartiblangan massivda o'rta elementni tanlab, kerakli element o'rtadan kichikmi yoki kattaligiga qarab, qidiruv doirasini ikki qismga bo'ladi.
- Massiv: [2, 3, 4, 5, 8]
- Misol: [2, 3, 4, 5, 8] massivida 4 elementini qidirish:
- O'rta element: 4
- 4 == 4 (Topildi)
Qidiruv algoritmlari mos massiv turi va qidirilayotgan elementni topish kerakli.
Masalan, tartiblangan massivlarda Binary Search, tartiblanmagan massivlarda esa Linear Search afzaldir. Har bir algoritmning murakkablik darajasi va ishlatish shartlari mavjud.
Endi saralash vaqidiruv algoritmlari yordamida bir necha misollar ko’rib chiqamiz:
Aytib o'tishimiz kerakki, masalalarni yechish uchun xususiy model yoki algoritm mavjud bo'lishi kerak, chunki har bir masala turli muammolar yoki talablar bo'lishi mumkin.
Ammo quyidagi kichik misollar sizga masallarni yechishda yordam berishi mumkin:
Misol Chiziqli Tartiblash (Bubble Sort)
Masala: Berilgan massivni chiziqli tartibda saralash.
Algoritm:
1. Massivni o'ngdan chapga tashqari yurishni boshlang.
2. Har bir elementni o'ngdagi element bilan solishtirib, agar o'ngdagi element kichik bo'lsa, ularni almashtirish.
3. Har bir yurishdan so'ng, eng katta element to'g'ri o'ng tomona joylashadi.
4. Yuqoridagi jarayonni to'g'ri to'xtatishdan so'ng, yurishni keyingi elementga o'rnating.
#include
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// Elementlarni almashtirish
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Bir misol uchun qidiruv algoritmi sifatida chiziqli tartiblash (binary search) algoritmini ko'rsatamiz:
Masala: Berilgan massivda berilgan elementni topish.
Algoritm:
1. Massiv boshlang'ich va oxirgi indekslarini aniqlang.
2. Massivni boshlanishi va oxirgi indekslari o'rtasidagi o'rtacha elementni aniqlang.
3. Agar o'rtacha element berilgan elementga teng bo'lsa, topildi deb qaytaring.
4. Agar berilgan element o'rtacha elementdan katta bo'lsa, qidiruvni o'rtacha elementdan keyinroq boshlanishi bilan takrorlang.
5. Agar berilgan element o'rtacha elementdan kichik bo'lsa, qidiruvni o'rtacha elementdan avvalgi boshlanishi bilan takrorlang.
6. Massiv boshlanishi va oxirgi indekslari bir-biriga teng bo'lishi yoki boshlanish indeksi oxirgi indeksdan katta bo'lishi yoki oxirgi indeks boshlanish indeksdan katta bo'lishi tugaganida, element topilmagan deb hisoblang.
Izoh:
Bu kodda, berilgan massivda berilgan elementni qidiruvini o'rganamiz. Qidiruv algoritmi massivni yaroqlilikda chiziqli tartibda saqlab turadi. Agar berilgan element massivda topilsa, uning indeksini qaytaradi; aks holda, "Element topilmadi" deb xabar chiqariladi.
#include
using namespace std;
int binarySearch(int arr[], int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
return mid; }
if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1; }
}
return -1; // Agar element topilmagan bo'lsa
}int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
if (result == -1) {
cout << "Element topilmadi";
} else {
cout << "Element " << x << " indeksda: " << result;
}
return 0;
}
|
| |
