8-Mavzu: Birlashtirib saralash algoritmlari. Samarali saralash algoritmlari. Birlashtirib saralashni rekursiv va rekursiv bo'lmagan algoritmlari

Download 42,15 Kb.
bet	4/4
Sana	30.05.2024
Hajmi	42,15 Kb.
	#257330

1 2 3 4

Bog'liq
8-Mavzu

Mavzu yuzasidan savollar

j = 1 : arr[j] > pivot, bajarilsa, hech nima oʻzgarmaydi
// i va arr [] da oʻzgarish yoʻq
j = 2 : arr[j] <= pivot, shart bajarilsa i++ va swap(arr[i], arr[j])

i = 1

arr[] = {10, 30, 80, 90, 40, 50, 70} // 80 va 30 almashdi
j = 3 : arr[j] > pivot, shart bajarilsa, hech nima oʻzgarmaydi
// No change in i and arr[]
j = 4 : arr[j] <= pivot, shart bajarilsa i++ va swap(arr[i], arr[j])

i = 2

arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 va 40 almashadi
j = 5 : arr[j] <= pivot, shart bajarilsa i++ va swap(arr[i], arr[j])

i = 3

arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 va 50 almashadi

Soʻnggi natija

arr[i+1] va arr[high]

arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 va 70 almashtiriladi

―Tayanch element‖ hisoblanuvchi 70 ham oʻz oʻrnida. Undan kichik elementdan boshida, kattalari esa undan tepada

Quick sort algoritmning umumiy dasturi (C++)

#include using namespace std;
// Ikki elementni almashtirish uchun yordamchi funksiya void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/*Ushbu funksiya
soʻnggi elementni “tayanch” sifatida qabul qiladi,
“tayanch” elementni tartiblangan qatorga toʻgʻri holatiga qoʻyadi va kichikroq (burilishdan kichikroq) burilishning chap tomoniga
va barcha katta elementlarni “tayanch element” ning oʻng tomoniga joylashtiradi
*/
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // tayanch element
int i = (low - 1); // Kichikroq element koʻrsatkichi va tayanch
//toʻgʻri holatini koʻrsatadi

for (int j = low; j <= high - 1; j++)
{
//Agar joriy element tayanchdan kichik boʻlsa if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); return (i + 1);
}
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);
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " "; cout << endl;
}
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1);
cout << "Saralangan massiv: \n"; printArray(arr, n);
return 0;
}

QuickSort algoritmi tahlili. Massivni „tayanch― elementiga nisbatan ikki qismga boʻlish jarayoni O(log₂n) vaqtni oladi. Bir xil rekursiya darajasi bajariladigan barcha boʻlinish amallari hajmi doimiy boʻlgan boshlangʻich massivning turli qismlarini qayta ishlagani uchun, har bir rekursiya darajasida jami O (n) amallar ham talab qilinadi. Shuning uchun algoritmning umumiy murakkabligi faqat boʻlinishlar soni, ya‘ni rekursiya darajasi bilan belgilanadi. Rekursiyaning darajsi,
oʻz navbatida, kirishlarning kombinatsiyasiga va ―tayanch element‖ qanday aniqlanishiga bogʻliq.
Eng yaxshi holat. Eng yaxshi holatda har bir boʻlinish paytida massiv ikkita bir xil (+/- bitta element) qismlarga boʻlinadi, shuning uchun qayta ishlangan ichki massivlarning oʻlchamlari 1 ga yetadigan maksimal rekursiya darajasi log₂n boʻladi. Natijada, quicksort tomonidan taqqoslash soni O(nlog₂(n)) algoritmining umumiy murakkabligini beradigan 𝐶_𝑛 = 2𝐶_𝑛/2 + 𝑛 rekursiv ifodasining qiymatiga teng boʻladi.
Oʻrtacha holat. Kirish ma‘lumotlarini tasodifiy taqsimlash uchun oʻrtacha murakkablik faqat ehtimollik bilan baholanishi mumkin.
Avvalo shuni ta‘kidlash kerakki, aslida, ―tayanch‖ elementi har safar massivni ikkita teng qismga ajratishi shart emas. Masalan, agar har bir bosqichda dastlabki massivning 75% va 25% uzunlikdagi
massivlarga boʻlinish boʻlsa, rekursiya darajasi 𝑙𝑜𝑔⁴𝑛 ga teng boʻladi va
O (nlogn) murakkablikni beradi. Umuman olganda, ―tayanch‖ elementning chap va oʻng tomonlari orasidagi har qanday aniq nisbatlar uchun algoritmning murakkabligi bir xil boʻladi, faqat har xil konstantalar mavjud.
Yomon holat. Eng yomon holatda har bir ―tayanch‖ 1 va n-1 oʻlchamdagi ikkita kichik massivni beradi, ya‘ni har bir rekursiv chaqiriq uchun kattaroq massiv oldingi vaqtga nisbatan 1 ta qisqa boʻladi. Agar har bir ishlov berilgan elementlarning eng kichigi yoki eng kattasi mos yozuvlar sifatida tanlansa, bu sodir boʻlishi mumkin.
Bunday holda, n-1 ―boʻlinish‖ amallar talab qilinadi va umumiy
ishlash muddati ^∑𝑛⁽𝑛 − 1⁾= 𝑂⁽𝑛²⁾ta operatsiyani tashkil qiladi,
𝑖=0
ya‘ni saralash kvadratik vaqt ichida amalga oshiriladi. Ammo
almashtirishlar soni va shunga koʻra ish vaqti uning eng katta kamchiligi emas. Bundan ham yomoni, bu holda algoritmni bajarish paytida rekursiya darajasi n ga yetadi.

Mavzu yuzasidan savollar:

Saralash algoritmlari va ularning tahlili haqida gapiring
Eng sodda algoritmlar va ularning murakkabligi
QuickSort va Merge Sort algoritmlarining biri-biridan farqli jihatlari.
Eng sodda algoritmlarning eng yaxshi va eng yomon holatdagi ishlash vaqtlarini tahlil qilish
Quick Sort algoritmining eng yaxshi va eng yomon holatdagi bahosini tahlil qiling.

Download 42,15 Kb.

1 2 3 4

Download 42,15 Kb.