Giriş
Merhabalar, bu konumda sıralama algoritmalarından ve çalışma mantıklarından bahsedeceğim. Sıralama algoritmalarını kullanmamızdaki amaç (adı üstünde) elimizdeki veriyi sıralamak. Tabii en hızlı şekilde. Genelde sayıları ve harfleri sıralıyoruz. Türlü türlü sıralama algoritması var, bazılarının yazması kolay fakat performansı düşük, bu algoritmaları genelde küçük listelerde kullanıyoruz. Bazılarının ise performansı yüksek fakat koda dökmesi/yazması zor. Bu algoritmalar genelde büyük listelerde kullanılır. En popülerlerine bir bakalım.
Bahsedeceklerim
» Bubble Sort
» Selection Sort
» Insertion Sort
» Merge sort
» Quick Sort
» Heap Sort
» Counting Sort
» Radix Sort
Konu Formatı
1) Algoritma açıklaması
2) Algoritmadan bir örnek
3) Worst Case, Best Case, Yöntem, Kararlılık
4) Bir programlama dili ile bu algoritmayı yazalım (Python)
5) Algoritma hakkında açıklayıcı görsel/video.
6) Algoritmayı öğrenirken kullanılabilecek harici linkler.
1. Bubble Sort
1.1) Bubble Sort en basit sıralama algoritmalarından biridir. Küçük listelerde iş görür bir sıralama algoritmasıdır. Koda dökmesi diğerlerine nazaran daha kolay. Karşılaştırma temellidir. Listedeki yan yana olan her ikili karşılaştırılarak geçişler tamamlanır. Eğer ilk değer büyükse diğer değer ile yer değiştirilir. Daha iyi anlamamız açısından bir örnek verelim.
1.2) Örneğin listemiz (1 5 7 6 2) olsun.
İlk Geçiş :
(1 5 7 6 2) -> Sıra doğru, devam.
(1 5 7 6 2) -> Sıra doğru, devam.
(1 5 7 6 2) -> 6<7 yer değiştir.
(1 5 6 7 2) -> 2<7 yer değiştir.
İkinci Geçiş :
(1 5 6 2 7) -> Sıra doğru, devam.
(1 5 6 2 7) -> Sıra doğru, devam.
(1 5 6 2 7) -> 2<6 yer değiştir.
Üçüncü geçiş :
(1 5 2 6 7) -> Sıra doğru, devam.
(1 5 2 6 7) -> 2<5 yer değiştir.
1.3) Performans
Worst Case : Ters sıralanmış dizi (n²)
Best Case : Sıralanmış dizi
Yöntem : Değiştirme
Kararlı mı : Evet
1.4) Python ile bu Bubble Sort algoritmasını yazalım. Bubble Sort fonksiyonu açıp parametre olarak bir liste alıyorum. Bu kodu Worst Case'e göre yazdığım için en başta listenin uzunluğunu alıp bu uzunluk kadar dönecek bir for döngüsü açıyorum. Bu for geçişlerimizi belirleyecek. Bu döngünün içine tekrar bir döngü açıp her ikiliyi geziyorum. İf bloğu açarak eğer ilk eleman ikinci elemandan büyükse yer değiştir diyorum. En sonda ise sıralanmış listemizi döndürüyorum. Kodları konu altına bırakacağım. Kodu daha optimize hale getirebilirsiniz.
1.5) Bubble Sort hakkında bir gif :
1.6) Yararlı Linkler
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://youtu.be/Cq7SMsQBEUw
https://www.geeksforgeeks.org/bubble-sort/
https://youtu.be/wiNIQ_lT3fk
https://youtu.be/xli_FI7CuzA
2 - Selection Sort
2.1) Çalışma mantığı basit bir algoritmadır. Performansı düşüktür. Bubble Sort'ta olduğu gibi performansı düşük olduğu için küçük listelerde kullanmaya daha uygundur. Selection Sort, sıralanması gereken listenin üstünden geçerek en küçük/en büyük sayıyı bulur ve sıralanmamış ilk değer ile yer değiştirir. Algoritma, belirli bir dizide iki alt diziyi korur. Birincisi sıralanmış dizi, ikincisi sıralanmamış dizi. Her geçişte sıralanmamış alt diziden min/max eleman alınır ve sıralı alt diziye taşınır. Alttaki örnek Seçim Algoritmasının çalışma mantığını daha iyi anlamanızı sağlayacaktır.
2.2) Çalışma mantığını anlatan bir örnek verelim.
arr[ ] = 64 25 12 22 11
Sarı : Sıralanmış alt dizi
Kırmızı : Sıralanmamış alt dizi
İlk geçiş :
arr[0...4] arasıdnan en küçük elemanı bul
Sıralanmamış ilk değer ile yer değiştir
11 25 12 22 64
İkinci geçiş :
arr[1...4] arasından en küçük elemanı bul
Sıralanmamış ilk değer ile yer değiştir
11 12 25 22 64
Üçüncü geçiş :
arr[2...4] arasından en küçük elemanı bul
Sıralanmamış ilk değer ile yer değiştir
11 12 22 25 64
Dördüncü geçiş :
arr[3...4] arasından en küçük elemanı bul
Sıralanmamış ilk değer ile yer değiştir
11 12 22 25 64
2.3) Performans
Worst Case : Ters sıralanmış dizi (n²)
Best Case : Sıralanmış dizi
Yöntem : Seçme
Kararlı mı : Hayır
2.4) Algoritmanın Python ile yazılmış hali:
2.5) Algoritmanın akış şeması :
2.6) Yararlı Linkler
Kod : https://github.com/hkeydesign/sort/blob/main/selection.py
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://youtu.be/tOa-RGkTSO0
https://www.geeksforgeeks.org/selection-sort/
https://youtu.be/g-PGLbMth_g
https://youtu.be/xWBP4lzkoyM
3 - Insertion Sort
3.1) Insertion Sort'a sokma, sokuşturma sıralaması diyebiliriz. Sıralanmamış kısımdan sıralanmış kısma eleman sokularak olması gereken yere taşınır. Dizi sanal olarak sıralanmış ve sıralanmamış olarak iki bölüme ayrılmıştır. Bu bölümleri ayracımız oluşturur. Sıralanmamış parçadan alınan değerler alınır ve sıralanan parçada doğru konuma yerleştirilir.
3.2) Bir örnek verelim:
listem = (1 4 2 5 3)
Sarı : Sıralanmış alt dizi
Kırmızı : Sıralanmamış alt dizi
| : Sanal Ayraç
Birinci geçiş :
1 | 4 2 5 3 -> 1 sıralı olduğu için devam.
İkinci geçiş:
1 4 | 2 5 3 -> 1 ve 4 sıralı olduğu için devam.
Üçüncü geçiş :
1 2 4 | 5 3 -> Geçiş tek adımda bitti.
Dördüncü geçiş :
1 2 4 5 | 3 -> Sıralı, devam.
Beşinci geçiş :
1 2 4 3 5 | -> 3<4 o yüzden yer değişecek.
1 2 3 4 5 | -> Sıralama bitti.
3.3) Performans
Worst Case : Ters sıralanmış dizi (n²)
Best Case : Sıralanmış dizi
Yöntem : Ekleme
Kararlı mı : Evet
3.4) Algoritmanın Python ile yazılmış hali :
3.5) Eklemeli Sıralama'nın rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek.
3.6) Yararlı Linkler
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://youtu.be/NnMSqZgvruM
https://www.geeksforgeeks.org/insertion-sort/
https://youtu.be/JU767SDMDvA
4 - Merge Sort
4.1) Merge Sort, Divide and Conquer (Parçala Fethet) mantığıyla çalışan bir algoritmadır. Öncelikle listeyi küçük parçalara ayırır. Bir üst katta bu küçük parçaları sıralar. Küçük parçalar birleşerek aralarında sıralanır. Böyle birleştirilerek parça sayısı teke inene kadar devam edilir ve sıralama tamamlanır. Oldukça verimlidir fakat koda dökmesi bizi biraz zorlayabilir :
Divide : n elemanlı sayı dizisisinin n/2 elemanlı iki diziye indirilmesi
Conquer : Her iki dizinin kendi arasında sıralanması
Combine : Sıralanmış dizilerin birleştirilmesi.
4.2) Bu örneği yazarak vermek gerçekten kafa karıştırıcı olacağı için kendi hazırladığım grafikleri sunmayı tercih ettim..
Öncelikle liste parçalara ayrılıyor.
İkili parçalara ayırldıktan sonra parçalar kendi arasında sıralanarak yazılır. Bir üst kata çıkarken birleşen iki ikilinin öncelikle ilk indexleri karşılaştırılır. Daha sonra bu işlem yukarı çıkana kadar ilk index, ikinci index şeklinde devam eder...
4.3) Performans
Worst Case : O(n log n)
Best Case : O(n log)
Yöntem : Birleştirme
Kararlı mı : Evet
4.4) Algoritmanın Python ile yazılmış hali.
4.5) Birleştirmeli sıralama'nın (merge sort) rastgele üretilmiş sayıları gösteren noktaları nasıl sıraladığını gösteren örnek
4.6) Yararlı Linkler
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://youtu.be/7LN9z140U90
https://youtu.be/f9CNp_uuNJg
https://www.geeksforgeeks.org/merge-sort/
5 - Quick Sort
5.1) Quick Sort, Böl ve Fethet mantığıyla çalışan bir algoritmadır. Pivot bir eleman seçilip diğer elemanlar pivot elemanın etrafında/yanında sıralanır. Pivot elemandan küçük olanlar sol tarafa, büyük olanlar sağ tarafa atılır. Bir kaç farklı pivot seçme yolu vardır:
1- Her zaman ilk elamanı pivot seç.
2- Her zaman son elemanı pivot seç.
3- Her zaman ortadaki elemanı pivot seç.
4- Rastgele bir pivot seç.
Farklı pivot seçme yollarının olmasının yanında bunların performansa da etkisi olduğu savunuluyor. Orijinal makalede her zaman ilk eleman pivot olarak seçilmiştir. Ben de bu örnekte ilk elemanı pivot olarak seçmeyi tercih ettim. Siz diğer elemanları da pivot olarak seçebilirsiniz.
5.2) Bir örnek verelim.
Sıralanacak listemiz (33 25 69 12 56 85 47) olsun
Mavi : Pivot
Sarılar : Karşılaştırılanlar
Kırmızı : Sıralananlar
33 47 69 85 56 12 25 -> İlk elemanımızı Pivot olarak seçtim.
33 47 69 85 56 12 25 -> 47 33'ten büyük ve 25 33'ten küçük. Yerlerini değiştiriyorum.
33 25 69 85 56 12 47 -> Yine karşılaştırıyoruz ve 12<33<69 olduğu için yerlerini değiştiriyorum.
33 25 12 85 56 69 47 -> 33<56<85 olduğu yine bir yer değiştirme işlemi yapmıyorum.
33 25 12 85 56 69 47 -> Şimdi ise Pivot elemanımızı olması gereken yere yerleştirelim.
25 12 33 85 56 69 47 -> Pivotumuzu yerine koyduk.
Elemanlar bu şekilde büyük ve küçük olarak ayrıldıktan sonra tekrar kendi aralarında Pivot şeçilerek sıralanır.
5.3) Performans
Worst Case : Her seferinde en küçük elemanı pivot seçtiğimizde ortaya çıkar. O(n²)
Best Case : Her seferinde ortanca sayıyı seçtiğimizde ortaya çıkar. Pivot seçme yöntemlerindeki ortanca ile karıştırmayın, buradaki ortanca sıralamaya göre ortanca.
Yöntem : Bölümlendirme
Kararlı mı : Hayır
5.4) Algoritmanın Python ile yazılmış hali.
5.5) Algoritma hakkında bir kaç grafik:
Yatay mavi çizgiler pivot:
5.6) Yararlı linkler
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://www.geeksforgeeks.org/quick-sort/
https://youtu.be/aubOM9dOy6c
https://youtu.be/Hoixgm4-P4M
6 - Heap Sort
6.1) İlla Türkçe karşılığını kullanmak istersek Yığın Algoritması olarak çevirebiliriz. Hızlı sıralama algoritmasından daha yavaş çalışıyor. Sıralama işleminde karmaşıklığı azaltmak için Heap veri yapısını kullanıyor. Heap ikili bir ağaç yapısıdır. Maksimum ve Minimum olarak iki türe ayrılır. Maksimumda en büyük sayı tepededir ve aşağı doğru sayılar azalmaktadır. Minimumda ise en küçük eleman en üsttedir ve sayılar aşağı indikçe azalmaktadır.
6.2) Örnek olarak şu diziyi sıralayalım - > [9, 25, 8, 2, 15, 13]
Ben şu an Maksimuma göre sıralayacağım. Öncelikle ağacımıza yerleştirelim :
En son index'in parent düğümünü buluyorum. Son index 13 değerli 6. index -> 6/2 = 3 yani üçüncü index ile karşılaştıracağız. İndex'i 0'dan değil de 1'den başlattım. Eğer 0'dan başlatsaydık 1 ekleyip işlem yapmamız gerekiyordu ama şu an karışılıklağa gerek yok, temeli öğrenmeyi amaçlıyoruz.
13 daha büyük olduğu ve ben maksimuma göre sıraladığım için yer değiştirdim. Şimdi diğer bir parent düğümüm olan 25 ile bireylerini karşılaştıracağım.
Sıraları doğru olduğu için ellemiyorum ve 15 ile 25'i karşılaştıracağım.
23 ikisinden de büyük olduğu için ellemedim. Şimdi root yani en tepe nokta ile karşılaştırma yapacağım.
25>9 olduğu için yer değiştirme işlemi yaptım.
25>13 olduğu için yer değiştirme işlemi yapmadım. Gördüğünüz gibi sıralama doğru olmadı. Elde ettiğimiz heap'te bir hata var. Bu sorunun sebebi 3. index'in çocuklarından biri olan 15 değerli 5. index'ten küçük olması. Bunu çözmek için işlemker recursive olarak devam etmeli. Şimdi aşağı doğru kontrole devam edelim.
Sorun yok, sıra doğru.
Diğer çocuğu ile karşılaştığımızda hatayı görüp yer değiştiriyoruz.
Verilerimiz yerleştirildikten sonra heap'ten silme işlemi yaparak sıralamayı yapabiliriz. Verileri silerken root eleman silinerek son index'teki eleman root yerine alınır.
Daha sonrasında Heap sıralanır. Üst kısımda anlattığım için tekrar yazmayacağım direkt düzenleyip göstereceğim.
Şimdi bu heap'i en alttan ve soldan listemize eklersek küçükten büyüğe bir sıralama elde ederiz. Heap'ten çıkardığımzı root elemanımız listenin en sonuna eklenir.
Sıralanmış dizimiz = [2, 8, 9, 13, 15, 25]
6.3) Performans
Worst Case : O(n log n)
Best Case : O(nlog n)
Yöntem : Seçme
Kararlı mı : Evet
6.4) Algoritmanın Python ile yazılmış hali:
6.5) Heap sort'un karışık elemanları nasıl sıraladığına dair bir gif:
6.6) Yararlı Linkler
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://www.geeksforgeeks.org/heap-sort/
https://youtu.be/HYLiT2wffUE
7 - Counting Sort
7.1) Veri kümesinde yer alan elemanların aralığını kullanarak sıralama yapar. En büyük eleman bulunarak [0..n] aralığında bir dizi oluşturulur. Lineer bir yapıya sahiptir ve kolay uygulanır. Hafızada karmaşıklığı fazladır fakat zaman karmaşıklığı diğer algoritmalara nazaran azdır. Dizideki değerlerin aralık bilgileri ile yeni bir dizi oluşturur ve bu dizide bulunan elemanların sayılarını (dizide x sayısından kaç tane var) bulundurur.
7.2)
Sıralayacağımız dizi:
Öncelikle bu diziden max değerini bulup yeni bir dizi oluşturalım.
Max -> 8
0-8
Bu aralıkta oluşturduğum dizi:
Her elemanın kaç tane bulunduğunu gösteriyor:
Artık tek yapmamız gereken her elemanı sayma değeri kadar yazmak . 1 tane 1, 3 tane 5, 1 tane 6, 1 tane 7 ve 1 tane 8:
7.3) Performans
Worst Case : O(n+k)
Best Case: O(n+k)
Yöntem : Sayma
Kararlı mı : Hayır
7.4) Algoritmanın Python ile yazılmış hali:
7.5) Güzel bir kaç gif:
7.6) Yararlı Linkler :
Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://youtu.be/fkX5Zy1qL7Y
https://www.programiz.com/dsa/counting-sort
https://www.geeksforgeeks.org/counting-sort/
8 - Radix Sort
8.1) Radix Sort, Taban Sıralaması olarak çevirilebilir. Sıralanacak sayıların hanelerine göre sıralama yapılır. En değersiz haneden en değerli haneye doğru sıralama yapılır. Bir dizidekei en fazla 5 haneli sayı varsa en değerli hane on binler basamağı, en değersiz hane ise birler basamağıdır.
8.2) Sıralacağım liste -> 240, 41, 20, 11, 25, 2
Kırmızı : Kontrol ettiğim hane
Öncelikle birler basamağını kontrol ediyorum - > 240, 41, 20, 11, 25, 2
Eğer karşılaştırdığımız basamakları aynı olan sayılar var ise sıralanmamış listemize uygun olarak yazarız yani solda olan yine sola yazılır.
Birler basamağına göre sıralanmış listemiz - > 240, 20, 41, 11, 2, 25
Şimdi ise onlar basamağına göre sıralayalım - > 240, 20, 41, 11, 02, 25
Onlar basamağına göre sıralanmış dizi - > 2, 11, 20, 25, 240, 40
En nihayetinde en değerli hanemizi yani yüzler basamağını sıralıyoruz - > 002, 011, 020, 025, 240, 040
Yüzler basamağına göre sıralanmış listemiz - > 2, 11, 20, 25, 40, 240
Gördüğünüz gibi listemiz sıralandı.
8.3) Performans
Kararlı mı : Evet
8.4) Algoritmanın Python ile yazılmış hali:
Kod için altta verdiğim geeksforgeeks sitesine bakabilirsiniz. Kodu yazamadım ama yazamadığım için öylesine bırakmak da istemedim. Bu yüzden geeksforgeeks'teki kodu anlatacağım. Bizim basamak sıralamalarını yapmamız için başka bir -alt- sıralama algoritmasına daha ihtiyacımız var. Bu kodda üstte de anlattığım Counting Sort kullanılmış. Kodda exp ile temsil edilen şey basamak. Göreceğiniz üzere Radix Sort fonksiyonundaki While içinde sürekli 10 ile çarpılıyor bu exp değeri. Maksimum sayının en değerli basamağına kadar giden bir While döngüsünden sonra sıralama tamamlanıyor.
8.5) Bir gif:
8.6) Yararlı Linkler
Taban Sıralaması (Radix Sort) âââ¬ââ¬Å Bilgisayar Kavramları
https://www.geeksforgeeks.org/radix-sort/
Forumda eşi olmayan bir konunun sonuna geldik. Tüm bu algoritmaları anlatan videolar çektim ve Youtube kanalıma yükledim, hızlı bir şekilde videolara ulaşmanız için oynatma listesi haline getirdim. 9 video bulunmakta ve yaklaşık 50 dakika.
Buradan ulaşabilirsiniz : https://www.youtube.com/playlist?list=PLIosuNQD8CmfFNsG7tCFma7edWr3r3p7R
Son düzenleme: