Algoritma ve Veri Yapıları

Sıralama (Sorting) işlemlerinde çalışma zamanı; elemanların sayısına,
ilk durumdaki dizilişe ve algoritmaya bağlıdır.


Best Case: Elemanlar zaten sıralı ise, linear time olarak adlandırılır.
Worst Case: Elemanlar ters olarak sıralı ise, quadratic time olarak alandırılır.
Avarage Case: 

---------------------------------------------------
Insertion Sort (eklemeli sıralama algoritması):
Düzensiz olan dizi elemanlarını tek tek ele alarak yapılan sıralamadır.
Elemanlar sıralamadaki uygun yere yerleştirildiği için eklemeli denilmiştir. 
Örnek olarak; 9 5 1 8 6 
küçükten büyüğe doğru bir sıralama yapılmak istendiğinde, ilk iki elemana
baktığımızda 9 ve 5'in yeri değiştirilir.
5 9 1 8 6
daha sonra 2. ve 3. elemana bakıldığında, 9 ve 1'in yeri değiştirilir.
5 1 9 8 6
3. ve 4. elemana baktığımızda 8 ve 9'un yeri değişir.
5 1 8 9 6
bu işlem doğru sıralama gerçekleşinceye kadar devam eder.


---------------------------------------------------
Quick Sort (hızlı sıralama algoritması):
Sıralanacak olan dizideki orta noktada (mean) bulunan bir sayıyı seçerek,
diğer bütün sayıları bu sayıdan büyük veya küçüktür diye sınıflandırarak
sıralama yapmayı hedefler. Bu açıdan böl ve fethet (divide and conquere) yaklaşımıdır.
Ayrıca seçilen orta noktaya eksen (pivot) ismi de verilir çünkü diğer sayılar
bu sayının ekseninde sıralanacaktır.
Esasında ortadaki bir sayıdan ziyade bu orta kısma yakın bir sayı da olabilir.
Örnek olarak; 5 7 2 9 6 1 4 7
İlk olarak dizinin ortasındaki sayıyı buluyoruz. 8 elamanlı olduğu için 4. elemanı
yani 9'u seçiyoruz.
Bütün sayılar 9'dan küçük olduğu için sıralama şu şekilde oldu;
5 7 2 6 1 4 7 9
Şimdi 9'u en sağa atık ve elimizdeki dizi 5 7 2 6 1 4 7 olarak kaldı.
Aynı işlemi bunun için yapıyoruz, yani ortadaki sayıyı seçiyoruz, burad bu sayı 6
Dizideki sayıları 6'dan büyük ve 6'dan küçük diye sıralarsak;
5 2 1 4 (6) 7 7
Şimdi 6'dan büyük ve 6'dan küçük sayılar için de aynı algoritmayı uygulayacağız.
Elimizde 2 dizi var, 5 2 1 4 ve 7 7
7 7 dizisinde bir değişikli olmayacak.
5 2 1 4 dizisinin ortasındaki elemanı seçtiğimizde bu 2'dir.
1 (2) 4 5 şeklinde düzenleme yaparsak elimizde 1 ve 4 5 şeklinde 2 dizi oldu.
1, 1 olarak kalacak. 4 5 dizisi sıralı. O yüzden bu diziyi birleştiriyoruz ve
ortaya 1 2 4 5 dizisi çıkıyor.
Şimdi biraz yukarı kısıma gidiyoruz. 1 2 4 5 dizisinin geldiği yer,
5 2 1 4 (6) 7 7 dizisinde 6'nın solunda kalan diziydi. Burada da birleştirme yaparsak,
1 2 4 5 6 7 7 olur.
1 2 4 5 6 7 7 dizisinin geldiği yer de 5 7 2 6 1 4 7 9 dizisinde 9'dan küçük
olan soldaki diziydi. Burada da sıralama yaparsak;
1 2 4 5 6 7 7 9 olur.


---------------------------------------------------
Selection Sort (seçerek sıralama algoritması):
Her adımda, dizideki en küçük elemanın nerede olduğunu bulur. Bu sayı ile
dizinin başındaki sayıyı yer değiştirerek, en küçük sayılar seçilerek başa
atılmış olur.
Örnek olarak; 5 7 2 9 6 1 3 7
i = 0 olarak atadık.
dizideki i sırasından sonraki en küçük sayının yerini buluyoruz.
Bu dizideki en küçük sayı 1'dir ve 5.sıradadır. (dizinin ilk elemanı 0. elemandır)
i sırasındaki sayıyı, bu sayı ile yer değiştiriyoruz. Yani 0. sıradaki sayı ile (5)
dizinin en küçük elemanını (1) yer değiştiriyoruz.
1 7 2 9 6 5 3 7
ardından i'yi 1 arttırıyoruz ve aynı işlemi tekrar yapıyoruz. Şöyle ki;
i = 1 olarak atadık.
dizideki i sırasından sonraki en küçük sayının yerini buluyoruz.
Kalan dizideki en küçük sayı 2'dir ve 2.sıradadır.
7 ile 2'yi yer değiştiriyoruz.
1 2 7 9 6 5 3 7
Aynı şekilde devam edersek;
1 2 3 9 6 5 7 7
1 2 3 5 6 9 7 7
1 2 3 5 6 7 9 7
1 2 3 5 6 7 7 9

---------------------------------------------------
Heap Sort (yığınlama sıralaması) :
Ağacın en üstündeki sayı alınarak sıralama işlemi yapılır.
Yığın ağacında en büyük sayı her zaman en üstte olmalıdır.
Örnek olarak; 5 12 20 18 4 3 sıralanmak istensin.
En büyük eleman 20 olduğu için köktedir ( root )
                        20
        12                              18  
5               4               3


20 değeri alınarak, sonuç dizisinin ilk elemanı yapılırsa,
ve sonra geriye kalan sayılar tekrar yığınlanırsa ( heapify ),
ve bu işlem kalmayana kadar tekrarlanırsa, sonuç dizisindeki veriler sıralanmış olur.
20 değerini ağaçtan sildikten sonra kalan verileri yığınlarsak, en üstteki sayı 18 olur
ve sonuç kümesi 20 18 olmuş olur.
Aynı işlemler tekrarlanır.
Bu sayılar ilk başta verilmiş sayıların sıralanmış hali yani 20 18 12 5 4 3 olur.


---------------------------------------------------
Priority Queue (öncelik sırası):
Klasik kuyruklar (queue) üzerine öncelik değerinin eklenmesi ile elde edilen
veri yapısının ismidir.
Normalde kuyruklar FIFO (first in first out) mantığı ile çalışır.
Yani örneğin bilet sırasındaki gibi en önde olan, kuyruktan ilk çıkar.
Son gelen ise bilete en son ulaşır.
Priorty Queue işlemlerinde ise bu sırada bekleyenlerden,
en öncelikli kişinin ilk erişmesi beklenir.
Örnek olarak;
Kişi No	        Öncelik
1	        5
2	        3
3       	1
4       	2
5	        4
olduğunu düşünelim.

Öncelik sırasına göre kişi no'larını sıralarsak, 1 5 2 4 3 olur.
Bunu, kişlieri öncelik sırasına göre sort etme ardından da queue gibi
veri yapısını işlemek olarak düşünebiliriz.
Aynı öncelik sırasından birden fazla kişi varsa, bu sefer fifo mantığı
ile işlem yapabiliriz.


---------------------------------------------------
ADT - Abstract Data Type (soyut veri tipleri)
Bir grup veriyi ve bu veri üzerinde yapılabilecek işlemleri düzenleyen yapının adıdır.
Soyutluk, veri yapısının bir tasarım olması ve kullanıcı için, yapının içinin tamamen soyut olması,
kullanan kişilerin bu veri tipinin uygulama detayları ile ilgili bilgisinin olmasını gerektirmemesidir.
Örnek soyut veri tipi olarak, linked list, stack, queue sayılabilir.

ADT’nin (abstract data types) daha verimli olabilmesi için özellikle
nesne yönelimli programlama dillerinde, her tip nesneyi alabilecek yapıda olması önerilir.
Bu sayede çok şekilcilik (polymorphism) sağlanmış olur ve stack içine
istenilen tipten veri konulabilir. Diğer bir yöntem ise stack tanımında template kullanmaktır.
Bu sayede bütün stack elemanları tek bir tip olacak ancak tip tanımı stack oluşturulurken verilmiş olacaktır.

---------------------------------------------------
Stack (yığın):
Tek taraflı giriş ve çıkışlara açık olan. İlk giren son çıkar LIFO (Last in First Out)
mantığı ile çalışan bir ADT örneğidir.
Temelde iki veya üç fonksiyonu bulunur bunlar:
Push -> Stack içerisine bir bilgi koymaya (Stack’in en tepesine koyar)
Pop -> Stack içerisinden bir bilgi almaya (Stack’in en tepesinden alır)
Top -> Stack’in en tepesindeki bilgiyi alır ancak stackten çıkartmaz sadece okur(lifo)

Temel olarak stack, bir array veya Linked List üzerine inşa edilebilirler.
Örnek olarak bir dizi üzerine inşa edilen stack için bir değişken,
dizide o anda kaç değer olduğunu tutacak ve her pop işleminden sonra bu değer azaltılırken,
her push işleminden sonra arttırılacaktır.
Benzer uygulama linked list üzerinde yapılırsa, pop işlemiyle sondan
bir düğüm silinecek veya push işlemi ile sona bir düğüm eklenecektir.


---------------------------------------------------
Singly Linked List (tekli bağlı liste):
{ http://dubluve.net/2013/01/12/c-programlama-dilinde-bagli-listeler/ }
{ http://bilgisayarkavramlari.sadievrenseker.com/2007/05/03/linked-list-linkli-liste-veya-bagli-liste/ }


---------------------------------------------------
Queues (kuyruklar):
{ http://bilgisayarkavramlari.sadievrenseker.com/2008/04/16/sira-queue/ }

---------------------------------------------------
Double-Ended Queue (çift sıralı kuyruklar):
{ http://bilgisayarkavramlari.sadievrenseker.com/2009/04/06/cift-uclu-sira-double-ended-queue/ }

---------------------------------------------------
Trees (ağaçlar):
{ http://bilgisayarkavramlari.sadievrenseker.com/2008/05/07/agaclar-tree/ }

---------------------------------------------------
Binary Tree (ikili ağaçlar):
{ http://bilgisayarkavramlari.sadievrenseker.com/2008/05/07/ikili-agac-binary-tree/ }

---------------------------------------------------
Hashing (özetleme fonksiyonları):
{ http://bilgisayarkavramlari.sadievrenseker.com/2008/05/26/ozetleme-fonksiyonlari-hash-function/ }

---------------------------------------------------
Binary Search Trees (ikili arama ağaçları):
Searching, Insertion, Deletion
{ http://bilgisayarkavramlari.sadievrenseker.com/2008/05/07/ikili-arama-agaci-binary-search-tree/ }

---------------------------------------------------
Red-Black Trees (kırmızı siyah ağaçları):
Properties, Rotations, Insertion, Deletion
{ http://bilgisayarkavramlari.sadievrenseker.com/2009/12/27/kirmizi-siyah-agaclari-red-black-trees/ }

---------------------------------------------------
Trie (metin ağacı):
{ http://bilgisayarkavramlari.sadievrenseker.com/2008/05/14/trie-metin-agaci/ }