Giriş: Verileri Anlamlandırmanın Temel Taşı - Sıralama Algoritmaları
Bilgisayar bilimlerinde veri işleme, yazılım geliştirme ve genel olarak problem çözme süreçlerinin ayrılmaz bir parçası olan sıralama algoritmaları, belirli bir veri kümesini önceden tanımlanmış bir düzene (genellikle artan veya azalan) göre düzenlemek için kullanılan yöntemlerdir. Geliştirdiğimiz hemen hemen her uygulamada, ister bir e-ticaret sitesindeki ürün listelemesi, ister bir veritabanındaki kayıtların sorgulanması, isterse de bir arama motorunun sonuçları olsun, verilerin belirli bir sıraya göre sunulması hayati önem taşır. Doğru sıralama algoritmasının seçimi, uygulamanın performansı ve verimliliği üzerinde doğrudan bir etkiye sahiptir. Yanlış bir seçim, büyük veri kümeleriyle çalışırken ciddi performans darboğazlarına yol açabilirken, akıllıca bir seçim sistemin genel tepkiselliğini artırabilir.
Sıralama algoritmaları, temel olarak iki ana kategoriye ayrılabilir: karşılaştırmalı sıralama algoritmaları ve doğrusal sıralama algoritmaları. Karşılaştırmalı algoritmalar, öğeleri birbiriyle karşılaştırarak sıralama yaparken, doğrusal algoritmalar öğelerin değerlerini doğrudan kullanarak (genellikle belirli bir aralıktaki tamsayılar için) daha hızlı çalışabilir. Bu rehberde, en yaygın kullanılan ve teorik olarak önemli olan sıralama algoritmalarını detaylı bir şekilde inceleyecek, çalışma prensiplerini, zaman ve yer karmaşıklıklarını, avantajlarını ve dezavantajlarını karşılaştırmalı bir yaklaşımla ele alacağız.
Temel Sıralama Algoritmaları
Veri kümelerini düzenlemek için geliştirilmiş sayısız sıralama algoritması bulunmaktadır. Bu bölümde, en bilinen ve eğitimde sıkça karşılaşılan bazı temel sıralama algoritmalarını detaylandıracağız.
1. Kabarcık Sıralaması (Bubble Sort)
Prensip: Kabarcık sıralaması, adını en ağır elementlerin (veya değerlerin) listede yukarı doğru "kabarcık gibi" yükselmesinden alır. Listenin başından sonuna doğru yinelenen geçişler yapar. Her geçişte, bitişik öğeleri karşılaştırır ve eğer yanlış sıradalarsa yerlerini değiştirir. Bu işlem, listede hiçbir öğe değişimi yapılmayana kadar devam eder, bu da listenin sıralandığı anlamına gelir.
Çalışma Şekli: Algoritma, listenin başından başlar, ilk iki öğeyi karşılaştırır. Eğer birinci öğe ikinciden büyükse yerlerini değiştirir. Sonra ikinci ve üçüncü öğeyi, ardından üçüncü ve dördüncüyü ve bu şekilde listenin sonuna kadar devam eder. Birinci geçişin sonunda en büyük öğe listenin sonuna yerleşmiş olur. İkinci geçişte, son öğe hariç tutularak aynı işlem tekrarlanır ve bir sonraki en büyük öğe yerini bulur. Bu işlem, tüm liste sıralanana kadar devam eder.
Karmaşıklık: Kabarcık sıralamasının zaman karmaşıklığı en kötü ve ortalama durumda O(n^2)'dir. Bu, büyük veri kümeleri için çok yavaş olduğu anlamına gelir. En iyi durumda (liste zaten sıralıysa) O
olur, çünkü tek bir geçiş yeterli olur. Yer karmaşıklığı ise O(1) yani sabittir.
2. Seçmeli Sıralama (Selection Sort)
Prensip: Seçmeli sıralama, her geçişte sıralanmamış kısmın en küçük (veya en büyük) öğesini bulur ve onu sıralanmış kısmın sonuna (veya başına) yerleştirir. Bu, her adımda doğru elemanı "seçip" yerine koymak anlamına gelir.
Çalışma Şekli: Algoritma, listenin ilk konumundan başlar. Bu konumdan başlayarak listenin geri kalanındaki en küçük öğeyi arar. En küçük öğe bulunduğunda, bu öğe ile ilk konumdaki öğe yer değiştirir. Ardından, ikinci konum için aynı işlem tekrarlanır ve bu şekilde listenin sonuna kadar devam eder. Her adımda, sıralanmış kısım bir öğe artar ve sıralanmamış kısım bir öğe azalır.
Karmaşıklık: Seçmeli sıralamanın zaman karmaşıklığı, en iyi, en kötü ve ortalama durumda daima O(n^2)'dir. Bunun nedeni, her zaman tüm liste taranarak en küçük öğenin bulunması gerekmesidir. Yer karmaşıklığı O(1)'dir. Kabarcık sıralamasından daha az yer değiştirme işlemi yapar, bu da bazı durumlarda pratik bir avantaj sağlayabilir.
3. Eklemeli Sıralama (Insertion Sort)
Prensip: Eklemeli sıralama, kart destesini sıralamaya benzer bir prensiple çalışır. Her bir öğeyi, zaten sıralanmış olan kısımda doğru konumuna "ekler".
Çalışma Şekli: Algoritma, listenin ikinci öğesinden başlar (ilk öğe tek başına sıralı kabul edilir). Her bir öğeyi alır ve onu kendisinden önceki sıralanmış kısımda, kendisinden küçük tüm öğelerin sağına ve kendisinden büyük tüm öğelerin soluna yerleştirir. Bunu yapmak için, mevcut öğeyi geçici bir değişkende tutar ve sıralanmış kısımda daha büyük olan tüm öğeleri birer konum sağa kaydırır. Doğru konum bulunduğunda, mevcut öğeyi o konuma yerleştirir.
Karmaşıklık: En iyi durumda (liste zaten sıralıysa) O zaman karmaşıklığına sahiptir. Ortalama ve en kötü durumda ise O(n^2)'dir. Küçük veri kümeleri veya neredeyse sıralı veri kümeleri için oldukça verimlidir. Yer karmaşıklığı O(1)'dir.
4. Birleştirmeli Sıralama (Merge Sort)
Prensip: Birleştirmeli sıralama, "böl ve yönet" (divide and conquer) prensibine dayanan, kararlı bir sıralama algoritmasıdır. Listeyi tekrar tekrar ikiye böler, her bir yarımı bağımsız olarak sıralar ve ardından sıralanmış yarımları birleştirir.
Çalışma Şekli: Algoritma, veriyi tek öğeli alt listelere bölünene kadar özyinelemeli olarak ikiye böler. Tek öğeli listeler doğası gereği sıralıdır. Ardından, bu tek öğeli listeler ikişerli olarak birleştirilmeye başlanır. Birleştirme işlemi sırasında, iki sıralanmış alt listeden öğeler karşılaştırılarak yeni, sıralanmış bir liste oluşturulur. Bu işlem, tüm öğeler tek bir sıralanmış listede birleşene kadar devam eder.
Karmaşıklık: Birleştirmeli sıralamanın zaman karmaşıklığı en iyi, en kötü ve ortalama durumda O(n log n)'dir. Bu, O(n^2) algoritmalarına göre büyük veri kümelerinde çok daha hızlı olduğu anlamına gelir. Ancak, O yardımcı yer karmaşıklığına ihtiyaç duyar, bu da bellekte ek alan gerektirdiği anlamına gelir. Bu, bazı durumlarda bir dezavantaj olabilir.
5. Hızlı Sıralama (Quick Sort)
Prensip: Hızlı sıralama da bir "böl ve yönet" algoritmasıdır. Listedeki bir öğeyi pivot olarak seçer ve diğer tüm öğeleri pivota göre iki alt listeye ayırır: pivottan küçük olanlar bir tarafa, pivottan büyük olanlar diğer tarafa. Ardından, alt listeler özyinelemeli olarak sıralanır.
Çalışma Şekli: Algoritmanın ana adımları şunlardır:
1. Pivot Seçimi: Listeden bir öğe pivot olarak seçilir. Pivot seçimi, algoritmanın performansını büyük ölçüde etkileyebilir. Genellikle ilk, son, orta veya rastgele bir öğe seçilir. Medyan-of-three gibi daha gelişmiş pivot seçim stratejileri de kullanılabilir.
2. Bölümlendirme (Partitioning): Pivot dışındaki tüm öğeler taranır ve pivottan küçük olanlar pivotun soluna, pivottan büyük olanlar pivotun sağına yerleştirilir. Eşit olan öğeler herhangi bir tarafa gidebilir. Bu işlemin sonunda, pivot nihai sıralı konumunda olur.
3. Özyinelemeli Sıralama: Pivotun solundaki alt liste ve sağındaki alt liste ayrı ayrı hızlı sıralama ile sıralanır.
Hızlı sıralama hakkında daha fazla bilgi ve farklı pivot stratejileri için bu kaynağı inceleyebilirsiniz.
Karmaşıklık: Hızlı sıralamanın ortalama zaman karmaşıklığı O(n log n)'dir ve pratikte genellikle en hızlı sıralama algoritmalarından biridir. Ancak, en kötü durumda (örneğin, liste zaten sıralıysa ve her zaman ilk veya son öğe pivot olarak seçiliyorsa) zaman karmaşıklığı O(n^2)'ye düşebilir. Bu durum, iyi bir pivot seçim stratejisi ile önlenmeye çalışılır. Yer karmaşıklığı özyinelemeli çağrılar nedeniyle O(log n) (ortalama) ile O (en kötü) arasında değişir.
6. Yığın Sıralaması (Heap Sort)
Prensip: Yığın sıralaması, ikili yığın (binary heap) veri yapısından faydalanan karşılaştırmalı bir sıralama algoritmasıdır. Bir ikili yığın, ebeveyn düğümün her zaman çocuk düğümlerinden daha büyük (max-heap) veya daha küçük (min-heap) olduğu özel bir tam ikili ağaçtır.
Çalışma Şekli: Algoritma iki ana adımdan oluşur:
1. Yığın Oluşturma: Verilen listenin tüm öğeleri, bir max-heap (büyükten küçüğe sıralama için) veya min-heap (küçükten büyüğe sıralama için) yapısına dönüştürülür. Bu işlem genellikle O zamanda yapılır.
2. Sıralama: Yığının kök öğesi (max-heap'te en büyük öğe) alınır ve listenin sonuna yerleştirilir. Kök öğe çıkarıldıktan sonra, kalan öğelerle yeni bir yığın oluşturulur. Bu işlem, yığın boşalana kadar tekrarlanır. Her bir "kök çıkarma" işlemi O(log n) zaman alır ve n kez tekrarlanır.
Karmaşıklık: Yığın sıralamasının zaman karmaşıklığı en iyi, en kötü ve ortalama durumda daima O(n log n)'dir. Yer karmaşıklığı O(1)'dir çünkü sıralama işlemi yerinde (in-place) yapılır. Bu, hızlı sıralamanın en kötü durum performansından ve birleştirmeli sıralamanın ek alan gereksiniminden kaçınan sağlam bir algoritma olmasını sağlar.
Sıralama Algoritmalarının Karşılaştırması
Algoritma seçiminde, veri kümesinin boyutu, veri dağılımı, bellek kısıtlamaları ve kararlılık gibi faktörler göz önünde bulundurulmalıdır. Aşağıda, incelediğimiz algoritmaların temel özelliklerinin bir karşılaştırması bulunmaktadır:
Zaman Karmaşıklığı Özeti (Büyük Veri Kümeleri İçin):
Sonuç
Sıralama algoritmaları, bilgisayar bilimlerinin temelini oluşturan ve pratikte karşılaşılan birçok problemin çözümünde kilit rol oynayan güçlü araçlardır. Her algoritmanın kendine özgü bir çalışma prensibi, avantajları ve dezavantajları bulunmaktadır. "En iyi" sıralama algoritması diye bir şey yoktur; seçim, uygulamanın özel gereksinimlerine ve veri setinin özelliklerine bağlıdır.
Küçük veri kümeleri için basit O(n^2) algoritmaları (örneğin Eklemeli Sıralama) yeterli hatta daha hızlı olabilirken, büyük veri kümeleri ve yüksek performans gerektiren sistemlerde O(n log n) algoritmaları (Hızlı Sıralama, Birleştirmeli Sıralama, Yığın Sıralaması) tercih edilmelidir. Hızlı sıralama genellikle ortalama durumda en hızlı performansı sunarken, Birleştirmeli Sıralama kararlılığı ve garantili O(n log n) performansı ile öne çıkar. Yığın Sıralaması ise, yerinde çalışabilmesi ve O(n log n) garanti etmesiyle güvenilir bir alternatiftir.
Veri setinin boyutu, belleğe erişim maliyeti, kararlılık gereksinimi ve önceden kısmen sıralanmış olma durumu gibi faktörleri dikkatlice değerlendirerek projenize en uygun sıralama algoritmasını seçmek, yazılımınızın verimliliği ve performansı için kritik öneme sahiptir. Bu rehber, karar verme sürecinizde size yol göstermeyi amaçlamaktadır.
Bilgisayar bilimlerinde veri işleme, yazılım geliştirme ve genel olarak problem çözme süreçlerinin ayrılmaz bir parçası olan sıralama algoritmaları, belirli bir veri kümesini önceden tanımlanmış bir düzene (genellikle artan veya azalan) göre düzenlemek için kullanılan yöntemlerdir. Geliştirdiğimiz hemen hemen her uygulamada, ister bir e-ticaret sitesindeki ürün listelemesi, ister bir veritabanındaki kayıtların sorgulanması, isterse de bir arama motorunun sonuçları olsun, verilerin belirli bir sıraya göre sunulması hayati önem taşır. Doğru sıralama algoritmasının seçimi, uygulamanın performansı ve verimliliği üzerinde doğrudan bir etkiye sahiptir. Yanlış bir seçim, büyük veri kümeleriyle çalışırken ciddi performans darboğazlarına yol açabilirken, akıllıca bir seçim sistemin genel tepkiselliğini artırabilir.
Sıralama algoritmaları, temel olarak iki ana kategoriye ayrılabilir: karşılaştırmalı sıralama algoritmaları ve doğrusal sıralama algoritmaları. Karşılaştırmalı algoritmalar, öğeleri birbiriyle karşılaştırarak sıralama yaparken, doğrusal algoritmalar öğelerin değerlerini doğrudan kullanarak (genellikle belirli bir aralıktaki tamsayılar için) daha hızlı çalışabilir. Bu rehberde, en yaygın kullanılan ve teorik olarak önemli olan sıralama algoritmalarını detaylı bir şekilde inceleyecek, çalışma prensiplerini, zaman ve yer karmaşıklıklarını, avantajlarını ve dezavantajlarını karşılaştırmalı bir yaklaşımla ele alacağız.
Temel Sıralama Algoritmaları
Veri kümelerini düzenlemek için geliştirilmiş sayısız sıralama algoritması bulunmaktadır. Bu bölümde, en bilinen ve eğitimde sıkça karşılaşılan bazı temel sıralama algoritmalarını detaylandıracağız.
1. Kabarcık Sıralaması (Bubble Sort)
Prensip: Kabarcık sıralaması, adını en ağır elementlerin (veya değerlerin) listede yukarı doğru "kabarcık gibi" yükselmesinden alır. Listenin başından sonuna doğru yinelenen geçişler yapar. Her geçişte, bitişik öğeleri karşılaştırır ve eğer yanlış sıradalarsa yerlerini değiştirir. Bu işlem, listede hiçbir öğe değişimi yapılmayana kadar devam eder, bu da listenin sıralandığı anlamına gelir.
Çalışma Şekli: Algoritma, listenin başından başlar, ilk iki öğeyi karşılaştırır. Eğer birinci öğe ikinciden büyükse yerlerini değiştirir. Sonra ikinci ve üçüncü öğeyi, ardından üçüncü ve dördüncüyü ve bu şekilde listenin sonuna kadar devam eder. Birinci geçişin sonunda en büyük öğe listenin sonuna yerleşmiş olur. İkinci geçişte, son öğe hariç tutularak aynı işlem tekrarlanır ve bir sonraki en büyük öğe yerini bulur. Bu işlem, tüm liste sıralanana kadar devam eder.
Kod:
function bubbleSort(array):
n = length(array)
for i from 0 to n-2:
swapped = false
for j from 0 to n-i-2:
if array[j] > array[j+1]:
swap(array[j], array[j+1])
swapped = true
if not swapped:
break // Eğer bu geçişte hiç yer değiştirme olmadıysa, liste sıralanmıştırKarmaşıklık: Kabarcık sıralamasının zaman karmaşıklığı en kötü ve ortalama durumda O(n^2)'dir. Bu, büyük veri kümeleri için çok yavaş olduğu anlamına gelir. En iyi durumda (liste zaten sıralıysa) O
olur, çünkü tek bir geçiş yeterli olur. Yer karmaşıklığı ise O(1) yani sabittir.2. Seçmeli Sıralama (Selection Sort)
Prensip: Seçmeli sıralama, her geçişte sıralanmamış kısmın en küçük (veya en büyük) öğesini bulur ve onu sıralanmış kısmın sonuna (veya başına) yerleştirir. Bu, her adımda doğru elemanı "seçip" yerine koymak anlamına gelir.
Çalışma Şekli: Algoritma, listenin ilk konumundan başlar. Bu konumdan başlayarak listenin geri kalanındaki en küçük öğeyi arar. En küçük öğe bulunduğunda, bu öğe ile ilk konumdaki öğe yer değiştirir. Ardından, ikinci konum için aynı işlem tekrarlanır ve bu şekilde listenin sonuna kadar devam eder. Her adımda, sıralanmış kısım bir öğe artar ve sıralanmamış kısım bir öğe azalır.
Kod:
function selectionSort(array):
n = length(array)
for i from 0 to n-2:
minIndex = i
for j from i+1 to n-1:
if array[j] < array[minIndex]:
minIndex = j
if minIndex != i:
swap(array[i], array[minIndex])Karmaşıklık: Seçmeli sıralamanın zaman karmaşıklığı, en iyi, en kötü ve ortalama durumda daima O(n^2)'dir. Bunun nedeni, her zaman tüm liste taranarak en küçük öğenin bulunması gerekmesidir. Yer karmaşıklığı O(1)'dir. Kabarcık sıralamasından daha az yer değiştirme işlemi yapar, bu da bazı durumlarda pratik bir avantaj sağlayabilir.
3. Eklemeli Sıralama (Insertion Sort)
Prensip: Eklemeli sıralama, kart destesini sıralamaya benzer bir prensiple çalışır. Her bir öğeyi, zaten sıralanmış olan kısımda doğru konumuna "ekler".
Çalışma Şekli: Algoritma, listenin ikinci öğesinden başlar (ilk öğe tek başına sıralı kabul edilir). Her bir öğeyi alır ve onu kendisinden önceki sıralanmış kısımda, kendisinden küçük tüm öğelerin sağına ve kendisinden büyük tüm öğelerin soluna yerleştirir. Bunu yapmak için, mevcut öğeyi geçici bir değişkende tutar ve sıralanmış kısımda daha büyük olan tüm öğeleri birer konum sağa kaydırır. Doğru konum bulunduğunda, mevcut öğeyi o konuma yerleştirir.
Kod:
function insertionSort(array):
n = length(array)
for i from 1 to n-1:
key = array[i]
j = i - 1
while j >= 0 and array[j] > key:
array[j+1] = array[j]
j = j - 1
array[j+1] = keyKarmaşıklık: En iyi durumda (liste zaten sıralıysa) O
zaman karmaşıklığına sahiptir. Ortalama ve en kötü durumda ise O(n^2)'dir. Küçük veri kümeleri veya neredeyse sıralı veri kümeleri için oldukça verimlidir. Yer karmaşıklığı O(1)'dir.4. Birleştirmeli Sıralama (Merge Sort)
Prensip: Birleştirmeli sıralama, "böl ve yönet" (divide and conquer) prensibine dayanan, kararlı bir sıralama algoritmasıdır. Listeyi tekrar tekrar ikiye böler, her bir yarımı bağımsız olarak sıralar ve ardından sıralanmış yarımları birleştirir.
Çalışma Şekli: Algoritma, veriyi tek öğeli alt listelere bölünene kadar özyinelemeli olarak ikiye böler. Tek öğeli listeler doğası gereği sıralıdır. Ardından, bu tek öğeli listeler ikişerli olarak birleştirilmeye başlanır. Birleştirme işlemi sırasında, iki sıralanmış alt listeden öğeler karşılaştırılarak yeni, sıralanmış bir liste oluşturulur. Bu işlem, tüm öğeler tek bir sıralanmış listede birleşene kadar devam eder.
Kod:
function mergeSort(array):
n = length(array)
if n <= 1:
return array
mid = floor(n / 2)
left = array[0 to mid-1]
right = array[mid to n-1]
left = mergeSort(left)
right = mergeSort(right)
return merge(left, right)
function merge(left, right):
result = empty_list
while left is not empty and right is not empty:
if first(left) <= first(right):
add first(left) to result
remove first(left)
else:
add first(right) to result
remove first(right)
while left is not empty:
add first(left) to result
remove first(left)
while right is not empty:
add first(right) to result
remove first(right)
return resultKarmaşıklık: Birleştirmeli sıralamanın zaman karmaşıklığı en iyi, en kötü ve ortalama durumda O(n log n)'dir. Bu, O(n^2) algoritmalarına göre büyük veri kümelerinde çok daha hızlı olduğu anlamına gelir. Ancak, O
yardımcı yer karmaşıklığına ihtiyaç duyar, bu da bellekte ek alan gerektirdiği anlamına gelir. Bu, bazı durumlarda bir dezavantaj olabilir.5. Hızlı Sıralama (Quick Sort)
Prensip: Hızlı sıralama da bir "böl ve yönet" algoritmasıdır. Listedeki bir öğeyi pivot olarak seçer ve diğer tüm öğeleri pivota göre iki alt listeye ayırır: pivottan küçük olanlar bir tarafa, pivottan büyük olanlar diğer tarafa. Ardından, alt listeler özyinelemeli olarak sıralanır.
Çalışma Şekli: Algoritmanın ana adımları şunlardır:
1. Pivot Seçimi: Listeden bir öğe pivot olarak seçilir. Pivot seçimi, algoritmanın performansını büyük ölçüde etkileyebilir. Genellikle ilk, son, orta veya rastgele bir öğe seçilir. Medyan-of-three gibi daha gelişmiş pivot seçim stratejileri de kullanılabilir.
2. Bölümlendirme (Partitioning): Pivot dışındaki tüm öğeler taranır ve pivottan küçük olanlar pivotun soluna, pivottan büyük olanlar pivotun sağına yerleştirilir. Eşit olan öğeler herhangi bir tarafa gidebilir. Bu işlemin sonunda, pivot nihai sıralı konumunda olur.
3. Özyinelemeli Sıralama: Pivotun solundaki alt liste ve sağındaki alt liste ayrı ayrı hızlı sıralama ile sıralanır.
Hızlı sıralama hakkında daha fazla bilgi ve farklı pivot stratejileri için bu kaynağı inceleyebilirsiniz.
Kod:
function quickSort(array, low, high):
if low < high:
pivotIndex = partition(array, low, high)
quickSort(array, low, pivotIndex - 1)
quickSort(array, pivotIndex + 1, high)
function partition(array, low, high):
pivot = array[high] // Genellikle son eleman pivot seçilir
i = low - 1
for j from low to high - 1:
if array[j] <= pivot:
i = i + 1
swap(array[i], array[j])
swap(array[i + 1], array[high])
return i + 1Karmaşıklık: Hızlı sıralamanın ortalama zaman karmaşıklığı O(n log n)'dir ve pratikte genellikle en hızlı sıralama algoritmalarından biridir. Ancak, en kötü durumda (örneğin, liste zaten sıralıysa ve her zaman ilk veya son öğe pivot olarak seçiliyorsa) zaman karmaşıklığı O(n^2)'ye düşebilir. Bu durum, iyi bir pivot seçim stratejisi ile önlenmeye çalışılır. Yer karmaşıklığı özyinelemeli çağrılar nedeniyle O(log n) (ortalama) ile O
(en kötü) arasında değişir.6. Yığın Sıralaması (Heap Sort)
Prensip: Yığın sıralaması, ikili yığın (binary heap) veri yapısından faydalanan karşılaştırmalı bir sıralama algoritmasıdır. Bir ikili yığın, ebeveyn düğümün her zaman çocuk düğümlerinden daha büyük (max-heap) veya daha küçük (min-heap) olduğu özel bir tam ikili ağaçtır.
Çalışma Şekli: Algoritma iki ana adımdan oluşur:
1. Yığın Oluşturma: Verilen listenin tüm öğeleri, bir max-heap (büyükten küçüğe sıralama için) veya min-heap (küçükten büyüğe sıralama için) yapısına dönüştürülür. Bu işlem genellikle O
zamanda yapılır.2. Sıralama: Yığının kök öğesi (max-heap'te en büyük öğe) alınır ve listenin sonuna yerleştirilir. Kök öğe çıkarıldıktan sonra, kalan öğelerle yeni bir yığın oluşturulur. Bu işlem, yığın boşalana kadar tekrarlanır. Her bir "kök çıkarma" işlemi O(log n) zaman alır ve n kez tekrarlanır.
Kod:
function heapSort(array):
n = length(array)
// Yığını oluştur (max-heap)
for i from floor(n/2) - 1 down to 0:
heapify(array, n, i)
// Öğeleri teker teker yığından çıkar
for i from n-1 down to 0:
swap(array[0], array[i]) // Mevcut kökü sona taşı
heapify(array, i, 0) // Kalan yığında heap özelliğini yeniden sağla
function heapify(array, n, i):
largest = i // Kökü en büyük olarak başlat
left = 2 * i + 1
right = 2 * i + 2
// Sol çocuk kökten büyükse
if left < n and array[left] > array[largest]:
largest = left
// Sağ çocuk şu anki en büyükten büyükse
if right < n and array[right] > array[largest]:
largest = right
// En büyük kök değilse
if largest != i:
swap(array[i], array[largest])
heapify(array, n, largest)Karmaşıklık: Yığın sıralamasının zaman karmaşıklığı en iyi, en kötü ve ortalama durumda daima O(n log n)'dir. Yer karmaşıklığı O(1)'dir çünkü sıralama işlemi yerinde (in-place) yapılır. Bu, hızlı sıralamanın en kötü durum performansından ve birleştirmeli sıralamanın ek alan gereksiniminden kaçınan sağlam bir algoritma olmasını sağlar.
Sıralama Algoritmalarının Karşılaştırması
Algoritma seçiminde, veri kümesinin boyutu, veri dağılımı, bellek kısıtlamaları ve kararlılık gibi faktörler göz önünde bulundurulmalıdır. Aşağıda, incelediğimiz algoritmaların temel özelliklerinin bir karşılaştırması bulunmaktadır:
- Kabarcık Sıralaması (Bubble Sort): Çok basit, O(n^2) kötü/ortalama, O en iyi durum zaman, O(1) yer, kararlı.
- Seçmeli Sıralama (Selection Sort): Basit, O(n^2) tüm durumlar zaman, O(1) yer, kararlı değil (genellikle).
- Eklemeli Sıralama (Insertion Sort): Basit, O(n^2) kötü/ortalama, O en iyi durum zaman, O(1) yer, kararlı. Küçük veya neredeyse sıralı veri setleri için iyi.
- Birleştirmeli Sıralama (Merge Sort): O(n log n) tüm durumlar zaman, O yardımcı yer, kararlı. Büyük veri kümeleri ve harici sıralama için ideal.
- Hızlı Sıralama (Quick Sort): Ortalama O(n log n) zaman (pratikte genellikle en hızlı), O(n^2) kötü durum zaman, O(log n) ortalama yer, O kötü durum yer, kararlı değil. Geniş kullanım alanı.
- Yığın Sıralaması (Heap Sort): O(n log n) tüm durumlar zaman, O(1) yer, kararlı değil. Güvenilir ve yerinde çalışan bir algoritma.
Zaman Karmaşıklığı Özeti (Büyük Veri Kümeleri İçin):
Kod:
Algoritma En İyi Durum Ortalama Durum En Kötü Durum
--------------------- --------------- -------------------- ---------------
Bubble Sort O(n) O(n^2) O(n^2)
Selection Sort O(n^2) O(n^2) O(n^2)
Insertion Sort O(n) O(n^2) O(n^2)
Merge Sort O(n log n) O(n log n) O(n log n)
Quick Sort O(n log n) O(n log n) O(n^2)
Heap Sort O(n log n) O(n log n) O(n log n)Sonuç
Sıralama algoritmaları, bilgisayar bilimlerinin temelini oluşturan ve pratikte karşılaşılan birçok problemin çözümünde kilit rol oynayan güçlü araçlardır. Her algoritmanın kendine özgü bir çalışma prensibi, avantajları ve dezavantajları bulunmaktadır. "En iyi" sıralama algoritması diye bir şey yoktur; seçim, uygulamanın özel gereksinimlerine ve veri setinin özelliklerine bağlıdır.
Küçük veri kümeleri için basit O(n^2) algoritmaları (örneğin Eklemeli Sıralama) yeterli hatta daha hızlı olabilirken, büyük veri kümeleri ve yüksek performans gerektiren sistemlerde O(n log n) algoritmaları (Hızlı Sıralama, Birleştirmeli Sıralama, Yığın Sıralaması) tercih edilmelidir. Hızlı sıralama genellikle ortalama durumda en hızlı performansı sunarken, Birleştirmeli Sıralama kararlılığı ve garantili O(n log n) performansı ile öne çıkar. Yığın Sıralaması ise, yerinde çalışabilmesi ve O(n log n) garanti etmesiyle güvenilir bir alternatiftir.
Veri setinin boyutu, belleğe erişim maliyeti, kararlılık gereksinimi ve önceden kısmen sıralanmış olma durumu gibi faktörleri dikkatlice değerlendirerek projenize en uygun sıralama algoritmasını seçmek, yazılımınızın verimliliği ve performansı için kritik öneme sahiptir. Bu rehber, karar verme sürecinizde size yol göstermeyi amaçlamaktadır.
