4 -mustaqil ta’lim ish hisoboti Fan“ Algoritmlarni loyihalash” Guruh ki21-02 Topshirdi: Zarpullayev. U tekshirdi: Bobonazarov. A samarqand-2023

1-amaliy mashg’ulot topshiriqlari.
Belgilardan iborat massiv berilgan. Massivni Quick sort algoritmi bo’yicha saralang
Berilgan belgilar massivi tuzilsin va Quick sort algoritmi yordamida saralansin.
Masalan:
input: {8, 3, 1, 5, 7, 6, 2, 4}
output: {1, 2, 3, 4, 5, 6, 7, 8}
C++ tilida yechimi:
#include
using namespace std;
void quickSort(int[], int, int);
int partition(int[], int, int);
int main()
{
int arr[] = { 8, 3, 1, 5, 7, 6, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Saralgan massiv: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int partition(int arr[], int low, int high)

{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(arr[i], arr[j]); // swap values
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
Chiquvchi algoritmda, massiv qiymatlarini ixtiyoriga ko'ra o'rganadi va osongina uning minimum yoki maksimum qiymatlarini diapason chiqaradi. Quyidagi harakatlar ishlatiladi:
- Massivning tugashi va oxiri aniqlanadi
- Massiv oxiridagi element pivot qilib tanlanadi
- Massivda pivot qiymatdan kichik elementlar qavati va undan katta elementlar qavati aniqlanadi
- Pivot qiymatiga qarab elementlar o'zaro almashtiriladi
- Pivot qiymat o'rtasidagi indeks topiladi va massiv esa ixtiyoriga nazaran chap va o'ng to'rtliklarga bo'linadi.
- Har bir to'rtlikda, yuqoridagi usullar bajariladi, to'g'ri bo'lsa ham bajarilmasa, massivni o'sha bo'limdagi qat'iy hisob bo'yicha taxlamaydi.
- Oyna rekursiv tarzda massivni soraladi
Yuqoridagi keldi-funksiya algoritmi va partition-funksiya indexlari bilan bir-biridan ajralib turadi. quickSort () funksiyasi massivni saralash uchun umumiy sukunatli shaklda joylashgan. partition () funksiyasi esa massivni ikkiga bo'lib partiya qiladi. Keyingi chora-tadbirlarni olib, massivni umumiy formulaga keltirib, sorted qaytaradi.