1 dk, tahmini okuma süresi
Python ile Hızlı Sıralama
En Son Güncelleme: 2 Ekim, 2022Hızlı sıralama, dizilerimizi/listelerimizi sıralamak için kullanabileceğimiz bir başka böl ve yönet algoritmasıdır. Öncelikle bir pivot noktası seçiyoruz. Bu pivot noktasını (veya değeri) seçtikten sonra, daha küçük değerleri soluna ve daha büyük değerleri sağına koyacağız. Dizimizi/listemizi bu pivot noktasına böleceğiz ve listeyi sıralayana kadar yinelemeli olarak sıralama algoritmamızı yürüteceğiz.
§Başlayalım
Pivot noktasını birden çok şekilde seçebiliriz. İlk, son veya orta değeri pivot olarak seçebileceğimiz gibi listemizden rastgele de seçebiliriz. Örneklerimizde pivotu nasıl seçtiğimiz çok önemli olmayacak, ancak gelecekte en kötü durum zaman karmaşıklığından kaçınmak için pivot olarak ortadaki elementi / değeri seçin. Analiz hakkında daha fazla bilgi edinmek istiyorsanız bu algoritmanın analiziyle ilgili bu harika videoyu izleyebilirsiniz.
§İlk Yaklaşım
Az önce söylediğim gibi, aynı işlevi oluşturmanın birden fazla yolu var ve burada iki tanesini göstereceğim. Algoritmalardan birinde diziyi tarayacak iki indeksimiz olacak. Dizinin farklı uçlarından taramaya başlayacaklar. Biri pivottan daha küçük bir değer arayacak, diğeri pivottan daha büyük bir değer arayacak. Her iki örnekte de dizileri artan düzende (min -> max) sıralayacağız.
Bu, ilk yaklaşımın kodu:
def partition(arr, low, high):
pivot = arr[high]
l = low
h = high - 1
while True:
while l <= h and arr[h] >= pivot:
h = h - 1
while l <= h and arr[l] <= pivot:
l = l + 1
if l <= h:
arr[l], arr[h] = arr[h], arr[l]
else:
break
arr[high], arr[l] = arr[l], arr[high]
return h
def quick_sort(arr, l, h):
if l < h:
p = partition(arr, l, h)
quick_sort(arr, l, p)
quick_sort(arr, p + 1, h)
if __name__ == "__main__":
data = [30, 20, 70, 10, 50, 90, 40]
print("Unsorted Array: ")
print(data)
size = len(data)
quick_sort(data, 0, size - 1)
print('Sorted Array in Ascending Order: ')
print(data)
§İkinci Yaklaşım
Aynı algoritmayı oluşturmanın sevdiğim ikinci yolu, aslında ilkinden çok daha popüler. Bunda pivot olarak son değeri seçiyoruz. Pivottan daha büyük ve daha küçük bir değer arayacak iki indeks var. Pivottan daha küçük bir değer arayarak diziyi tarayacağız ve bulduğumuzda ikinci dizini (indeks) artıracağız ve değiştireceğiz. Yinelemeyi bitirdiğimizde, dizideki sonuncu değeri ve indeksten daha küçük bir değer olan son i değeri ile takas ettireceğiz. Bu son değeri de geri döndüreceğiz.
Bu da ikinci yaklaşımın kodu:
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
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 quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
data = [30, 20, 70, 10, 50, 90, 40]
print("Unsorted Array: ")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order: ')
print(data)
§Hızlı Sıralamanın Karmaşıklığı
Bu algoritma için en kötü durum zaman karmaşıklığı O(N²)'dir, ancak sıralanmış bir diziniz olmadığı sürece bunu görmezsiniz. En kötü durumda O(N²) olmasını önlemek için pivotu medyan, rastgele veya orta nokta olarak seçin. Ortalama zaman karmaşıklığı O(NlogN) olacaktır. Bulabildiğim en basit ve anlaşılır açıklamanın bu olduğunu düşündüğüm için bu videoya bir göz atmanızı öneririm.
Her özyinelemeli çağrı O(1) yer kullanır. Bu algoritma için herhangi bir yardımcı dizi vs. kullanmadığımız için yer (alan) karmaşıklığımız yinelemeler tarafından oluşturulan ağacın yüksekliğine bağlı olacaktır. Yani en azından logn olduğunu söyleyebiliriz. En kötü durumda, dizinin uzunluğu kadar yığın oluşturacağız. En kötü durumda uzay karmaşıklığı O(N) olacaktır. Bu en kötü durum da yukarıda linkini bıraktığım videoda daha detaylı anlatılıyor.
Öğrenmeye devam edin!
Ilker AkbiyikBenzer Paylaşımlar
