Quick Sort

Quick sort algoritmi arraydagi tartibsiz elementlarni tartiblash uchun ishlatiladi.Uni bajarish uchun recursiya dan foydalaniladi.Uning bajaridigan ishlar soni B0(nlogn) ga teng bo'ladi agar pivet(birinchi tanlab olingan element) random tarzda tanlansa chunki u doim o'zgaradi va arrayning o'rtasidan va har xil joylaridan tekshiradi binery search kabi agar doim 0 elementni olsak 100 ta elementlik oldindan tartiblangan arrayni tartiblash uchun 100 * 100 marta ish bajaradi.Bu esa B0(n2) n kvadrat ga teng bo'lib qoladi.Masalan: O'zgarmas doim 0 elementni olishga misol ↙

let arr = [1,2,3,4,5,6,7,8,9,10]
function quickSort(nums){
if(nums.length <= 1){
    return nums
}
let pivet = nums[0]
let left = []
let right = []
for(let i = 1; i < nums.length; i++){
  if(nums[i] < pivet){
    left.push(nums[i]
  }else if(nums[i] > pivet){
    right.push(nums[i])
  }
  }
  return [...quickSort(left),pivet,...quickSort(right)]
}
//Bu function quyidagicha ishlaydi  bo'sh array left array va bu 9 martada 
[] [2, 3, 4, 5, 6,7, 8, 9, 10]
[] [3, 4, 5, 6,7, 8, 9, 10]
[] [4, 5, 6, 7,8, 9, 10]
[] [ 5, 6, 7, 8, 9, 10 ]
[] [ 6, 7, 8, 9, 10 ]
[] [ 7, 8, 9, 10 ]
[] [ 8, 9, 10 ]
[] [ 9, 10 ]
[] [ 10 ]
// [1,2,9,3,7,4,5,6,8] shunday ko'rinishdadi tartiblanmagan array berilsa
[] [ 2, 9, 3, 7, 4, 5, 6, 8 ]
[] [ 9, 3, 7, 4, 5, 6, 8 ]
[ 3, 7, 4, 5, 6, 8 ] []
[] [ 7, 4, 5, 6, 8 ]
[ 4, 5, 6 ] [ 8 ]
[] [ 5, 6 ]
[] [ 6 ]         //tartiblanmagan holatda 7 martada tartiblayapdi.

Agar pivet soni doim random ravishda olinadigan qilsak qanday ishlashini ko'ramiz

let arr = [1,2,3,4,5,6,7,8,9,10]
function quickSort(nums){
if(nums.length <= 1){
    return nums
}
let pivet = nums[Math.floor(Math.random() * nums.length)] // random olish
let left = []
let right = []
for(let i = 1; i < nums.length; i++){
  if(nums[i] < pivet){
    left.push(nums[i]
  }else if(nums[i] > pivet){
    right.push(nums[i])
  }
  }
  return [...quickSort(left),pivet,...quickSort(right)]
}
//Bu function quyidagicha ishlaydi va bu 3 martada tartibladi 
[ 2 ] [ 4, 5, 6, 7, 8, 9 ]
[ 5, 6, 7 ] [ 9 ]
[] [ 7 ]
// [1,2,9,3,7,4,5,6,8] shunday ko'rinishdadi tartiblanmagan array berilsa
[ 2, 3, 4 ] [ 9, 7, 6, 8 ]
[ 3 ] []
[ 7, 6 ] []
[] []       //tartiblanmagan holatda 4 martada tartiblayapdi.

Ko'rinib turganidek pivet raqamni random ravishda olish ancha unumdor usul.
Quick sort uchun leetcode dan bir misol ko'ramiz.

Misolni tushuntiraman bizga nums arrayi va k chi element indeksi beriladi biz nums ichidan k chi eng katta elementni olishimiz kerak.Masalan Example1: da k=2 va javob 5 bo'lishi kerak chunki 1 chi eng katta element 6 va 2 chi eng katta element 5 ga teng.Bizdan k =2 ni so'ragani uchun javob=5

var findKthLargest = function(nums, k) {    
 function quickSort(num) {        
 if (num.length <= 1) { 
 return num;
 }        
 let pivot = num[Math.floor(Math.random() * num.length)];        
 let left = [];        
 let right = [];        
 let middle = [];               
  for (let i = 0; i < num.length; i++) {            
   if (num[i] > pivot) {                
     left.push(num[i]);           
   } else if (num[i] < pivot) {               
     right.push(num[i]);            
   } else {           
     middle.push(num[i]);   
   }
  }           
  return [...quickSort(left), ...middle, ...quickSort(right)];    
 }
  return quickSort(nums)[k-1]
}
//bu masala shartida masalan 2 misolda nums = [3,2,3,1,2,4,5,5,6] bu array
// biz avval ko'rganimizdan farqli chunki unda bir xil elementlar mavjud 
// endi biz bir xil elementlarni ham bir arrayga joylashimiz kerak shuning 
// uchun middle o'zgaruvchisi ishlatildi agar uni ishlatmaganimizda 
// faqat pivot dan katta va kichik ligiga tekshirayotgan edik va bu hatolik

To'g'ri bu masalani oddiygini JS dagi tayyor sort methodi bilan ham yechsak bo'ladi atiga 2 qator code bo'ladi.Quick sortni bilmasimdan oldin shunday yechgan edim lekin endi quick sort bilan yechdim chunki masalaning pastki qismidagi topik larda quick sort bor edi.

JS dagi sort methodi qaysi sortlash algoritmidan foydalanishi,uning tezligi va qanday ishlashini bilishni hohlaysizmi?Unda commentga yozib qoldiring.