Temel sıralama algoritmalarını öğrenmek Computer Science 101 dersinin bir parçasıdır. Ancak pesudocode’da veya büyük hesaplama için daha uygun dillerde (Python’dan) birçok örnek var. Bu yüzden hızlı bir şekilde üç temel sıralama algoritması üzerinden gidip C# göstermek onları düşündüm.

C # / .NET’te Varsayılan Sıralama

Bunların üzerinden geçerek, muhtemelen “Peki hangisi C# kullanıyor?” Diye düşüneceksiniz. Yani, Array.Sort() çağırırsanız, bu örneklerden herhangi birini kullanıyor mu? Peki cevap “it depends”. Genel olarak bir Liste, Dizi veya Koleksiyonda “Sort()” kullanılırken şunları kullanır:

  • Koleksiyonda 16’dan az öğe varsa, “Eklemeli sıralama” algoritması kullanılacaktır (bunun hakkında aşağıda konuşacağız).
  • Bölüm sayısı 2 günlük * dizi boyutunu * aşarsa, Yığın sıralaması kullanılır.
  • Aksi takdirde Hızlı sıralama kullanılır.

Ancak bu her zaman böyle değildir, örneğin bir listede Linq kullanılırken ve OrderBy çağrılırken, Hızlı sıralama her zaman temel uygulama olarak kullanılır.

Ancak, burada belirtmeye çalıştığım şey, gerçek dünyada şimdiye kadar kullanılmışsa ve aşağıda bir röportaj sorusu olarak kullanılması daha muhtemeldir, aşağıda özetlenen sıralama algoritmaları nadiren vardır. Ancak anlamak daha önemlidir çünkü çoğu zaman bu daha “arkaik” algoritmaların üzerine başka sıralama algoritmaları inşa edilir (Silikon Vadisi’ndeki şakaların da anlaşılmasına yardımcı olur!).

Array vs List

Sadece C# söz konusu olduğunda sıralama algoritmaları hakkında konuşmak çok önemli bir şey işaret etmek istiyorum. Programlamaya ilk başladığımda, örneklerin neden örnek kodlarında her zaman diziler kullandığını anlayamıyordum. Elbette C# ‘da olduğumuzdan, Listeler çok daha havalı! Sabit bir dizi, bağlantılı bir listeden açıkça daha hızlı olsa da, örneklerde bile dizileri kullanmamız gerekiyor mu?

Mesele şu ki, bunların hepsi “yerinde” türler. Yani, sonucu döndürmek, durumu depolamak veya “kısmi” sonuçları tutmak için ikinci bir nesne oluşturmayız. Aşağıda Eklemeli sıralama gibi şeyler yaptığımızda, bunun bir Liste ile nasıl daha kolay yapılabileceğine bir örnek vereceğim, ancak bellekte ek bir dizi oluşturulması gerekiyor. Hemen hemen tüm sıralama algoritmalarında, verilen veri yapısı içinde çalıştıklarını ve tamamen farklı bir nesne döndürmek için öğeleri “klonlamadıklarını” veya yeni bir Liste’ye seçmediklerini göreceksiniz. Bir kez “sıralama” nın sadece “bana en düşük eşyayı ver” ile ilgili olmadığını fark ettim ve sadece buradaki yeni listeye koyacağım ve tüm öğeleri seçene kadar devam edeceğim, ama bunun yerine neredeyse en etkili yol Bir dizinin içindeki öğeleri “dengelemek”, sözde kod sıralama algoritmaları aniden anlamlıdır.

Kabarcık Sırala(Bubble Sort)

İlk önce Kabarcık sıralaması’a bakacağız. Bu, verilerin sıralanması için aslında daha kötü bir durum senaryosudur, çünkü bazı şeylerin gerçekten sıralanması için tekli swapların birçok “geçişini” gerektirir.

Koda bakalım:

public static void BubbleSort(int[] input)
{
    var itemMoved = false;
    do
    {
        itemMoved = false;
        for (int i = 0; i < input.Count() - 1; i++)
        {
            if (input[i] > input[i + 1])
            {
                var lowerValue = input[i + 1];
                input[i + 1] = input[i];
                input[i] = lowerValue;
                itemMoved = true;
            }
        }
    } while (itemMoved);
}

Şimdi BubbleSort nasıl çalışır? Sıfır indeksinden başlayarak, dizideki bir öğeyi ve öğeyi alır ve karşılaştırırız. Doğru sıradalarsa, hiçbir şey yapmayız, yanlış sıradalarsa (örneğin, dizideki daha düşük öğe aslında bir sonraki öğeden daha yüksek bir değerdir), bu öğeleri değiştiririz. Sonra dizideki her öğeyi aynı şeyi yaparak devam ederiz (daha yüksekse bir sonraki öğeyle değiştirme).

Artık her öğeyi yalnızca komşusu ile karşılaştırdığımız için, her öğe yalnızca birkaç yeri taşıması gerektiğinde tek bir yeri taşıyabilir. Peki Bubblesort bunu nasıl çözüyor? Tüm süreci tekrar tekrar yürütüyor. “İtemMoved” değişkenini nasıl kullandığımıza dikkat edin. Bir öğeyi değiştirip taramayı baştan başlatacak olursak bunu true olarak ayarladık.

İşleri doğrudan doğru konuma değil, birer birer hareket ettirdiğimiz ve işleri doğru yapmak için birden fazla geçişe ihtiyaç duyduğumuz için BubbleSort son derece verimsiz olarak görülüyor.

Eklemeli Sıralama(Insertion Sort)

Bir sonraki adım Eklemeli sıralama. Şimdi, öğeleri tek tek kontrol ederken, bunun yerine yaptığımız şey, öğeyi en başından itibaren doğru dizine “eklemek” tir. Öğeyi komşusu ile değiştirdiğimiz BubbleSort’un aksine, daha önce kontrol ettiklerimiz göz önüne alındığında öğeyi doğru konuma yerleştiriyoruz.

Aslında kodu iki kez göstereceğim. İlk tipik eklemeli sıralama olduğunu düşünüyorum:

public static void InsertionSort(int[] input)
{
    for (int i = 0; i < input.Count(); i++)
    {
        var item = input[i];
        var currentIndex = i;
        while (currentIndex > 0 && input[currentIndex - 1] > item)
        {
            input[currentIndex] = input[currentIndex - 1];
            currentIndex--;
        }
        input[currentIndex] = item;
    }
}

Yani bu kodun kısa bir açıklaması.

Dizindeki her öğeye göz atıyoruz ve değeri alıyoruz. Daha sonra, başladığımız indeksin altındaki * indekslerindeki * her öğeye göz atacağız. Eğer öğe altlarındaki endeksten daha düşük bir değere sahipse, altındaki öğeyi 1 yukarı “kaydırırız”. Sonraki öğeyi kontrol edin. Bir bakıma bu bir tür kabarcık gibidir, çünkü onların altındaki komşuyu karşılaştırıyoruz, ama takas yaparsak, sonuna kadar değiştirmeye devam ederiz.

Son dizine (0) ulaşırsak veya geçerli öğemizden daha düşük bir değere sahip yeni bir öğeye basarsak, geçerli öğemizi bu dizine “ayırırız” ve basitçe ekleriz.

Ancak “Ekleme” sıralama algoritmasını görüntülemenin daha basit bir yolu, aslında geri döndürülecek yeni bir liste oluşturmaktır. Örneğin :

public static List<int> InsertionSortNew(this List<int> input)
{
    var clonedList = new List<int>(input.Count);
    for (int i = 0; i < input.Count; i++)
    {
        var item = input[i];
        var currentIndex = i;
        while (currentIndex > 0 && clonedList[currentIndex - 1] > item)
        {
            currentIndex--;
        }
        clonedList.Insert(currentIndex, item);
    }
    return clonedList;
}

Bu örnekte, bunun yerine, öğeleri doğru konuma ekleyerek yavaşça eklediğimiz yepyeni bir liste oluşturuyoruz. Yine, tam olarak doğru değil, çünkü üstündeki öğeleri bir dizine kaydırmak zorunda kalmadan belirli dizinlere öğe ekleyebilmek gibi şeyler yapıyoruz. Ancak öğeyi belirli bir dizine ekleyebilmek, sadece C # ‘ın bizim için hallettiği şekerdir.

Yine de, genellikle liste sıralaması hakkında konuştuğumuzda, “yerinde” sıralamadan bahsediyoruz ve öğeleri yeni bir nesneye ayırmaya çalışmıyoruz.

Seçim Sıralaması(Selection Sort)

Seçim Sıralaması aslında Eklemeli sıralamaya çok benzer. Kod şöyle görünür:

public static void SelectionSort(int[] input)
{
    for (var i = 0; i < input.Length; i++)
    {
        var min = i;
        for(var j = i + 1; j < input.Length; j++) { 
            if(input[min] > input[j])
            {
                min = j;
            }
        }
        if(min != i)
        {
            var lowerValue = input[min];
            input[min] = input[i];
            input[i] = lowerValue;
        }
    }
}

Temelde yaptığımız şey dizini baştan sona taramaktır. Her dizin için, dizinin geri kalanını geçerli öğeye kıyasla daha düşük (Etki, en düşük) bir öğe için tararız. Birini bulursak, mevcut öğeyle değiştiririz. Geçerli öğenin dizide daha sonraki bir konuma gitmesi, sonunda tüm öğeler kontrol edilecek kadar önemli değildir.

Şimdi, yine, bu, yerinde dizi ölçütlerimiz nedeniyle olması gerekenden daha karmaşık görünüyor. Ama gerçekten yaptığımız şey, bir tanesini taramak, listedeki en düşük öğeyi bulmak, bir diziye koymak ve sonra bir sonraki en yüksekle devam etmektir.

Böl ve Ayıkla Sıralama(Divide and Conquer Sorting)

Image for post

Burada yer almayan “Böl ve Ayıkla” sıralama algoritmalarıdır, bunlar Birleştirmeli sıralama ve Hızlı sıralama gibi çalışmayı daha küçük sıralama işlemlerine bölen ve ardından sonuçları birleştiren şeylerdir. Bunlar genellikle vahşi doğada bulacağınız sıralama algoritmalarıdır, ancak sıralamanın “temellerini” biraz geçmiş olabilir.

CEVAP VER

Please enter your comment!
Please enter your name here