Sıralama Algoritmaları | 8 Algoritma

0x1D

Kıdemli Üye
23 Nis 2020
2,652
78
MARS


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.

4dKDtQ.png



Bahsedeceklerim

» Bubble Sort
» Selection Sort
» Insertion Sort
» Merge sort
» Quick Sort
» Heap Sort
» Counting Sort
» Radix Sort


4dKDtQ.png



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.



rNH0rM.png




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.


4dKDtQ.png



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.


4dKDtQ.png



1.3) Performans

Worst Case : Ters sıralanmış dizi (n²)
Best Case : Sıralanmış dizi (n)
Yöntem : Değiştirme
Kararlı mı : Evet


4dKDtQ.png



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.

bubble.png




4dKDtQ.png



1.5) Bubble Sort hakkında bir gif :

Bubble_sort_animation.gif



1_DOUJStF3et-GKApITUHedw.gif



4dKDtQ.png



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



rNH0rM.png




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.

4dKDtQ.png



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


4dKDtQ.png



2.3) Performans

Worst Case : Ters sıralanmış dizi (n²)
Best Case : Sıralanmış dizi (n)
Yöntem : Seçme
Kararlı mı : Hayır


4dKDtQ.png



2.4) Algoritmanın Python ile yazılmış hali:

selection.png



4dKDtQ.png



2.5) Algoritmanın akış şeması :

Selection-sort-flowchart.jpg



4dKDtQ.png



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


rNH0rM.png



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.


4dKDtQ.png



3.3) Performans

Worst Case : Ters sıralanmış dizi (n²)
Best Case : Sıralanmış dizi (n)
Yöntem : Ekleme
Kararlı mı : Evet


4dKDtQ.png



3.4) Algoritmanın Python ile yazılmış hali :

insertion.png



4dKDtQ.png



3.5) Eklemeli Sıralama'nın rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek.


Insertion_sort_animation.gif



insertionsort.png



4dKDtQ.png



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



rNH0rM.png




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.


4dKDtQ.png



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.

merge.png


İ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...

merge2.png



4dKDtQ.png



4.3) Performans
Worst Case : O(n log n)
Best Case : O(n log(n))
Yöntem : Birleştirme
Kararlı mı : Evet


4dKDtQ.png



4.4) Algoritmanın Python ile yazılmış hali.


merge.png



4dKDtQ.png



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

250px-Merge_sort_animation.gif



4dKDtQ.png



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/


rNH0rM.png



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.


4dKDtQ.png


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.


4dKDtQ.png



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


4dKDtQ.png



5.4) Algoritmanın Python ile yazılmış hali.


quick.png



4dKDtQ.png


5.5) Algoritma hakkında bir kaç grafik:

Yatay mavi çizgiler pivot:

Sorting_quicksort_anim.gif



QuickSort2.png



4dKDtQ.png



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


rNH0rM.png


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.


4dKDtQ.png


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 :

temel.png


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.

temel1.png


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.

temel2.png


Sıraları doğru olduğu için ellemiyorum ve 15 ile 25'i karşılaştıracağım.

temel3.png


23 ikisinden de büyük olduğu için ellemedim. Şimdi root yani en tepe nokta ile karşılaştırma yapacağım.

temel4.png


25>9 olduğu için yer değiştirme işlemi yaptım.

temel5.png


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.

temel6.png


Sorun yok, sıra doğru.

temel7.png


Diğer çocuğu ile karşılaştığımızda hatayı görüp yer değiştiriyoruz.

as1.png


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.

as2.png


Daha sonrasında Heap sıralanır. Üst kısımda anlattığım için tekrar yazmayacağım direkt düzenleyip göstereceğim.

as3.png


Ş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]



4dKDtQ.png



6.3) Performans

Worst Case : O(n log n)
Best Case : O(nlog n)
Yöntem : Seçme
Kararlı mı : Evet


4dKDtQ.png



6.4) Algoritmanın Python ile yazılmış hali:

heap.png



4dKDtQ.png



6.5) Heap sort'un karışık elemanları nasıl sıraladığına dair bir gif:

Sorting_heapsort_anim.gif



4dKDtQ.png



6.6) Yararlı Linkler

Kod : https://github.com/xenopeltis1/siralama-algoritmalari
https://www.geeksforgeeks.org/heap-sort/
https://youtu.be/HYLiT2wffUE


rNH0rM.png


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.


4dKDtQ.png



7.2)

Sıralayacağımız dizi:

cnt1.png


Öncelikle bu diziden max değerini bulup yeni bir dizi oluşturalım.

Max -> 8

0-8

Bu aralıkta oluşturduğum dizi:

cnt2.png


Her elemanın kaç tane bulunduğunu gösteriyor:

cnt3.png


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:

cnt4.png



4dKDtQ.png



7.3) Performans

Worst Case : O(n+k)
Best Case: O(n+k)
Yöntem : Sayma
Kararlı mı : Hayır


4dKDtQ.png


7.4) Algoritmanın Python ile yazılmış hali:

count.png



4dKDtQ.png



7.5) Güzel bir kaç gif:

2016-03-09-counting-sort.gif


Counting_Sort_Animation.gif



4dKDtQ.png


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/


rNH0rM.png


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.


4dKDtQ.png



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ı.


4dKDtQ.png



8.3) Performans

Kararlı mı : Evet


4dKDtQ.png


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.


4dKDtQ.png


8.5) Bir gif:

radix-sort-animation-o.gif



4dKDtQ.png


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:

Sort

Katılımcı Üye
14 Eki 2019
968
79
Ellerinize Sağlık. Benimde Kabuk Algoritması Hakkında Sunum Hazırlamam Gerekliydi. Bir An Gözüm Kabuk Algoritmasını Aradı :(
Bu Tür Algoritmalar Hakkında Sunum Yapacak Arkadaşlarım İçin Çok İyi Oldu. Teşekkür ederim
 

0x1D

Kıdemli Üye
23 Nis 2020
2,652
78
MARS
Eline sağlık, güzel konu olmuş

Eline sağlık, harika konu olmuş :D

ᑕᕮᗰ ΛDΓİΛП;9242279' Alıntı:
Emeğine sağlık .

Elinize emeğinize sağlık

Helall leeeğn,yapıyorsun bu sporu -_-

Eline sağlık emek kokuyor Xenopeltis.


Teşekkürler arkdaşlar :))
 

AquieLL

Kıdemli Üye
1 Tem 2014
4,036
16
aquu.php
Eline sağlık.Gerçekten kaliteli bir konu olmuş özellikle BİG-O Notasyonlarını da göstermen iyi olmuş.
 
Üst

Turkhackteam.org internet sitesi 5651 sayılı kanun’un 2. maddesinin 1. fıkrasının m) bendi ile aynı kanunun 5. maddesi kapsamında "Yer Sağlayıcı" konumundadır. İçerikler ön onay olmaksızın tamamen kullanıcılar tarafından oluşturulmaktadır. Turkhackteam.org; Yer sağlayıcı olarak, kullanıcılar tarafından oluşturulan içeriği ya da hukuka aykırı paylaşımı kontrol etmekle ya da araştırmakla yükümlü değildir. Türkhackteam saldırı timleri Türk sitelerine hiçbir zararlı faaliyette bulunmaz. Türkhackteam üyelerinin yaptığı bireysel hack faaliyetlerinden Türkhackteam sorumlu değildir. Sitelerinize Türkhackteam ismi kullanılarak hack faaliyetinde bulunulursa, site-sunucu erişim loglarından bu faaliyeti gerçekleştiren ip adresini tespit edip diğer kanıtlarla birlikte savcılığa suç duyurusunda bulununuz.