AlgoPit

Counting Sort Algoritması

Counting Sort Açıklaması

Counting Sort, karşılaştırma yapmadan sıralama yapan, belirli koşullar altında lineer zaman karmaşıklığı (O(n)) sunan bir sıralama algoritmasıdır. Giriş dizisindeki her elemanın kaç kez tekrarlandığını sayarak çalışır ve bu sayıları kullanarak sıralı bir dizi oluşturur. ## Çalışma Prensibi: 1. Giriş dizisindeki maksimum değeri bul (k). 2. k+1 uzunluğunda bir sayaç dizisi oluştur ve tümünü 0 ile başlat. 3. Giriş dizisinin her bir elemanı için, sayaç dizisinde ilgili indeksi 1 artır. 4. Sayaç dizisini kümülatif olarak güncelle (her eleman kendinden önceki ile toplanır). 5. Sıralı diziyi oluşturmak için giriş dizisini sondan başa doğru tara. 6. Her eleman için, sayaç dizisindeki değer, o elemanın sıralı dizideki konumunu belirtir. ## Önemli Özellikler: 1. **Karşılaştırma Yapmadan Sıralama**: Diğer algoritmaların aksine, elemanları birbiriyle karşılaştırmaz. 2. **Kararlı Sıralama**: Eşit değere sahip elemanların göreceli sırası korunur. 3. **Sınırlı Uygulama Alanı**: Sadece sınırlı değer aralığına sahip tam sayılar için verimlidir. 4. **Zaman Karmaşıklığı**: O(n+k), burada n giriş dizisinin boyutu, k ise olası değer aralığı. Counting Sort, özellikle k değeri n ile karşılaştırılabilir olduğunda (k = O(n)) çok verimlidir, ancak değer aralığı çok büyükse verimli değildir.

Kod Örnekleri

Counting 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.

Counting Sort - JavaScript
1/**
2 * Counting Sort implementation for JavaScript arrays
3 * @param {Array} arr - The array of non-negative integers to sort
4 * @returns {Array} - A new sorted array
5 */
6function countingSort(arr) {
7  // Create a copy to avoid modifying the original array
8  const result = [...arr];
9  
10  // Edge case: empty array
11  if (result.length === 0) return result;
12  
13  // Find the maximum element to determine the count array size
14  const max = Math.max(...result);
15  
16  // Create counting array (index 0 to max)
17  const count = new Array(max + 1).fill(0);
18  
19  // Count frequency of each element
20  for (let i = 0; i < result.length; i++) {
21    count[result[i]]++;
22  }
23  
24  // Update counting array with cumulative count
25  for (let i = 1; i < count.length; i++) {
26    count[i] += count[i - 1];
27  }
28  
29  // Create the output array
30  const output = new Array(result.length);
31  
32  // Build the output array in a stable way (traversing from end to start)
33  for (let i = result.length - 1; i >= 0; i--) {
34    output[count[result[i]] - 1] = result[i];
35    count[result[i]]--;
36  }
37  
38  // Copy the output array to result
39  for (let i = 0; i < result.length; i++) {
40    result[i] = output[i];
41  }
42  
43  return result;
44}

Kendi Verilerinizle Test Edin

Aşağıya kendi verilerinizi girerek Counting Sort algoritmasını test edebilirsiniz. Virgülle ayrılmış pozitif tam sayılar girin (örn: 5,3,8,4,2). Not: Counting Sort sadece tam sayılarla çalışır ve negatif değerler için ek işlemler gerektirir.

Counting Sort Demo

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

Sıralanmış Dizi: null

Not: Counting Sort, değer aralığı sınırlı tam sayı dizileri için O(n+k) karmaşıklığa sahiptir. Burada k dizideki maksimum değerdir.

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

  • En İyi Durum: O(n+k) - Burada n giriş dizisinin boyutu, k ise değer aralığı.
  • Ortalama Durum: O(n+k) - Karmaşıklık, giriş verisinin dağılımından bağımsızdır.
  • En Kötü Durum: O(n+k) - Diğer algoritmalardan farklı olarak, dizinin durumundan etkilenmez.

Alan Karmaşıklığı

O(n+k) - Sayaç dizisi (k boyutunda) ve çıktı dizisi (n boyutunda) için ekstra bellek kullanır. Yerinde (in-place) bir sıralama algoritması değildir.

Kararlılık (Stability)

Counting Sort kararlı bir algoritma olarak uygulanabilir. Bu uygulama, giriş dizisini sondan başa doğru tarayarak eşit değerli elemanların göreceli sırasının korunmasını sağlar.

Avantajlar ve Dezavantajlar

Avantajlar

  • Sınırlı aralıkta lineer zaman karmaşıklığı (O(n+k)) sağlar.
  • Karşılaştırma yapmadığı için karşılaştırma tabanlı algoritmaların O(n log n) alt sınırını aşabilir.
  • Kararlı bir sıralama algoritmadır, eşit değere sahip elemanların orijinal sırasını korur.
  • Radix Sort gibi daha gelişmiş algoritmaların yapı taşı olarak kullanılır.

Dezavantajlar

  • Sadece tam sayı veya sınırlı aralıktaki değerler için etkilidir.
  • Değer aralığı (k) çok büyükse verimsiz olabilir.
  • Veri kümesi boyutuna ek olarak, değer aralığı kadar ekstra bellek gerektirir.
  • Negatif sayılar için doğrudan uygulanamaz, ek değişiklikler gerektirir.
  • Anahtar-değer çiftleri veya daha karmaşık veri yapıları için özel uygulamalar gerektirir.

Counting Sort ve Karşılaştırmalı Algoritmalar

Counting Sort ile karşılaştırma tabanlı ve karşılaştırma yapmayan diğer sıralama algoritmalarının karşılaştırması:

ÖzellikCounting SortQuick SortRadix SortBucket Sort
Karşılaştırma Yapar mı?HayırEvetHayırKısmen
Zaman KarmaşıklığıO(n+k)O(n log n) (Ortalama)O(d(n+k))O(n+k)
Alan KarmaşıklığıO(n+k)O(log n)O(n+k)O(n+k)
KararlılıkKararlıKararsızKararlıUygulamaya Bağlı
Veri KısıtlamalarıSınırlı aralıklı tam sayılarYokSabit boyutlu anahtarlarDüzgün dağılımlı veriler
Tekrarlayan elemanlar için verimlilikYüksekOrtaYüksekOrta-Yüksek
Tercih Edilme DurumuKüçük tam sayı aralığıGenel amaçlıÇok basamaklı sayılarDüzgün dağılımlı veriler

Counting Sort, sınırlı aralıktaki tam sayılar için mükemmel bir seçimdir ve lineer zaman karmaşıklığı sunar. Ancak, geniş değer aralıkları veya karmaşık veri türleri için uygun değildir. Bu durumlarda Radix Sort veya karşılaştırma tabanlı algoritmalar tercih edilmelidir.

İlgili Algoritmalar

Counting Sort ile ilişkili veya benzer algoritmalar:

Radix Sort

Sayıları basamak basamak sıralar ve her basamak için genellikle Counting Sort kullanır. Büyük sayılar için daha verimlidir.

Bucket Sort

Veriyi "kovalara" böler ve her kovayı ayrı ayrı sıralar. Veri düzgün dağılımlı olduğunda Counting Sort gibi lineer zaman karmaşıklığı sunar.

Pigeonhole Sort

Counting Sort'un bir varyasyonudur. Her değer için tam olarak bir "güvercin yuvası" oluşturur ve elemanları yerleştirir. Değer aralığı ve eleman sayısı yakın olduğunda idealdir.

Counting Sort

Karşılaştırma yapmadan sıralama yapan, sınırlı değer aralığında lineer zamanda çalışan bir algoritma.

Avantajlar

  • Sınırlı aralıkta lineer zaman karmaşıklığı (O(n+k))
  • Karşılaştırma yapmadığı için karşılaştırma tabanlı algoritmaların alt sınırını aşabilir
  • Kararlı bir sıralama algoritmasıdır
  • Tekrarlanan değerler için oldukça verimlidir

Dezavantajlar

  • Sadece tam sayı veya sınırlı aralıktaki değerler için etkilidir
  • Değer aralığı (k) çok büyükse verimsiz olabilir
  • Ekstra bellek gerektirir (yerinde sıralama yapmaz)
  • Negatif sayılar için doğrudan uygulanamaz