Toshkent Axborot Texnologiyalar Universiteti Axborot xavfsizligi fakulteti715-20 guruh talabasi Ismoilov Feruzning ma’lumotlar tuzilmasi va algoritmlari fanidan bajargan mustaqil ishi Kriptalogiya kafedrasi Toshkent 2022 Mavzu

Rekursiv QuickSort funksiyasi uchun psevdokod: 
 
/* past --> Boshlang'ich indeks, yuqori --> Yakuniy indeks */
QuickSort(arr[], past, yuqori)
{
agar (past < yuqori)
{
/* pi bo'lish indeksi, arr[pi] hozir
to'g'ri joyda */
pi = bo'lim (arr, past, baland);

QuickSort(arr, past, pi - 1); // pidan oldin
QuickSort(arr, pi + 1, baland); // pi dan keyin
}
}

QuickSort tomonidan olingan QuickSort vaqtini tahlil qilish 
, umuman olganda, quyidagicha yozilishi mumkin. 
 
T(n) = T(k) + T(nk-1) + (n)
 
Birinchi ikki shart ikkita rekursiv qo'ng'iroqlar uchun, oxirgi atama bo'lish jarayoni uchun. k - pivotdan kichikroq elementlar soni. 
QuickSort tomonidan qabul qilingan vaqt kiritish massivi va bo'lim strategiyasiga bog'liq. Quyida uchta holat keltirilgan.
 
Eng yomon holat: bo'lish jarayoni har doim eng katta yoki eng kichik elementni pivot sifatida tanlaganda eng yomon holat yuzaga keladi. Agar oxirgi element har doim pivot sifatida tanlanadigan yuqoridagi bo'lim strategiyasini ko'rib chiqsak, eng yomon holat massiv o'sish yoki kamayish tartibida tartiblangan bo'lsa sodir bo'ladi. Quyida eng yomon holat uchun takrorlanish mavjud. 
 
T(n) = T(0) + T(n-1) + (n) ga teng

T(n) = T(n-1) + (n)
 
Yuqoridagi takrorlanishning yechimi (n ² ).
 
Eng yaxshi holat: eng yaxshi holat bo'lish jarayoni har doim o'rta elementni pivot sifatida tanlaganida sodir bo'ladi. Quyida eng yaxshi holat uchun takrorlanish keltirilgan. 
 
T(n) = 2T(n/2) + (n)
 
Yuqoridagi takrorlanishning yechimi (nLogn). Buni asosiy teoremaning 2-holati yordamida hal qilish mumkin .
 
O'rtacha holat: 
O'rtacha vaziyatni tahlil qilish uchun biz massivning barcha mumkin bo'lgan almashtirishlarini hisobga olishimiz va oson ko'rinmaydigan har bir almashtirish vaqtini hisoblashimiz kerak . 
Bo'lim O(n/9) elementlarni bir to'plamga va O(9n/10) elementlarni boshqa to'plamga qo'yish hollarini ko'rib chiqib, o'rtacha holat haqida tasavvurga ega bo'lishimiz mumkin. Quyida ushbu holat uchun takrorlanish mavjud. 
 
T(n) = T(n/9) + T(9n/10) + (n)
 
Yuqoridagi takrorlanishning yechimi ham O(nLogn)
Garchi QuickSort-ning eng yomon vaqt murakkabligi O(n ^{2 ) boʻlsa-da, bu} Birlashtirish Saralash va Uyma Saralash kabi koʻplab boshqa saralash algoritmlaridan koʻra koʻproq boʻlsa -da, QuickSort amalda tezroq, chunki uning ichki aylanishi mumkin. ko'pgina arxitekturalarda va real dunyo ma'lumotlarida samarali qo'llanilishi mumkin. QuickSort turli yo'llar bilan pivot tanlovini o'zgartirish orqali amalga oshirilishi mumkin, shuning uchun ma'lum bir turdagi ma'lumotlar uchun eng yomon holat kamdan-kam uchraydi. Biroq, ma'lumotlar katta bo'lsa va tashqi xotirada saqlangan bo'lsa, birlashma tartibi odatda yaxshiroq hisoblanadi.