4 -mustaqil ta’lim ish hisoboti Fan“ Algoritmlarni loyihalash” Guruh ki21-02 Topshirdi: Zarpullayev. U tekshirdi: Bobonazarov. A samarqand-2023
Download 111.6 Kb.
|
algoritm 4 mt — копия
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. Download 111.6 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling