Algoritma ve Programlama Dünyası — Uygulama 6 (Quick Sort)
Merhaba sevgili okurlar! Algoritma ve programlama dünyası serisinin bir önceki bölümünde, ‘Bubble Sort’ adlı bir sıralama algoritması üzerine durmuştuk. Eğer önceki yazıyı okumadıysanız, bu linke tıklayarak ulaşabilirsiniz. Bu bölümde ise, hızlı sıralama anlamına gelen ve genellikle büyük veri setlerinin sıralanmasında kullanılan “Quick Sort” algoritmasını inceleyeceğiz.
Quick Sort Nedir?
Quick Sort, bir sıralama algoritmasıdır. İsmini, verileri hızlı bir şekilde sıralama özelliğinden alır. Tony Hoare tarafından 1959 yılında geliştirilen Quick Sort, böl ve yönet algoritma yaklaşımını kullanır. Bu yaklaşımda, büyük problemler küçük alt problemlere ayrılır ve bu alt problemler çözülerek ana problem çözülür.
Quick Sort Algoritmasının Mantığı
Quick Sort algoritmasının temel mantığı “pivot” elementini kullanarak veri setini ikiye bölmedir. Genellikle veri setindeki ilk, orta ya da son eleman pivot olarak seçilebilir. Pivot seçildikten sonra, algoritma pivotun solundaki tüm elemanları pivotun değerinden küçük, pivotun sağındaki tüm elemanları ise pivotun değerinden büyük olacak şekilde düzenler. Bu işlem sonucunda pivot elemanın doğru konumda olduğunu biliriz. Sonra aynı işlem pivotun solundaki ve sağındaki elemanlar için tekrarlanır. Bu işlem, tüm liste sıralanana kadar devam eder. Uygulamanın pseudocode aşağıdaki gibidir:
procedure quickSort(A : list of sortable items)
if length(A) <= 1
return A
select and remove a pivot value 'p' from 'A'
create empty lists 'less' and 'greater'
for each x in 'A'
if x <= p then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quickSort(less), 'p', quickSort(greater))Python’da Quick Sort Uygulaması
Python dilinde Quick Sort algoritmasının uygulaması aşağıdaki gibidir:
def partition(arr, low, high):
i = (low-1)
pivot = arr[high]
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)
def quick_sort(arr, low, high):
if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)Bu kodda, partition fonksiyonu bir pivot belirler ve pivotun etrafında liste ayırır. quick_sort fonksiyonu ise bu işlemi tekrarlar ve liste sıralanana kadar devam eder.
Bir örnek ile test edelim:
# Testimiz için bir dizi oluşturalım
arr = [10, 7, 8, 9, 1, 5]
# Dizinin sıralanmamış hali
print("Dizinin Sıralanmamış Hali:")
print(arr)
# Quick Sort'u çağırıyoruz
quick_sort(arr, 0, len(arr)-1)
# Dizinin sıralanmış hali
print("Dizinin Quick Sort ile Sıralanmış Hali:")
print(arr)Bu kod çalıştırıldığında, çıktısı aşağıdaki gibi olacaktır:
Dizinin Sıralanmamış Hali:
[10, 7, 8, 9, 1, 5]
Dizinin Quick Sort ile Sıralanmış Hali:
[1, 5, 7, 8, 9, 10]Algoritmanın Görsel Örneği
Quick Sort algoritmasının daha iyi anlaşılabilmesi için, [8, 4, 7, 6, 2, 3] dizisinin sıralamasını görsel olarak adım adım inceleyelim. Bu örnekte pivotu her zaman dizinin son elemanı olarak seçeceğiz.
İlk adım: [8, 4, 7, 6, 2 | 3]
İkinci adım: [2 | 3 | 8, 4, 7, 6]
Üçüncü adım: [2, 3 | 8, 4, 7 | 6]
Dördüncü adım: [2, 3 | 6, 4 | 7 | 8]
Beşinci adım: [2, 3 | 4 | 6, 7, 8]Algoritmanın Zaman ve Hafıza Karmaşıklığı
Quick Sort algoritmasının zaman karmaşıklığı, en kötü durumda O(n²), ortalama ve en iyi durumda ise O(n log n)’dir. En kötü durum, pivotun her zaman en küçük ya da en büyük eleman olduğu durumlarda meydana gelir. Ancak çoğu durumda, Quick Sort algoritması hızlı bir performans gösterir.
Hafıza karmaşıklığı O(log n)’dir. Yani, orijinal diziyi sıralamak için ekstra bir dizi oluşturulmaz.
Sonuç
Bu bölümde, Quick Sort algoritmasını ayrıntılı bir şekilde inceledik. Quick Sort, hızlı ve etkili bir sıralama algoritmasıdır ve genellikle büyük veri setlerinin sıralanması için kullanılır.
Gelecek yazımızda bir başka algoritmayı inceleyeceğiz. Bizi takipte kalın! Eğer bu yazıyı beğendiyseniz aşağıdaki alkışa istediğiniz kadar tıklayarak yazılarıma destek olabilirsiniz :)
Herhangi bir sorunuz olursa veya benimle iletişim kurmak isterseniz, tüm sosyal medya hesaplarım aşağıdaki linkte yer alıyor.
Ayrıca diğer blog yazılarımı aşağıda yer alan websitem üzerinden takip edebilirsiniz.
Bir sonraki yazıda görüşmek üzere!
