Sıralama Algoritmaları Nelerdir? Nasıl Çalışırlar?

Kod yazarken dikkat etmemiz gereken önemli şeylerin başında yazdığımız kodun time (zaman) ve space (kapladığı yer) complexity’si (karışıklığı) geliyor. Küçük çaplı projelerde her ne kadar dikkat etmesek de binlerce, on binlerce hatta belki yüz binlerce satır koddan oluşan projelerde bunlara dikkat etmemiz gerekiyor. Bunun için halihazırda kullanılmakta olan bazı algoritmalar mevcut. Daha önceki yazılarımızdan birinde bahsettiğimiz Binary Search bunlara bir örnektir. Sıralı bir dizinde eleman ararken direkt dizinin tüm elemanlarını aradığımız elemanla karşılaştırabiliriz. Ama çok fazla elemana sahip olan dizinlerde bu sistemimizi oldukça zorlayacaktır. Bu yüzden Binary Search kullanırız. Peki bir dizini nasıl sıralı hale getirebiliriz? Bu konuda yardımımıza sıralama algoritmaları yetişiyor.

Örnekler üzerinde gitmeden önce Python’da sıralama yapacağımız dizini tanımlayalım.

arr = [22,54,11,2,87,63,102,41,10,66]

Bu şekilde 10 elemanlı ve sıralı olmayan bir listemiz var. Şimdi popüler sıralama algoritmaları ile bu dizinimizi sıralı hale getirelim.

Selection Sort :

Selection Sort (Seçerek Sıralama) aslında performans bakımından diğer sıralama algoritmalarına kıyasla bir tık zayıf kalsa da zor durumlarımızda bize yardımcı oluyor. Uygulaması oldukça basit olan bu algoritma dizinin ilk elemanının en küçük eleman olduğunu varsayıyor. Ardından tek tek bu elemanı diğer elemanlarla karşılaştırıyor. Eğer karşılaştırdığı eleman daha küçük ise onu en küçük değer olarak alıyor ve ilk eleman yerine artık diğer elemanları onunla karşılaştırıyor. Dizinin sonuna vardığında ise en küçük elemanı dizinin başına yazıyor. Ardından bu işlemi 2. elemandan başlayarak yapıyor ve bulduğu en küçük değeri 2. sıraya koyuyor ve bu işlemi dizinin son elemanına kadar aynı şekilde tekrarlıyor. Selection Sort’un kodlaması kısmı ise şu şekilde :

for i in range(len(arr)):
    enKucukIdx = i
    for j in range(i+1,len(arr)):
        if arr[j] < arr[enKucukIdx]:
            enKucukIdx = j      
    arr[i],arr[enKucukIdx] = arr[enKucukIdx], arr[i]

Selection Sort time complexity’si :

• Best Case (En iyi durum) : O(n²)
• Worst Case (En kötü durum) : O(n²)
• Average Case (Ortalama Durum): O(n²)

Bubble Sort:

Bubble Sort bir diğer adıyla baloncuk sıralama algoritmasıdır. Belki de uygulaması ve kavraması en kolay olan sıralama algoritmasıdır. Bubble Sort dizinimizdeki elemanları ikili ikili karşılaştırır ve eğer soldaki eleman sağdakinden büyükse bunların yerlerini değiştirir. Bunu listenin sonuna kadar tekrarlar.

for i in range(len(arr)-1):
    for j in range(0,len(arr)-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1],arr[j]

Gördüğünüz gibi kısa bir kod parçacığı ile dizinimizi sıralı hale getirebiliyoruz. Bubble Sort’un time complexity’si ise :

• Best Case : O(n)
• Worst Case : O(n²)
• Average Case : O(n²)

Insertion Sort :

Yine uygulaması çok zor olmayan bir sıralama algoritmasını incelemekteyiz. Insertion yani ekleme sıralaması dizinin 2.elemanından başlar ve sona doğru gider. O sırada baktığı elemanı bir değerde tutar ve dizinin başına kadar o elemandan küçük eleman bulana kadar karşılaştırır. Yukarıdaki örnekte de görüldüğü gibi algoritma bir elemanı tuttuğunda onu sola doğru karşılaştıra karşılaştıra gider.

Birçok insan kart oyununda elindeki kartları sıralarken Insertion Sort mantığı ile sıralama yapar.

Insertion Sort kodlaması ise şu şekildedir:

for i in range(1,len(arr)):
    deger = arr[i]
    j = i-1
    while(j>= 0 and deger < arr[j]):
        arr[j+1] = arr[j]
        j -= 1
    arr[j+1] = deger

Insertion Sort’un time complexity’si :

• Best Case : O(n)
• Worst Case : O(n²)
• Average Case : O(n²)

Merge Sort:

Diğer sıralama algoritmalarına kıyasla uygulaması biraz karışık olan fakat hız ve kullandığı bellek bakımından onlardan daha verimli bir algoritma olan Merge Sort yani Birleştirme Sıralaması Divide and Conquer (Parçala ve Fethet) yaklaşımı ile çalışır.

Merge Sort algoritması dizini, alt dizinin eleman sayısı 1 olana tekrar tekrar ortadan ikiye böler. Ardından bu küçük dizinleri kendi aralarında birleştirmeye başlar. Bu birleştirmeyi yaparken aynı zamanda sıralamayı da bununla birlikte yapar.

def merge(sol, sag):
	if not len(sol) or not len(sag):
		return sol or sag

	sonuc = []
	i, j = 0, 0
	while (len(sonuc) < len(sol) + len(sag)):
		if sol[i] < sag[j]:
			sonuc.append(sol[i])
			i+= 1
		else:
			sonuc.append(sag[j])
			j+= 1
		if i == len(sol) or j == len(sag):
			sonuc.extend(sol[i:] or sag[j:])
			break 

	return sonuc

def mergesort(arr):
	if len(arr) < 2:
		return arr

	orta = len(arr)//2
	sol = mergesort(arr[:orta])
	sag = mergesort(arr[orta:])

	return merge(sol, sag)

Merge Sort’un time complexity’si :

• Best Case : O(n*log n)
• Worst Case : O(n*log n)
• Average Case: O(n*log n)

Quick Sort:

Quick Sort bir diğer adıyla Hızlı Sıralama da Merge Sort gibi Parçala ve Fethet yaklaşımı ile çalışır. Algoritma bir elemanı pivot değer olarak seçer ve elemanları o değer etrafında sıralar.

Quick Sort’da pivot elemanını seçmek için çok farklı yollar vardır. En çok kullanılanları ise :

• İlk elemanı pivot olarak seçme
• Son elemanı pivot olarak seçme
• Rastgele bir elemanı pivot olarak seçme
• Medyan değerini pivot olarak seçme

Quick Sort 1959 yılında geliştirilmesine rağmen, Merge Sort gibi rakiplerine göre 3 kat daha hızlıdır.

Quick Sort’da pivot seçilir ve dizinin diğer değerleri büyükse pivotun sağına, küçükse pivotun soluna atılır. Ardından sağdaki ve soldaki 2 dizinde de aynı işlem uygulanır ve bu kontrol edilen dizinin eleman sayısı 1 olana kadar devam eder. Parçalama işleminin ardından dizin birleşirken sıralı hale gelir.

İsterseniz gelin sürekli son elemanın pivot değer olarak seçildiği bu örneğe bakalım:

def parcalama(arr,low,high): 
    i = (low-1)       
    pivot_deger = arr[high]    
    for j in range(low , high): 
        if(arr[j] < pivot_deger): 
            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(arr,low,high): 
    if(low < high): 
        pivot_deger = parcalama(arr,low,high) 
        quickSort(arr, low, pivot_deger-1) 
        quickSort(arr, pivot_deger+1, high) 
        
quickSort(arr,0,len(arr)-1)

Quick Sort time complexity’si :

• Best Case: O(n*log n)
• Worst Case: O(n²)
• Average Case: O(n*log n)

Bellekte dizinleri sıralı şekilde tutmamıza yarayan bu sıralama algoritmaları genel olarak bu şekillerde çalışmakta. Verdiğimiz bu 5 örnek en çok bilinenleri fakat buradan diğer tüm sıralama algoritmalarına bakabilirsiniz.