Referati toshkent 2023 saralash algoritmlari mohiyati va ularning samaradorligini baholash. Reja

Toʻrtinchi oʻtish
Endi tartiblangan kichik massivda mavjud boʻlgan elementlar 5, 11 va 12 Keyingi ikkita elementga oʻtish: 13 va 6

Shubhasiz, ular tartiblanmagan, shuning uchun ikkalasini almashtirishni amalga oshiring

Endi 6 12 dan kichik, shuning uchun yana almashtiring

Almashtirish 11 va 6 ni tartiblamaydi, shuning uchun yana almashtiring

Nihoyat, massiv toʻliq tartiblangan.
Dasturi:

#include using namespace std; void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = { 12, 11, 13, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, N); printArray(arr, N); return 0; }

Quick sort (Tezkor saralash)
Quick sort yigirmanchi asrning eng muhim algoritmlaridan bo‘lib, u ko‘p dasturlarda ishlatiladi. Mergesort kabi, Quicksort ham rekursiv algoritm, lekin Quicksort’ning Mergesort’dan farqi – rekursiya ish tugallangach ishga tushadi (Mergesort’da avval rekursiya, keyin ish boshlanardi) (5-rasm).

5-rasm. Quick sort

Quicksort ishlash tartibi

Shuffle. Quicksortda tartiblashni boshlashdan avval array aralashtirib olinadi.
Partition. Keyin array ikkiga ajratiladi. Bunda ajratuvchi elementning (pivot) chap tarafida elementdan kichik qiymatlar, o‘ng tarafida elementdan katta qiymatlar o‘rin olishi kerak.
Sort. So‘nggi bosqichda ikki qism tartiblanadi.