C ile Ekleme Sıralama Algoritması, C++, Java, Python Örnekler

Eklemeli Sıralama nedir?

Ekleme Sıralaması, elemanları tek tek işleyerek ve sıralanmış bir bölge içindeki doğru konumuna yerleştirerek sıralama yapan karşılaştırmalı sıralama algoritmalarından biridir.

Her eleman, önceden sıralanmış bir listeye sırayla eklenir. Başlangıçtaki sıralanmış listenin boyutu birdir. Ekleme Sıralama algoritması, dış döngünün k. iterasyonundan sonra ilk k elemanın sıralanmasını sağlar.

Eklemeli Sıralama algoritması sonucu artımlı olarak oluşturduğu için, öğretilmesi sezgiseldir, hata ayıklaması kolaydır ve daha karmaşık algoritmaların ölçülebilir kazanımlar olmadan ek yük getireceği çok küçük girdiler için güçlü bir temel oluşturur.

Eklemeli Sıralama Algoritmasının Özellikleri

Ekleme sıralama algoritmasının gerçek iş yüklerindeki davranışını açıklayan aşağıdaki önemli özellikleri vardır:

• Kararlı bir sıralama tekniği olduğundan eşit elemanların göreceli sırasını değiştirmez.
• Bu yöntem küçük veri kümeleri için etkilidir ancak karesel büyümenin baskın olduğu daha büyük listeler için etkili değildir.
• Ekleme Sıralama algoritması uyarlanabilir bir algoritmadır; yani girdi kısmen sıralıysa toplam adım sayısını azaltır. Dizi İç döngü sırasında sabit zamanlı kaydırmalara olanak sağlayan rastgele erişim sayesinde, verimliliği artırmak için girdi olarak sağlanır.
• Bu, yerinde işlem yapan bir algoritmadır, bu nedenle giriş boyutuna orantılı ek depolama alanı gerektirmez.

Bu özellikler göz önünde bulundurularak, bir sonraki bölümde algoritmanın her aşamasını çalıştıran temel ekleme işlemi açıklanmaktadır.

Insert nasıl yapılır? Operaiş mi?

Ekleme Sıralama algoritmasında, sıralanmamış elemanları sıralamak için ekleme işlemi kullanılır. Bu işlem, sıralanmış bölgenin mevcut sırasını koruyarak, zaten sıralanmış bir listeye yeni bir eleman eklemeye yardımcı olur.

Ekleme işleminin sözde kodu:

N elementten oluşan bir A listesi düşünün.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

Yukarıdaki örnekte, zaten sıralanmış bir listeye 6 numaralı yeni bir eleman eklenmiştir. Aşağıdaki adımlar izlenecektir. tracYeni eleman doğru konumuna doğru sola doğru hareket ederken iç döngüyü inceleyin.

) 1 Adım A[5], 9 > 6'nın sol komşu elemanıyla karşılaştırıldığında, 9 ve 6'nın konumunu değiştiririz. Şimdi 6. eleman A[4]'e taşınır.

) 2 Adım Şimdi A[4] ve A[3]'ü karşılaştırıyoruz ve A[3] > A[4] olduğunu görüyoruz, bu yüzden 6 ve 8'in konumlarını tekrar değiştiriyoruz.

) 3 Adım Şimdi A[3] ve A[2]'yi karşılaştıralım. A[2] > A[3] olduğundan, 7 ve 6'nın konumlarını değiştiriyoruz.

) 4 Adım A[1] ve A[2]'yi karşılaştırıyoruz. A[1] < A[2] olduğundan, soldaki bitişik eleman artık daha büyük değildir. 6'nın doğru şekilde eklendiği sonucuna varıyoruz ve iç döngüyü burada durduruyoruz.

Eklemeli Sıralama Nasıl Çalışır?

Yukarıda bahsedilen ekleme işlemi, Ekleme Sıralama algoritmasının temelini oluşturur. Ekleme işlemi her eleman üzerinde gerçekleştirilir ve sonunda, sıralanmış bölge her dış geçişte bir eleman daha büyüdüğü için sıralanmış liste elde edilir.

Yukarıdaki şekil, bir veri yapısında Ekleme Sıralama algoritmasının çalışma şeklini göstermektedir. Başlangıçta, sıralanmış alt listede yalnızca bir eleman bulunur, yani 4. A[1], yani 3 eklendikten sonra, sıralanmış alt listenin boyutu 2'ye yükselir ve algoritma, her eleman yerleştirilene kadar bu deseni sürdürür.

Kavramsal akış oluşturulduktan sonra, aşağıdaki bölümlerde somut uygulamalar gösterilmektedir. C++, C ve Python Böylece farklı dillerdeki döngü yapılarını karşılaştırabilirsiniz.

C++ Eklemeli Sıralama Programı

MKS C++ Aşağıdaki uygulama iki iç içe döngü kullanır: dış döngü bir sonraki sıralanmamış öğeyi seçer ve iç döngü doğru konum bulunana kadar onu sola kaydırır.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Çıktı:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code Ekleme Sıralaması için

Aynı mantık doğrudan C diline de uygulanabilir. Standart printf Çağrılar akış çıktısını değiştirir, ancak iç döngüdeki takas deseni aynıdır. C++ sürümü.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Çıktı:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Eklemeli Sıralama Programı

Python demet değişimini desteklerping tek bir ifadede, bu nedenle iç döngü C ve diğer döngülerden daha kompakttır. C++ Aynı algoritmik davranışı korurken, benzerlerine de uyum sağlamak.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Çıktı:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Eklemeli Sıralamanın Özellikleri

İşte, eklemeli sıralama algoritmasının ne zaman doğru araç olduğuna karar vermenize yardımcı olacak önemli özellikleri:

• İnternet üzerinden: Ekleme Sıralaması, elemanları aldığı anda sıralayabilir. Eğer bir eleman listesini zaten sıraladıysak ve listeye daha fazla eleman eklediysek, tüm sıralama işlemini tekrar çalıştırmamıza gerek yoktur. Bunun yerine, yalnızca yeni eklenen elemanlar üzerinde yineleme yaparız.
• Yerinde: Eklemeli Sıralama algoritmasının alan karmaşıklığı sabittir ve ek alan gerektirmez. Bu algoritma elemanları yerinde sıralar.
• Kararlı: Ekleme Sıralama algoritmasında, değerleri eşit olan elemanların yerlerini değiştirmeyiz. Örneğin, x ve y olmak üzere iki eleman eşitse ve sıralanmamış listede x, y'den önce geliyorsa, sıralanmış listede de x, y'den önce gelmeye devam edecektir. Bu da Ekleme Sıralama algoritmasını kararlı kılar.
• Uyarlanabilir: A sıralama algoritması Giriş elemanları veya elemanların bir alt kümesi zaten sıralı olduğunda daha az zaman alıyorsa, bir algoritma uyarlanabilir olarak adlandırılır. Yukarıda tartıştığımız gibi, Ekleme Sıralama algoritmasının en iyi çalışma süresi O(N), en kötü çalışma süresi ise O(N^2)'dir. Ekleme Sıralama, uyarlanabilir sıralama algoritmalarından biridir.

Ekleme Sıralamasının Karmaşıklığı

Aşağıdaki karmaşıklık tartışması, hem bellek kullanımını hem de çalışma süresini kapsamakta olup, Ekleme Sıralama algoritmasını aşağıdaki gibi alternatiflerle karşılaştırabilmeniz için değerlendirebilirsiniz. Bubble Sırala hem de Hızlı sıralama.

Uzay Karmaşıklığı

Ekleme Sıralaması, elemanları sıralamak için ek alana ihtiyaç duymaz. Alan karmaşıklığı sabittir, yani O(1), çünkü giriş boyutundan bağımsız olarak yalnızca birkaç geçici değişken kullanılır.

Zaman Karmaşıklığı

Eklemeli Sıralama algoritması her seferinde bir eleman üzerinde çalıştığı için, N elemanı sıralamak için N-1 geçiş gerektirir. Her geçişte, elemanlar zaten sıralıysa sıfır takas yapabilir veya elemanlar azalan sırada düzenlenmişse birçok takas gerekebilir.

• Geçiş 1 için gereken minimum takas sayısı sıfırdır ve gereken maksimum takas sayısı 1'dir.
• Geçiş 2 için gereken minimum takas sayısı sıfırdır ve gereken maksimum takas sayısı 2'dir.
• N geçişi için gereken minimum takas sıfırdır ve gereken maksimum takas N'dir.
• Minimum takas sıfırdır, bu nedenle N geçişi yinelemek için en iyi zaman karmaşıklığı O(N)'dir.
• Toplam maksimum takas sayısı (1+2+3+4+…+N) yani N(N+1)/2 olduğundan, en kötü zaman karmaşıklığı O(N^2)'dir.

İşte Ekleme Sıralama algoritmasının önemli zaman karmaşıklığı:

• En Kötü Durum KarmaşıklığıO(n^2): Artan sırada sıralanması gereken bir dizinin azalan sırada sıralanması en kötü senaryodur.
• En İyi Durum Karmaşıklığı: O(n): En iyi durum, dizinin zaten sıralı olduğu zaman gerçekleşir; dış döngü n kez çalışırken, iç döngü hiç çalışmaz. Sadece n karşılaştırma olduğundan, karmaşıklık doğrusaldır.
• Ortalama Vaka Karmaşıklığı: O(n^2): Bu, dizinin elemanlarının ne artan ne de azalan bir düzende karışık bir şekilde sıralanması durumunda meydana gelir.

SSS