THT DUYURU

Algoritma Algoritma geliştirme için gerekli tekniklerin paylaşıldığı alandır.

Seçenekler

Sıralama Algoritmaları | 8 Algoritma

0x1D - ait Kullanıcı Resmi (Avatar)
Yazılımcı
Üyelik tarihi:
04/2020
Nereden:
a
Yaş:
100
Mesajlar:
2.319
Konular:
381
Teşekkür (Etti):
731
Teşekkür (Aldı):
1753
Ticaret:
(0) %
24
4638
03-12-2020 20:29
#1


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 (n)
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 (n)
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/b...n/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 (n)
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(n))
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?lis...Fma7edWr3r3p7R

Konu 0x1D tarafından (03-12-2020 20:41 Saat 20:41 ) değiştirilmiştir.
`TR0GRES - ait Kullanıcı Resmi (Avatar)
Katılımcı Üye
Üyelik tarihi:
03/2020
Nereden:
\U0001F606
Mesajlar:
347
Konular:
32
Teşekkür (Etti):
269
Teşekkür (Aldı):
248
Ticaret:
(0) %
03-12-2020 20:35
#2
Ellerine Sağlık ,
---------------------
Mᥙstᥲfᥲ Kᥱmᥲᥣ ATATÜRK





- Teşekkür etti.
Slientname - ait Kullanıcı Resmi (Avatar)
Heyk Meyk Yok
Üyelik tarihi:
10/2019
Yaş:
19
Mesajlar:
711
Konular:
21
Teşekkür (Etti):
102
Teşekkür (Aldı):
512
Ticaret:
(0) %
03-12-2020 20:37
#3
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
- Teşekkür etti.
ѕeleɴια - ait Kullanıcı Resmi (Avatar)
Anka Underground (Çaylak)
Üyelik tarihi:
05/2018
Nereden:
SQLİnjection
Mesajlar:
1.553
Konular:
185
Teşekkür (Etti):
355
Teşekkür (Aldı):
1409
Ticaret:
(0) %
03-12-2020 20:45
#4
Eline sağlık Xeno bol şans ,)
---------------------
Tanımayanlar için baysiberbela
- Teşekkür etti.
x4807 - ait Kullanıcı Resmi (Avatar)
Nick
Üyelik tarihi:
08/2019
Nereden:
+
Mesajlar:
924
Konular:
105
Teşekkür (Etti):
1867
Teşekkür (Aldı):
956
Ticaret:
(0) %
03-12-2020 20:49
#5
Eline sağlık, güzel konu olmuş
- Teşekkür etti.
Ego1st - ait Kullanıcı Resmi (Avatar)
Yazılımcı
Üyelik tarihi:
03/2018
Mesajlar:
1.088
Konular:
98
Ticaret:
(0) %
03-12-2020 21:02
#6
Eline sağlık, harika konu olmuş
- Teşekkür etti.
BÖKE - ait Kullanıcı Resmi (Avatar)
İstihbarat Tim Lider Yardımcısı
Üyelik tarihi:
08/2016
Mesajlar:
8.530
Konular:
1232
Teşekkür (Etti):
979
Teşekkür (Aldı):
2808
Ticaret:
(0) %
03-12-2020 21:14
#7
Emeğine sağlık .
---------------------
- Teşekkür etti.
maj344 - ait Kullanıcı Resmi (Avatar)
Tamamen Askıya Alındı
Üyelik tarihi:
02/2019
Mesajlar:
277
Konular:
28
Teşekkür (Etti):
999
Teşekkür (Aldı):
152
Ticaret:
(0) %
03-12-2020 21:28
#8
Helall leeeğn,yapıyorsun bu sporu
- Teşekkür etti.
Voldemort - ait Kullanıcı Resmi (Avatar)
Nagini
Üyelik tarihi:
04/2020
Mesajlar:
225
Konular:
61
Teşekkür (Etti):
174
Teşekkür (Aldı):
437
Ticaret:
(0) %
03-12-2020 21:33
#9
Elinize emeğinize sağlık
---------------------



- Teşekkür etti.
kanserojen - ait Kullanıcı Resmi (Avatar)
İstihbaratçı
Üyelik tarihi:
12/2018
Mesajlar:
862
Konular:
90
Teşekkür (Etti):
764
Teşekkür (Aldı):
1215
Ticaret:
(0) %
04-12-2020 11:19
#10
Eline sağlık emek kokuyor Xenopeltis.
---------------------
𝔦𝔰𝔱𝔦𝔥𝔟𝔞𝔯𝔞𝔱 𝔱𝔦𝔪𝔦

"Squ4LL
- Teşekkür etti.

Bookmarks


« Önceki Konu | Sonraki Konu »
Seçenekler