Quick Sort alqoritmi

[codex]

Quick Sort — sürətli, yerində (in-place) və müqayisəyə əsaslanan sıralama alqoritmidir. Bu alqoritm “pivot” adlanan bir element seçir və digər elementləri bu pivotdan kiçik və ya böyük olmalarına görə iki alt massivə ayırır. Daha sonra bu alt massivlər rekursiv şəkildə sıralanır. Quick Sort-un orta və ən yaxşı halda zaman mürəkkəbliyi O(n log n) olsa da, ən pis halda bu O(n²)-ə qədər arta bilər. Bununla belə, böyük verilənlər üzərində effektiv işlədiyinə görə çox istifadə olunur.

---

İmplementasiya

Pivot (partition) yardımçı funksiyası

1. Üç parametr qəbul edən bir funksiya yaradın: array, start indeksi və end indeksi (bunlar susmaya görə 0 və array.length - 1 ola bilər);
2. Elementləri dəyişmək üçün ayrıca bir köməkçi funksiya (swap) yaradın;
3. Pivotu seçin (məsələn, arr[start] dəyəri);
4. Hal-hazırkı pivot indeksini ayrıca bir dəyişəndə saxlayın;
5. start + 1-dən end-ə qədər dövr edin:
   • Əgər cari element pivotdan kiçikdirsə, pivot indeksini bir vahid artırın və cari elementi həmin yeni pivot indeksindəki elementlə dəyişdirin;
6. Pivotu yerləşdiyi start indeksindən, pivot indeksinə dəyişin;
7. Pivot indeksini qaytarın;

Həll:

const pivot = (arr, start = 0, end = arr.length - 1) => {
  const swap = (arr, idx1, idx2) => 
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

  let pivot = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) swap(arr, ++swapIdx, i);
  }

  swap(arr, start, swapIdx);
  
  return swapIdx;
}

---

Quick Sort alqoritminin özü

1. Üç parametr qəbul edən əsas funksiya yaradın: massiv, left (susmaya görə 0) və right (array.length - 1);
2. Əgər left < right şərti doğrudursa:
   • Pivot funksiyasını çağırın və massivlə birlikdə left, right dəyərlərini ötürün;
   • Pivot funksiyası sizə yeni pivot indeksini qaytardıqdan sonra, rekursiv şəkildə:
     • Pivotun solundakı altmassiv üçün quickSort(arr, left, pivotIndex - 1)
     • Pivotun sağındakı altmassiv üçün quickSort(arr, pivotIndex + 1, right) çağırın;
3. Əks halda sadəcə massiv qaytarılır;

Həll:

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    const pivotIndex = pivot(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }

  return arr;
}

---

Nəticə

Quick Sort yüksək performans və minimal yaddaş istifadəsi ilə tanınır. Əgər düzgün seçilmiş pivot istifadə edilərsə, böyük verilənlər üçün olduqca effektiv olur. Lakin ən pis ssenaridə O(n²) mürəkkəbliyə malik olduğu üçün bəzən alternativ alqoritmlərlə müqayisə etmək lazımdır.

---

Quick Sort-u vizual olaraq görmək üçün Macar (Küküllőmenti legényes) xalq rəqsinə tamaşa etməniz kifayət edəcək