Cuma, Aralık 4, 2020

Bilinmesi Gereken 6 Sıralama Algoritması

Sıralama algoritması, bir diziyi girdi olarak alan, dizide belirli işlemleri gerçekleştiren, bazen liste olarak adlandırılan ve sıralı bir dizi çıktı veren bir dizi talimattan oluşan bir algoritmadır. Sıralama algoritmaları, Big-O notasyonu, böl-ve-yönet yöntemleri ve veri yapıları (ikili ağaçlar, yığınlar) gibi diğer önemli bilgisayar bilimi konularını tanıtmanın basit bir yolunu sağladıkları için genellikle bilgisayar bilimi derslerinin başlarında öğretilir. Bu yazımızda ise bilinmesi gereken 6 sıralama algoritması listeleyeceğiz.

Verilerle çalışırken, sıralama temel görevlerden birisidir. Verileri sıralamak için birçok yöntem olsa bile bazıları diğerlerinden daha iyi, bazıları belirli kullanımlar için daha etkilidir. Yönteme veya kullanılan veri yapılarına bağlı olarak birçok seçeneğiniz vardır.

Bubble Sort

Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır. Örneğin:

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

    return arr


array=[7,3,1,5,6,2]
sorted_array = bubble_sort(array)
print(sorted_array) # 
#Expected output: [1,2,3,5,6,7]
  • Bubble sort algoritmasının worst (en kötü) ve average-case (ortalama durum) karmaşıklığı O(n2)dir. Yani verilerin sıralamak istediğimiz sıranın tersinde olduğu veya elemanların liste içerisinde keyfi olarak dağıtıldığı anlamına gelir.
  • En iyi karmaşıklık durumu O(n). Zaten bu da listenin sıralanmış hali oluyor.

Selection Sort

Selection sort, performans sebebiyle Bubble sort algoritmasının iyileştirilmiş halidir. Aynı worst-case karmaşıklığına sahip olsalar bile, selection sort algoritmasında daha az değişme söz konusudur.

Selection sort algoritmasının iki tür çalışma mantığı vardır. Birincisi, listedeki en küçük sayıyı bulur ve listenin başına koyar. İkincisi ise, listedeki en büyük sayıyı bulup listenin sonuna koyar. Örneğin:

selection-sıralama-algoritması

Animasyondaki sarı renk listenin sıralanmış halini, kırmızı renk listedeki minimum sayıyı, mavi ise üzerinde dolaşılan sayıyı temsil eder.

def selectionSort(array):
    for i in range(0,len(array)):
        min_index = i
        for j in range(i+1,len(array):
            if array[j] < array[min_index]:
               min_index = j
     array[i],array[min_index]=array[min_index],array[i]

array = [4,0,3,5,1,8,7]
sorted_array = selectionSort(array)
print(sorted_array)
#Expected output: [0,1,3,4,5,7,8}

Selection sort ile Bubble sort aynı karmaşıklıklara sahiptir.

Insertion Sort

Insertion sort algoritması brute-force (kaba kuvvet) bir algoritmadır. Selection sorta nazaran daha az kıyaslamay yapar.

Insertion sort algoritması, diziden bir eleman seçer ve komşuları seçilen elemandan daha küçük/büyük olup olmadıklarını sıralar. Sıralanan elemanların sayısı arttıkça, algoritma yeni elemanları sıralanan elemanlara göre kontrol eder ve yeni elemanı listede doğru konuma ekler. Mesela:

def insertionSort(array):
    for i in range(1,len(data)):
        tmp = array[i]
        minIndex = i
   while minIndex > 0 and tmp < array[minIndex -1]:
         array[minIndex] = array[minIndex -1]
         minIndex -=1
  array[minIndex] = tmp
  return array
  • Insertion sort algoritmasının en kötü ve ortalama karmaşıklık durumu O(n2)’dir. Bu durum, sırasıyla dizi ters sırada olduğunda ve öğeler dizide rastgele bulunduğunda gerçekleşir.
  • En iyi durum karmaşıklığı O(n)’dir. Bu da veriler zaten istenen sırada sıralandığında gerçekleşir.

Quick Sort

Quick sort algoritması, diğer sıraladığımız algoritmalara nazaran en verimli çalışan algoritmadır. Diziyi, öğelere sıralamak için özyinelemeli olarak çağrılan alt dizilere bölmek için divide-and-conquer (böl ve yönet) yaklaşımını kullanır.

Quick sort algoritmasını uygulamak için öncelikle bir pivot seçmemiz gerekir. Dizinin diğer değerleri seçilen pivottan büyükse sağına, küçükse 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. Örneğin:

def quickSort(array,left,right):
   if right <= left:
      return
   else:
     pivot = partition(array,left,right)
     quickSort(array,left,pivot-1)
     quickSort(array,pivot+1,right)
  return array

def partition(array,left,right):
    pivot = array[left]
    leftIndex = left+1
    rightIndex = right

   while True:
     while leftIndex <= rightIndex and array[leftIndex] <= pivot: 
           leftIndex += 1
     while rightIndex >= leftIndex and array[rightIndex] >= pivot:
            rightIndex -=1

     if rightIndex <= leftIndex:
        break

    array[leftIndex], array[rightIndex] = array[rightIndex], array[leftIndex]
     print(array)
  array[left], array[rightIndex] = array[rightIndex], array[left]
  print(array)

  return rightIndex

Quick sort algoritmasının en kötü karmaşıklık durumu O(n2)’dir. En iyi ve ortalama karmaşıklık durumu ise O(n*log(n))’dir.

Merge Sort

merge-sıralama-algoritması

Merge sort algoritması, tıpkı Quick sort algoritması gibi böl ve yönet yaklaşımını uygulayarak çalışır. Sıralama, veri kümesini ayrı parçalara bölerek ve parçaları sıralayarak başlar. Daha sonra bu küçük dizinleri kendi aralarında birleştirmeye başlar. Bu birleştirmeyi yaparken aynı zamanda sıralamayı da bununla birlikte yapar. Sıralama ve birleştirme, tüm veri kümesi yine tek bir parça olana kadar devam eder. Örneğin:

def mergeSort(array):
   if len(array) < 2:
      return array
  middle = len(array) //2
  left = mergeSort(data[:middle])
  right = mergeSort(data[middle:])

 merged = merge(left, right)
  return merged

def merge(left,right):
   if not len(left):
      return left

  if not len(right):
     return right

result = []
leftIndex = 0
rightIndex=0
totalLen = len(left) + len(right)

while(len(result) < totalLen):
     if left[leftIndex] < right[rightIndex]:
        result.append(left[leftIndex])
        leftIndex +=1
    else:
       result.append(right[rightIndex])
       rightIndex +=1

    if leftIndex == len(left) or rightIndex == len(right):
       result.extend(left[leftIndex:] or right[rightIndex:])
       break

return result
  • Merge Sort algoritmasının en kötü ve ortalama karmaşıklık durumu (n *log(n)), ki bu da onu diğer sıralama algoritmalarından daha hızlı yapar.

Bucket Sort

Bucket Sort algoritması, diziyi bucketlara (kovalara) bölerek çalışır. Daha sonra her bir kovadaki elemanlar, herhangi bir sıralama algoritması kullanılarak veya bucket sort algoritmasını yinelemeli olarak çağırarak sıralanır. Örneğin:

bucket-sıralama-algoritması
def bucketSort(array):
    bucket=[]
    for i in range(len(array)):
        bucket.append([])
    for j in array:
        index_bucket = int(10 * j)
        bucket[index_bucket].append(j)
        print(bucket)
    for i in range(len(data)):
        # Ben burda Python'da built-in bir method olan sorted()'ı kullandım.
        bucket[i] = sorted(bucket[i])
        kIndex=0
       
        for i in range(len(data)):
            for j in range(len(bucket[i])):
                array\[kIndex] = bucket[i\][j]
                kIndex+=1
    print(array)
  • Bucket Sort algoritması, O(n2) en kötü karmaşıklık durumuna sahiptir. En iyi karmaşıklık durumu ise O(n+k)’dır. Ortalama durum karmaşıklı ise O(n)’dir.

Bugün En Çok Okunanlar

CEVAP VER

Lütfen yorumunuzu giriniz!
Lütfen adınızı buraya girin