Insertion Sort Algoritması
Insertion Sort Açıklaması
Insertion Sort, sıralanmış kısıma elemanları tek tek yerleştiren basit ve sezgisel bir sıralama algoritmasıdır. Bu algoritma, kart oyununda elimizdeki kartları sıralarken kullandığımız stratejiye benzer bir yaklaşım kullanır. ## Çalışma Prensibi: 1. Dizinin ilk elemanı zaten sıralı kabul edilir. 2. İkinci elemandan başlayarak, her elemanı sıralı alt dizide doğru konuma yerleştir. 3. Bu işlem için, mevcut elemanı geçici olarak sakla. 4. Sıralı kısımda elemandan büyük olan tüm elemanları bir pozisyon sağa kaydır. 5. Boşalan konuma mevcut elemanı yerleştir. 6. Dizinin tüm elemanları için 2-5 adımlarını tekrarla. ## Önemli Özellikler: 1. **Yerinde Sıralama**: Ekstra bellek kullanmadan orijinal diziyi sıralar. 2. **Kararlı Sıralama**: Eşit değere sahip elemanların göreceli sırası korunur. 3. **Uyarlanabilir**: Kısmen sıralı dizilerde daha az işlem yaparak daha verimli çalışır. 4. **Çevrimiçi Algoritma**: Giriş verilerini hepsi bir anda değil, sırayla alabilir. Insertion Sort, küçük veri setleri veya neredeyse sıralı diziler için oldukça verimlidir. Örneğin, zaten sıralı bir diziye yeni elemanlar eklerken idealdir. Ancak büyük ve rastgele düzenlenmiş dizilerde daha yavaştır.
Kod Örnekleri
Insertion 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.
1/**2 * Insertion Sort implementation for JavaScript arrays3 * @param {Array} arr - The array to sort4 * @returns {Array} - A new sorted array5 */6function insertionSort(arr) {7 // Create a copy to avoid modifying the original array8 const result = [...arr];9 const n = result.length;10 11 // Start from the second element (index 1)12 for (let i = 1; i < n; i++) {13 // Store the current element to be inserted14 const current = result[i];15 16 // Find the position to insert the current element in the sorted subarray17 let j = i - 1;18 while (j >= 0 && result[j] > current) {19 // Shift elements to the right20 result[j + 1] = result[j];21 j--;22 }23 24 // Insert the current element at the correct position25 result[j + 1] = current;26 }27 28 return result;29}Kendi Verilerinizle Test Edin
Aşağıya kendi verilerinizi girerek Insertion Sort algoritmasını test edebilirsiniz. Virgülle ayrılmış sayılar girin (örn: 5,3,8,4,2) veya rastgele bir dizi oluşturun.
Insertion Sort Demo
Verdiğiniz dizi Insertion Sort algoritması ile sıralanacaktır.
Not: Insertion Sort kısmen sıralı dizilerde daha verimlidir ve küçük veri setleri için uygun bir seçimdir.
Algoritma Analizi
Zaman ve Alan Karmaşıklığı
Zaman Karmaşıklığı
- En İyi Durum:
O(n)- Dizi zaten sıralıysa, sadece karşılaştırma yapılır ve hiç yer değiştirme yapılmaz. - Ortalama Durum:
O(n²)- Rastgele sırada olan bir dizi için, her eleman ortalama olarak yarısı kadar yer değiştirir. - En Kötü Durum:
O(n²)- Dizi tersine sıralıysa, her eleman en başa kadar taşınmak zorundadır.
Alan Karmaşıklığı
O(1) - Insertion 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)
Insertion Sort kararlı bir algoritmadır. Eşit değere sahip elemanların göreceli sırası korunur. Bu özellik, çoklu anahtar sıralaması gerektiren uygulamalarda önemlidir.
Avantajlar ve Dezavantajlar
Avantajlar
- Anlaşılması ve uygulanması son derece kolaydır.
- Ekstra bellek gerektirmez (O(1) alan karmaşıklığı).
- Kararlı bir algoritma olduğundan, eşit değerli elemanların sırası korunur.
- Neredeyse sıralı dizilerde, O(n) karmaşıklığa yaklaşır ve oldukça verimlidir.
- Çevrimiçi bir algoritma olduğundan, veri aktarımı sırasında sıralama yapabilir.
- Küçük veri setleri için basit ve verimlidir.
Dezavantajlar
- Büyük veri setleri için O(n²) zaman karmaşıklığı nedeniyle verimsizdir.
- Rastgele sıralanmış veya tersine sıralı dizilerde performans kaybı yaşanır.
- Her eleman için kaydırma işlemi maliyetlidir.
- Dizinin boyutu büyüdükçe, daha gelişmiş algoritmalardan (Quick Sort, Merge Sort vb.) önemli ölçüde daha yavaştır.
Insertion Sort Nasıl Çalışır?
Aşağıda, Insertion Sort'un [5, 2, 4, 6, 1, 3] dizisini sıralama adımları gösterilmiştir:
Adım Adım Insertion Sort
Başlangıç Dizisi:
[5, 2, 4, 6, 1, 3]İlk eleman (5) zaten sıralanmış kabul edilir.
1. Adım: İkinci elemanı (2) ekle
2 değeri 5'ten küçük olduğu için, 5'i sağa kaydır ve 2'yi yerleştir:
[2, 5, 4, 6, 1, 3]Sıralanmış kısım: [2, 5]
2. Adım: Üçüncü elemanı (4) ekle
4 değeri 5'ten küçük ama 2'den büyük olduğu için, 5'i sağa kaydır ve 4'ü yerleştir:
[2, 4, 5, 6, 1, 3]Sıralanmış kısım: [2, 4, 5]
3. Adım: Dördüncü elemanı (6) ekle
6 değeri 5'ten büyük olduğu için yerinde kalır:
[2, 4, 5, 6, 1, 3]Sıralanmış kısım: [2, 4, 5, 6]
4. Adım: Beşinci elemanı (1) ekle
1 değeri tüm önceki elemanlardan küçük olduğu için, hepsini sağa kaydır ve 1'i başa yerleştir:
[1, 2, 4, 5, 6, 3]Sıralanmış kısım: [1, 2, 4, 5, 6]
5. Adım: Altıncı elemanı (3) ekle
3 değeri 2'den büyük ama 4'ten küçük olduğu için, 4, 5 ve 6'yı sağa kaydır ve 3'ü yerleştir:
[1, 2, 3, 4, 5, 6]Sıralanmış kısım: [1, 2, 3, 4, 5, 6]
Sonuç: Tamamen Sıralanmış Dizi
[1, 2, 3, 4, 5, 6]Insertion Sort ve Diğer Algoritmalar
Insertion Sort ile diğer popüler sıralama algoritmalarının karşılaştırması:
| Özellik | Insertion Sort | Bubble Sort | Selection Sort | Quick Sort |
|---|---|---|---|---|
| En İyi Durum | O(n) | O(n) | O(n²) | O(n log n) |
| En Kötü Durum | O(n²) | O(n²) | O(n²) | O(n²) |
| Alan Karmaşıklığı | O(1) | O(1) | O(1) | O(log n) |
| Kararlılık | Kararlı | Kararlı | Kararsız | Kararsız |
| Uyarlanabilirlik | Yüksek | Düşük | Yok | Kısmen |
| Çevrimiçi | Evet | Hayır | Hayır | Hayır |
| Tercih Edilme Durumu | Kısmen sıralı küçük veri setleri | Eğitim amaçlı | Az takas gerektiren durumlar | Genel amaçlı büyük veri setleri |
Insertion Sort, özellikle kısmen sıralı diziler için verimli bir seçimdir. Çoğu programlama dilinin dahili sıralama fonksiyonları, küçük alt dizileri sıralamak için Insertion Sort'u tercih eder. Bu yüzden hibrit algoritmalarda (Timsort gibi) sıklıkla kullanılır.
İlgili Algoritmalar
Insertion Sort ile ilişkili veya benzer algoritmalar:
Shell Sort
Insertion Sort'un geliştirilmiş versiyonu. Büyük adımlarla başlayıp giderek küçülen adımlarla sıralama yapar, böylece uzak elemanları daha hızlı hareket ettirir.
Binary Insertion Sort
Linear arama yerine binary search kullanarak elemanın doğru pozisyonunu daha hızlı bulan bir Insertion Sort varyasyonudur.
Timsort
Insertion Sort ve Merge Sort'u birleştiren bir hibrit algoritma. Python, Java ve daha birçok dilin yerleşik sıralama algoritması olarak kullanılır.
Insertion Sort
Sıralanmış bir alt listeye elemanları birer birer ekleyerek sıralama yapan bir algoritma.
Avantajlar
- Kısmen sıralı veriler için çok verimli
- Küçük veri setleri için basit ve etkili
- Kararlı bir sıralama algoritması
- Yerinde sıralama (ek bellek gerektirmez)
- Çevrimiçi bir algoritma (veri gelirken sıralayabilir)
Dezavantajlar
- Büyük veri setleri için O(n²) karmaşıklık nedeniyle verimsiz
- Her eleman için kaydırma işlemi zaman alıcı olabilir
- Rastgele sıralanmış dizilerde performans düşüktür
- Büyük veri setlerinde Quick Sort veya Merge Sort'tan daha yavaştır