Sıralama Algoritmaları

Sıralama Algoritmaları Nedir ?

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, bir dizi elemanın belirli bir sıraya göre düzenlenmesini sağlayan algoritmalar olarak tanımlanabilir. Bu algoritmalar, veri yapılarındaki elemanların farklı özelliklerine göre sıralanmasına olanak tanırlar.

Sıralama Algoritmaları Nelerdir ? 

1. Seçme Sıralama (Selection Sort)

2. Kabarcık Sıralama (Bubble Sort)

3. Sallama Sıralama (Shaker Sort)

4. Ekleme Sıralama (Insertion Sort)

5. Kabuk Sıralama (Shell Sort)

6. Cüce Sıralama (Gnome Sort)

7. Kütüphane Sıralama (Library Sort)

8. Hızlı Sıralama (Quick Sort)

9. Tarak Sıralama (Comb Sort)

10. Birleştirme Sıralama (Merge Sort)

11. Yığın Sıralama (Heap Sort)

12. Sayarak Sıralama (Counting Sort)

13. Kova Sıralama (Bucket Sort)

14. Temel Sıralama (Radix Sort)

15. Tim Sıralama (Tim Sort)

16. Serseri Sıralama (Stooge Sort)

17. İplik Sıralama (Strand Sort)

18. Kokteyl Sıralama (Cocktail Sort)

1. Seçme Sıralama (Selection Sort)

Seçme Sıralaması, basit bir sıralama algoritmasıdır. Bu algoritma, bir dizi içerisindeki elemanların birbiriyle karşılaştırılıp sıralanması esasına dayanır.

Algoritma, sıralanacak dizinin ilk elemanından başlayarak, dizideki tüm elemanlar üzerinde en küçük elemanı bulur ve bu elemanı ilk elemanla yer değiştirir. Ardından ikinci elemandan başlayarak, dizide kalan elemanların içinden en küçük elemanı bulur ve ikinci elemanla yer değiştirir. Bu işlem dizinin son elemanına kadar devam eder ve sonunda dizi sıralanmış bir şekilde elde edilir.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[11, 27, 34, 55, 62]

Kabarcık Sıralama (Bubble Sort)

Kabarcık Sıralaması, kolay anlaşılabilir ve basit yapılı bir sıralama algoritmasıdır. Ancak büyük veri setlerinde yavaş çalışmaktadır.

Algoritma, iki döngüden oluşur. İlk döngü, dizideki elemanların tamamı sıralanana kadar tekrarlanır. İkinci döngü, her turda elemanların son i indekse kadar döngü yapar. Eğer iki elemanın sırası yanlışsa, yer değiştirilir. Bu işlem, tüm elemanların sıralanana kadar devam eder.

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

arr = [55, 34, 27, 12, 22, 11, 62]

sorted_arr = bubble_sort(arr)

for i in sorted_arr:
    print(i)

Sonuç çıktısı:

11
12
22
27
34
55
62

Sallama Sıralama (Shaker Sort)

Sallama Sıralaması, kabarcık sıralamasına benzer bir sıralama algoritmasıdır. Kabarcık sıralamasında olduğu gibi, sallama sıralamasında da elemanlar birbirleriyle karşılaştırılarak sıralanır. Ancak kabarcık sıralamasından farklı olarak, sallama sıralamasında iki yönlü tarama yapılır ve bu sayede daha verimli bir sıralama işlemi gerçekleştirilir.




Algoritma, ilk önce liste sonuna kadar büyük olan elemanlar sağa doğru kaydırılır ve en büyük eleman sağ tarafa konumlandırılır. Daha sonra, en büyük elemanın konumunu sabitleyerek sol tarafa doğru küçük elemanlar tarama edilir ve en küçük eleman sol tarafa konumlandırılır. Bu işlem, tüm elemanlar sıralanana kadar tekrarlanır.

def shaker_sort(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        for i in range(left, right):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
        right -= 1
        for i in range(right, left, -1):
            if arr[i] < arr[i-1]:
                arr[i], arr[i-1] = arr[i-1], arr[i]
        left += 1
    return arr

arr = [800, 123, 444, 712, 11]
sorted_arr = shaker_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[11, 123, 444, 712, 800]

Ekleme Sıralama (Insertion Sort)

Ekleme Sıralaması, sıralanacak olan dizinin elemanlarını, dizinin önceden sıralanmış bölümündeki uygun pozisyona yerleştirerek sıralama yapan basit bir sıralama algoritmasıdır.

Algoritma, ikinci elemandan başlayarak her karşılaştırma sonucu bir sağdaki sayıya atlayarak devam ederek, sol tarafta kalan sayılar ile karşılaştırılması ve bir dizi oluşturulmasını sağlıyor. Özellikle küçük boyutlu diziler için oldukça etkili bir sıralama algoritmasıdır.

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

arr = [62, 27, 55, 34, 11]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[11, 27, 34, 55, 62]

Kabuk Sıralama (Shell Sort)

Kabuk Sıralama, insertion sort algoritmasına dayalı olarak çalışan bir sıralama algoritmasıdır. Kabuk sıralaması, insertion sort algoritmasından farklı olarak, aralıklarla elemanları karşılaştırır ve bu aralıkları her adımda azaltarak son adımda elemanları bir araya getirerek sıralama işlemini gerçekleştirir.

def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i

            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp
        gap //= 2

    return arr

arr = [62, 27, 55, 34, 11]
sorted_arr = shell_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[11, 27, 34, 55, 62]

Cüce Sıralama (Gnome Sort)

Cüce Sıralama, özellikle küçük boyutlu dizilerde etkili bir sıralama algoritmasıdır. Ancak, büyük boyutlu dizilerde performansı diğer algoritmalara göre düşük olabilir. Eklemeli Sıralamaya benzer bir yapısı vardır.

Algoritma, sıralanacak olan dizinin başından itibaren başlayarak, her adımda önceki elemanla karşılaştırarak doğru pozisyona yerleştirir. Eğer önceki elemandan küçükse, bir önceki elemanla yer değiştirir. Diziyi sonuna kadar gezdikten sonra, yeniden başa döner ve işlemi tekrarlar. Bu işlem, sıralanacak olan dizi tamamen sıralanana kadar devam eder.

def gnome_sort(arr):
    i = 0
    n = len(arr)
    while i < n:
        if i == 0 or arr[i] >= arr[i-1]:
            i += 1
        else:
            arr[i], arr[i-1] = arr[i-1], arr[i]
            i -= 1
    return arr

arr = [5, 3, 8, 1, 6, 9]
n = len(arr)
sorted_arr = gnome_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[1, 3, 5, 6, 8, 9]

Kütüphane Sıralama (Library Sort)

Kütüphane Sıralaması, eklemeli sıralama algoritmasını art arda yapılan eklemeleri dizideki boşlukları kullanıp hızlandırarak kullanan bir sıralama algoritmasıdır. Tek sorunu ise algoritmanın kullandığı aralıklar nedeniyle fazladan yere gereksinim duymasıdır.

def library_sort(arr):
    chunks = [[]]
    for i in range(1, len(arr)):
        if arr[i] < arr[i - 1]:
            chunks.append([])
        chunks[-1].append(arr[i])

    for i in range(len(chunks)):
        chunks[i].sort()

    sorted_arr = []
    for chunk in chunks:
        sorted_arr = merge(sorted_arr, chunk)
    return sorted_arr

def merge(A, B):
    if len(A) == 0:
        return B
    elif len(B) == 0:
        return A
    elif A[0] < B[0]:
        return [A[0]] + merge(A[1:], B)
    else:
        return [B[0]] + merge(A, B[1:])

arr = [5, 3, 8, 1, 6, 9, 12, 55, 64, 27, 62]
sorted_arr = library_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[1, 3, 6, 8, 9, 12, 27, 55, 62, 64]

Hızlı Sıralama (Quick Sort)

Hızlı Sıralaması, karşılaştırmalı bir sıralama algoritmasıdır, yani elemanların karşılaştırılması ile sıralama işlemi gerçekleştirilir. En hızlı sıralama algoritmalarından biridir ve genellikle tercih edilen bir sıralama algoritmasıdır.

Algoritma, pivot olarak adlandırılan bir eleman seçerek çalışır. Bu eleman, dizinin bir yerinde seçilir ve bu elemandan küçük olan elemanlar soluna, büyük olanlar sağına yerleştirilir. En kötü durumda, yani pivot seçimi yanlış yapıldığında, performansı düşük olabilir. Bu nedenle, iyi bir pivot seçimi algoritmanın verimliliği açısından önemlidir.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in range(1, len(arr)):
            if arr[i] < pivot:
                left.append(arr[i])
            else:
                right.append(arr[i])
        return quick_sort(left) + [pivot] + quick_sort(right)

arr = [64, 25, 12, 22, 11, 34, 55, 62, 117, -12]
sorted_arr = quick_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[-12, 11, 12, 22, 25, 34, 55, 62, 64, 117]

Tarak Sıralama (Comb Sort)

Tarak Sıralama, Kabarcık ve Hızlı sıralama karışımıdır. Ancak, kabarcık sıralamasının aksine, sabit bir adım büyüklüğü yerine, aralığı azaltarak sıralama yapar. Bu algoritma, özellikle büyük listeleri sıralarken performansı artırır.

Algoritma, önce listeyi bir adım boyutunda bölerek alt diziler oluşturur. Daha sonra, alt diziler arasındaki elemanları karşılaştırarak swap işlemi yapar. Bu işlem, listenin sonuna kadar devam eder. Daha sonra adım boyutunu azaltarak işlemi tekrarlar. Adım boyutu 1 olduğunda, algoritma bitirilir.

def comb_sort(arr):
    n = len(arr)
    gap = n
    shrink = 1.3
    swapped = True

    while gap > 1 or swapped:
        gap = int(gap / shrink)
        swapped = False
        i = 0
        while i + gap < n:
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True
            i += 1

    return arr

arr = [5, 3, 8, 1, 6, 9]
n = len(arr)
sorted_arr = comb_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[1, 3, 5, 6, 8, 9]


Birleştirme Sıralama (Merge Sort)

Birleştirme Sıralaması, karşılaştırmalı bir sıralama algoritmasıdır. Sıralanacak dizi çok büyük olduğunda performans açısından diğer sıralama algoritmalarından daha iyi sonuçlar verir. Ancak yüksek bellek kullanımı nedeniyle küçük boyutlu dizilerde dieğr sıralama algoriitmalarına göre daha yavaş çalışabilir.

Algoritma, sıralanacak diziyi önce küçük parçalara ayırarak daha sonra bu küçük parçaları sıralayarak son olarak da birleştirerek tam bir sıralı dizi elde eder

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr
arr = [64, 25, 12, 22, 11, 34, 55, 62, 117, -12, 2, 2, 27, 34, -3, -9]
sorted_arr = merge_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[-12, -9, -3, 2, 2, 11, 12, 22, 25, 27, 34, 34, 55, 62, 64, 117]

Yığın Sıralama (Heap Sort)

Yığın Sıralaması, bir diziyi sıralamak için yığın veri yapısını kullanır. Bir yığın, bir ağaç veri yapısıdır ve her düğüm, ona bağlı olan iki düğüme sahiptir. İstikrarsız bir sıralama algoritmasıdır, yani aynı anahtar değerlerine sahip elemanlar sıralama işlemi sonrasında orijinal sıralama durumunu koruyamayabilir. En kötü durumda O(n log n) zaman karmaşıklığına sahiptir ve sabit ekstra bellek gerektirir.

Algoritma, ilk olarak diziyi bir yığın veri yapısına dönüştürür. Daha sonra yığının en büyük elemanını (dizinin ilk elemanı) dizinin sonuna taşır ve yığını yeniden düzenleyerek yine en büyük elemanı bulur. Bu işlem yığın tamamen boşalana kadar (dizi sıralanana kadar) tekrarlanır.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)

    # Yığını oluştur
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Yığından sırayla eleman alarak sırala
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr

arr = [64, 25, 12, 22, 11, 34, 55, 62, 117, -12, 2, 2, 27, 34, -3, -9, 79, 8, 0, 13]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[-12, -9, -3, 0, 2, 2, 8, 11, 12, 13, 22, 25, 27, 34, 34, 55, 62, 64, 79, 117]

Sayarak Sıralama (Couting Sort)

Sayarak Sıralama, özellikle küçük sayılarla sıralama yapılması gerektiği durumlarda tercih edilen bir sıralama algoritmasıdır. Sıralanacak dizideki en büyük sayı biliniyorsa, O(n) zaman karmaşıklığına sahip olması sebebiyle hızlı bir sıralama algoritmasıdır.

Algoritma, sıralanacak dizideki her bir elemanın kaç kez tekrar ettiğini sayarak çalışır. Ardından, sayım dizisi adı verilen bir yardımcı dizi kullanarak, her bir elemanın sıralanmış dizideki doğru pozisyonunu hesaplar.

def counting_sort(arr):
    n = len(arr)
    count = [0] * 10
    output = [0] * n
    for i in range(n):
        count[arr[i]] += 1
    for i in range(1, 10):
        count[i] += count[i-1]
    for i in range(n-1, -1, -1):
        output[count[arr[i]]-1] = arr[i]
        count[arr[i]] -= 1
    return output

arr = [1, 4, 1, 2, 7, 5, 2]
sorted_arr = counting_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[1, 1, 2, 2, 4, 5, 7]


Kova Sıralama (Bucket Sort)

Kova Sıralama, elemanları bir aralıkta bulunan dizileri sıralamak için kullanılan bir sıralama algoritmasıdır. Bu algoritma, elemanları bölerek farklı kovalara yerleştirir, daha sonra her bir kova içindeki elemanları ayrı ayrı sıralar ve son olarak kovaların içeriğini birleştirerek sıralanmış diziyi oluşturur.

Kova sıralama, elemanların dağılımı eşit şekilde olduğunda çok verimli bir algoritma olabilir. Ancak elemanların dağılımı dengesiz olduğunda performansı düşebilir. Örneğin, elemanların büyük bir kısmı aynı kovada toplanırsa, o kovanın içindeki elemanlar için başka bir sıralama algoritması kullanılması gerekebilir.

def bucket_sort(arr, bucket_size=5):
    if len(arr) == 0:
        return arr

    min_value = min(arr)
    max_value = max(arr)

    bucket_count = (max_value - min_value) // bucket_size + 1
    buckets = [[] for _ in range(bucket_count)]

    for i in range(len(arr)):
        buckets[(arr[i] - min_value) // bucket_size].append(arr[i])

    for i in range(bucket_count):
        buckets[i].sort()

    result = []
    for i in range(bucket_count):
        result += buckets[i]

    return result

arr = [10, 9, 7, 8, -6, 0 ,34, 62, 55, 34]
sorted_arr = bucket_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[-6, 0, 7, 8, 9, 10, 34, 34, 55, 62]

Temel Sıralama (Radix Sort)

Temel Sıralama, basamaklar arasında sıralama yaparak çalışan bir sıralama algoritmasıdır. Öncelikle sıralanacak sayıların hangi sayı sistemi üzerinden sıralanacağı belirlenir. Örneğin onluk sayı sistemi için basamaklar 0'dan 9'a kadar giderken, ikilik sayı sistemi için sadece 0 ve 1 basamakları vardır.

Algoritma, sayıları sıralamak için önce en az anlamlı basamaktan başlayarak sayıları sınıflandırmak için bir dizi adım gerçekleştirir. Sonra bir sonraki anlamlı basamakta yeniden sıralama yapılır ve bu adım basamaklar bittikçe tekrarlanır.

def radix_sort(arr):
    max_num = max(arr)
    digit_count = 0
    while max_num > 0:
        max_num //= 10
        digit_count += 1

    for i in range(digit_count):
        buckets = [[] for _ in range(10)]
        for num in arr:
            digit = (num // (10 ** i)) % 10
            buckets[digit].append(num)

        arr = []
        for bucket in buckets:
            arr.extend(bucket)

    return arr

arr = [800, 123, 444, 712, 11]
sorted_arr = radix_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[11, 123, 444, 712, 800]

Tim Sıralama (Tim Sort)

Tim Sıralama, birleştirme (merge) sıralama ve ekleme (insertion) sıralamasının birleşiminden oluşan bir sıralama algoritmasıdır.




Tim sort, öncelikle küçük alt-listeler oluşturarak insertion sort kullanır. Bu alt-listeler, belli bir boyutun altına düşene kadar devam ederler. Daha sonra, birleştirme sıralaması ile alt-listeler birleştirilir.

Python'da "sorted()" fonksiyonu, varsayılan olarak Tim sort'u kullanır.

numbers = [5, 1, 3, 2, 4]
sorted_numbers = sorted(numbers)
print(sorted_numbers)

Sonuç çıktısı:

[1, 2, 3, 4, 5]

Serseri Sıralama (Stooge Sort)

Serseri Sıralama, üçlü bir rekürsif algoritma kullanarak bir diziyi sıralamak için kullanılan bir sıralama algoritmasıdır.

Algoritma, bir dizi elemanını serseri sıralaması yöntemi kullanarak sıralar. İlk olarak, dizinin ilk ve son elemanları karşılaştırılır ve gerekiyorsa yerleri değiştirilir. Daha sonra, dizinin ilk 2/3'lük kısmı sıralanır, ardından son 2/3'lük kısmı sıralanır ve son olarak ilk 2/3'lük kısım tekrar sıralanır. Bu işlemler, dizinin tamamen sıralanana kadar devam eder.

def stooge_sort(arr, start, end):
    if arr[start] > arr[end]:
        arr[start], arr[end] = arr[end], arr[start]

    if (end - start + 1) > 2:
        one_third = (end - start + 1) // 3

        stooge_sort(arr, start, end - one_third)

        stooge_sort(arr, start + one_third, end)

        stooge_sort(arr, start, end - one_third)

    return arr

arr = [5, 3, 8, 1, 6, 9]
n = len(arr)
sorted_arr = stooge_sort(arr, 0, n - 1)
print(sorted_arr)

Sonuç çıktısı:

[1, 3, 5, 6, 8, 9]

İplik Sıralama (Strand Sort)

İplik Sıralama, sıralanacak olan dizinin, sıralanmış alt dizilerinin oluşturularak bu alt dizilerin birleştirilmesi yoluyla sonucun oluşturulması mantığına dayanır. Algoritmanın her bir aşamasında ana dizinin üzerinden geçilir ve bu diziden zaten sıralanmış olan bir dizi eleman çıkarılır. Çıkarılan bu eleman dizileri daha sonra birleştirilir.

def strand_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = strand_sort(left_half)
    right_half = strand_sort(right_half)

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:]
    result += right[j:]

    return result

arr = [5, 3, 8, 1, 6, 9, 12, 55, 64, 27, 62]
sorted_arr = strand_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[1, 3, 5, 6, 8, 9, 12, 27, 55, 62, 64]

Kokteyl Sıralama (Cocktail Sort)

Shaker sort ve Cocktail sort aslında aynı sıralama algoritmasını temsil eder. İkisi de Bubble sort'un geliştirilmiş versiyonlarıdır. Algoritmaları arasında bir fark yoktur

def cocktail_sort(A):
    n = len(A)
    swapped = True
    start = 0
    end = n - 1
    while swapped:
        swapped = False
        # soldan sağa doğru tarayın
        for i in range(start, end):
            if A[i] > A[i + 1]:
                A[i], A[i + 1] = A[i + 1], A[i]
                swapped = True
        # sağdan sola doğru tarayın
        if not swapped:
            break
        swapped = False
        end = end - 1
        for i in range(end - 1, start - 1, -1):
            if A[i] > A[i + 1]:
                A[i], A[i + 1] = A[i + 1], A[i]
                swapped = True
        start = start + 1
    return A

arr = [5, 3, 8, 1, 6, 9, 12, 55, 64, 27, 62, 62]
sorted_arr = cocktail_sort(arr)
print(sorted_arr)

Sonuç çıktısı:

[1, 3, 5, 6, 8, 9, 12, 27, 55, 62, 64]