🔍 Quick Sort Alqoritmi – İzah, Kod və Performans
Quick Sort effektiv və çox istifadə olunan sortlama alqoritmlərindən biridir. “Divide and Conquer” (Böl və idarə et) prinsipinə əsaslanır. Bu yazıda Quick Sort-un necə işlədiyini, C# kod nümunəsini və digər sort alqoritmlərlə müqayisəsini izah edəcəyik.
📌 Alqoritmin İş Prinsipi
- Pivot adlı element seçilir (məsələn, sonuncu element).
- Massiv pivotdan kiçik və böyük olan hissələrə bölünür.
- Hər iki hissəyə rekursiv olaraq Quick Sort tətbiq olunur
🧠 Big-O Analizi
| Hal | Təsvir | Vaxt Mürəkkəbliyi |
|---|
| Ən yaxşı hal | Pivot massivləri bərabər bölür | O(n log n) |
| Ortalama hal | Ümumi halda rast gəlinən | O(n log n) |
| Ən pis hal | Pivot ən kiçik və ya ən böyük elementdir (massiv sıralıdır) | O(n²) |
| Yaddaş istifadəsi | Rekursiyaya görə | O(log n) (stack) |
🔄 Quick Sort-un Digər Alqoritmlərlə Müqayisəsi
| Alqoritm | Ən Yaxşı Hal | Ən Pis Hal | Ortalama Hal | Yaddaş |
|---|
| Quick Sort | O(n log n) | O(n²) | O(n log n) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
💻 C# ilə Quick Sort Kodu və İzahı
using System;
namespace SortingQ
{
internal class Program
{
static void Main(string[] args)
{
int[] arr = { 90, 3, 45, 1, 89, 34, 58, 73, 4, 8 };
QuickSort(arr);
foreach (int i in arr)
{
Console.WriteLine(i);
}
}
// İki elementi dəyişmək üçün funksiya
static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Public interfeys
static void QuickSort(int[] arr)
{
QuickSort(arr, 0, arr.Length - 1);
}
// Əsas QuickSort funksiyası (rekursiv)
static void QuickSort(int[] arr, int low, int high)
{
if (low >= high)
return;
int pivotNewIndex = Partition(arr, low, high);
QuickSort(arr, low, pivotNewIndex - 1);
QuickSort(arr, pivotNewIndex + 1, high);
}
// Pivotu yerinə yerləşdirir və ayırma edir
static int Partition(int[] arr, int low, int high)
{
int pivot = arr[high]; // Pivot olaraq son elementi seçirik
int i = low;
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
Swap(arr, i, j);
i++;
}
}
Swap(arr, i, high); // Pivotu yerinə qoy
return i; // Pivotun yeni indeksi
}
}
}
✅ Üstünlüklər
- Çox sürətlidir – orta halda O(n log n)
- Yaddaş baxımından Merge Sort-a nisbətən qənaətlidir
- Sadə şəkildə implementasiya olunur
⚠️ Çatışmazlıqlar
- Ən pis halda O(n²) ola bilər (məsələn, sıralı massivlərdə)
- Stabil deyil (eyni dəyərə malik elementlərin sırası dəyişə bilər)
- Rekursiya çox dərinə getsə
StackOverflowException yarana bilər
📘 Nəticə
Quick Sort real tətbiqlərdə çox effektiv sortlama metodudur. Əgər pivot ağıllı seçilərsə (məsələn, median-of-three üsulu ilə), çox yüksək performans göstərir.
