Selection Sort Algoritması

Selection Sort Açıklaması

Selection Sort, dizideki en küçük elemanı bulup başa yerleştiren bir sıralama algoritmasıdır. Bu algoritma, diziyi sıralı ve sırasız olmak üzere iki bölüme ayırır. Her adımda, sırasız bölümdeki en küçük elemanı bulur ve sıralı bölümün sonuna ekler. ## Çalışma Prensibi: 1. Dizinin ilk elemanını geçici olarak en küçük kabul eder. 2. Dizinin geri kalanında daha küçük bir eleman arar. 3. Daha küçük bir eleman bulunursa, bu elemanı yeni en küçük olarak işaretler. 4. Tarama tamamlandıktan sonra, bulunan en küçük elemanı dizinin başıyla takas eder. 5. Sıralı bölümü bir eleman artırır (ilk elemanı artık sıralı kabul eder). 6. Bu işlemleri, sırasız bölüm bitene kadar tekrarlar. ## Önemli Özellikler: 1. **Takas Optimizasyonu**: Minimum eleman zaten doğru konumdaysa takas yapılmaz. 2. **Kararsız Sıralama**: Eşit değere sahip elemanların orijinal sırası korunmayabilir. 3. **Karşılaştırma Sayısı**: Her zaman n*(n-1)/2 karşılaştırma yapar. 4. **Takas Sayısı**: En fazla (n-1) takas işlemi gerçekleştirir, bu da Bubble Sort'tan daha az takas demektir. Selection Sort, veri kümesinin büyüklüğünden bağımsız olarak her zaman aynı sayıda adım atar, bu nedenle en iyi, ortalama ve en kötü durum karmaşıklıkları aynıdır: O(n²).

Kod Örnekleri

Selection Sort algoritmasının farklı programlama dillerindeki uygulamaları aşağıda verilmiştir. Her örnek, algoritmanın optimize edilmiş versiyonunu içerir ve detaylı açıklamalarla sunulmuştur.

Selection Sort - JavaScript

1/**
2 * Selection Sort implementation for JavaScript arrays
3 * @param {Array} arr - The array to sort
4 * @returns {Array} - A new sorted array
5 */
6function selectionSort(arr) {
7  // Create a copy to avoid modifying the original array
8  const result = [...arr];
9  const n = result.length;
10  
11  // Outer loop - each iteration places one element in its final position
12  for (let i = 0; i < n - 1; i++) {
13    // Assume the current index has the minimum value
14    let minIndex = i;
15    
16    // Find the minimum element in the unsorted portion
17    for (let j = i + 1; j < n; j++) {
18      if (result[j] < result[minIndex]) {
19        minIndex = j;
20      }
21    }
22    
23    // Swap only if a new minimum was found
24    if (minIndex !== i) {
25      // Destructuring swap
26      [result[i], result[minIndex]] = [result[minIndex], result[i]];
27    }
28  }
29  
30  return result;
31}

Kendi Verilerinizle Test Edin

Aşağıya kendi verilerinizi girerek Selection Sort algoritmasını test edebilirsiniz. Virgülle ayrılmış sayılar girin (örn: 5,3,8,4,2) veya rastgele bir dizi oluşturun.

Selection Sort Demo

Verdiğiniz dizi Selection Sort algoritması ile sıralanacaktır.

Girdi (virgülle ayrılmış değerler veya dizi)

Sonuç

Sıralanmış Dizi: null

Not: Selection Sort her durum için O(n²) zaman karmaşıklığına sahiptir, ancak az sayıda takas işlemi gerçekleştirir.

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(n²) - Dizi zaten sıralı olsa bile algoritma her zaman tüm diziyi tarar.
Ortalama Durum: O(n²) - Algoritma her zaman n*(n-1)/2 karşılaştırma yapar.
En Kötü Durum: O(n²) - Dizi ters sıralı olsa bile algoritma aynı sayıda adım atar.

Alan Karmaşıklığı

O(1) - Selection Sort yerinde (in-place) bir sıralama algoritmasıdır. Giriş dizisinin boyutundan bağımsız olarak sabit miktarda ekstra bellek kullanır.

Kararlılık (Stability)

Selection Sort kararsız bir algoritmadır. Eşit değere sahip elemanların göreceli sırası korunmayabilir. Bunun nedeni, uzak mesafedeki takas işlemlerinin orijinal sırayı bozabilmesidir.

Avantajlar ve Dezavantajlar

Avantajlar

Anlaşılması ve uygulanması kolaydır.
Ekstra bellek alanı gerektirmez (O(1) alan karmaşıklığı).
Takas işlemi sayısı azdır - en fazla (n-1) takas yapılır.
Küçük veri setleri için yeterince verimli olabilir.
Yazma işlemi maliyetli olduğunda (örn. EEPROM) verimli olabilir.

Dezavantajlar

Büyük veri setleri için O(n²) zaman karmaşıklığı nedeniyle verimsizdir.
Dizi durumuna bakılmaksızın her zaman aynı karmaşıklığa sahiptir - uyarlanabilir değildir.
Kararsız bir algoritma olduğundan, eşit değerli elemanların sırası değişebilir.
Modern uygulamalarda, daha iyi performans sunan algoritmalar tercih edilir.

Selection Sort vs Bubble Sort

Selection Sort ve Bubble Sort, benzer zaman karmaşıklığına sahip olsalar da, önemli farklılıklar içeren iki temel sıralama algoritmasıdır. İşte bu iki algoritmanın karşılaştırması:

Özellik	Selection Sort	Bubble Sort
Takas İşlemi	En fazla (n-1) takas yapar	En kötü durumda n*(n-1)/2 takas yapar
Karmaşıklık (En İyi Durum)	O(n²)	O(n) - Zaten sıralı veri için
Karmaşıklık (En Kötü Durum)	O(n²)	O(n²)
Kararlılık	Kararsız	Kararlı
Erken Çıkış	Yok - Her zaman tüm diziyi tarar	Var - Sıralı durumda erken sonlanabilir
Uyarlanabilirlik	Uyarlanabilir değil	Kısmen uyarlanabilir
Tercih Edilme Durumu	Takas işlemi maliyetli ise	Veri seti neredeyse sıralı ise

İki algoritma da O(n²) karmaşıklığa sahiptir, ancak Selection Sort her zaman daha az takas işlemi yapar. Bununla birlikte, Bubble Sort kısmen sıralı verilerde daha iyi performans gösterebilir ve kararlı bir algoritma olması eşit elemanların orijinal sırasını koruduğu anlamına gelir.

İlgili Algoritmalar

Selection Sort'a benzer veya alternatif olarak kullanılabilecek diğer sıralama algoritmaları:

Insertion Sort

Kısmen sıralı veriler için Selection Sort'tan daha verimli ve kararlı bir algoritmadır.

Heap Sort

Selection Sort'un daha gelişmiş bir versiyonu olarak düşünülebilir, O(n log n) karmaşıklığa sahiptir.

Merge Sort

Daha hızlı (O(n log n)) ve kararlı bir algoritmadır, ancak ekstra bellek gerektirir.