Ekleme Sıralaması: C ile Algoritma, C++, Java, Python Örnekler

Eklemeli Sıralama nedir?

Eklemeli sıralama, her seferinde bir öğeyi yineleyerek ve öğeyi doğru konuma yerleştirerek öğeleri sıralamak için kullanılan karşılaştırmalı sıralama algoritmalarından biridir.

Her öğe önceden sıralanmış bir listeye sırayla eklenir. Zaten sıralanmış listenin boyutu başlangıçta birdir. Eklemeli sıralama algoritması, k'inci yinelemeden sonra ilk k elemanın sıralanmasını sağlar.

Eklemeli Sıralama Algoritmasının Özellikleri

Ekleme Sıralaması Algoritması aşağıdaki önemli Özelliklere sahiptir:

• Kararlı bir sıralama tekniği olduğundan eşit elemanların göreceli sırasını değiştirmez.
• Daha küçük veri kümeleri için verimlidir ancak daha büyük listeler için etkili değildir.
• Ekleme Sıralaması uyarlanabilir olup, kısmen sıralanırsa toplam adım sayısını azaltır. Dizi verimli hale getirilmesi için girdi olarak sağlanmaktadır.

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

Eklemeli Sıralama algoritmasında, sıralanmamış öğeleri sıralamak için ekleme işlemi kullanılır. Zaten sıralanmış bir listeye yeni bir öğe eklenmesine yardımcı olur.

Ekleme işleminin sözde kodu:

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

A[N-1] is the element to be inserted in the 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, halihazırda sıralanmış bir listeye yeni bir öğe (6) eklenecektir.

) 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] ile A[3]'ü karşılaştırıyoruz ve A[3] > A[4] olduğunu buluyoruz, yine 6 ile 8'in konumunu değiştiriyoruz.

) 3 Adım Şimdi A[3] ve A[2]'yi karşılaştırın, çünkü A[2] > A[3] 7 ve 6'nın konumunu değiştirsin.

) 4 Adım A[1] ve A[2]'yi karşılaştırıyoruz ve A[1] < A[2] olduğundan, yani soldaki bitişik eleman artık daha büyük değil. Şimdi 6'nın doğru yerleştirildiği sonucuna varıyoruz ve algoritmayı burada durduruyoruz.

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

Yukarıda tartışılan ekleme işlemi, ekleme sıralamasının omurgasıdır. Ekleme prosedürü her öğe üzerinde yürütülür ve sonunda sıralanmış listeyi elde ederiz.

Yukarıdaki örnek şekil veri yapısında ekleme sıralamasının çalışmasını göstermektedir. Başlangıçta, sıralanmış alt listede yalnızca bir öğe vardır, yani 4. A[1] yani 3'ü ekledikten sonra, sıralanmış alt listenin boyutu 2'ye büyür.

C++ Eklemeli Sıralama Programı

#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

Ekleme Sıralaması için C Kodu

#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ı

#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

Eklemeli Sıralamanın önemli özellikleri şunlardır:

• İnternet üzerinden: Ekleme sıralaması, öğeleri aldığı sırada sıralayabilir. Yani, eğer zaten bir öğe listesini sıraladıysak ve listelere birkaç öğe daha eklediysek, sıralama prosedürünün tamamını yeniden çalıştırmamıza gerek yok. Bunun yerine yalnızca yeni eklenen unsurları yinelememiz gerekiyor.
• Yerinde: Ekleme sıralama algoritmasının alan karmaşıklığı sabittir ve ekstra alan gerektirmez. Bu algoritma öğeleri yerinde sıralar.
• Kararlı: Eklemeli sıralamada değerleri eşit olan elemanların yerlerini değiştirmeyiz. Örneğin, x ve y olmak üzere iki öğe eşittir ve sıralanmamış listelerde x, y'den önce görünür; ardından sıralanmış listede x, y'den önce görünür. Bu, ekleme sıralamasını kararlı hale getirir.
• Uyarlanabilir: A sıralama algoritması Giriş öğeleri veya öğelerin alt kümesi zaten sıralanmışsa daha az zaman alırsa uyarlanabilirdir. Yukarıda tartıştığımız gibi, ekleme sıralamasının en iyi çalışma süresi O(N) ve en kötü çalışma süresi O(N^2)'dir. Eklemeli sıralama, uyarlanabilir sıralama algoritmalarından biridir.

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

Uzay Karmaşıklığı

Eklemeli sıralama, öğeleri sıralamak için ekstra alana ihtiyaç duymaz, alan karmaşıklığı sabittir, yani O(1).

Zaman Karmaşıklığı

Ekleme sıralaması her bir öğeyi aynı anda yinelediğinden, N öğeyi sıralamak için N-1 geçiş gerektirir. Her geçişte, öğeler zaten sıralanmışsa sıfır takas yapabilir veya öğeler azalan düzende düzenlenmişse takas yapabilir.

• 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 takaslar (1+2+3+4+..+N) i. N(N+1)/2'dir, en kötü zaman karmaşıklığı O(N^2)'dir.

İşte yerleştirme sıralamasının önemli zaman karmaşıklığı:

• En Kötü Durum Karmaşıklığı: O(n2): Bir dizi artan sıradayken, azalan sırada sıralamak en kötü senaryodur.
• En İyi Durum Karmaşıklığı: O(n): En İyi Durum Karmaşıklığı, dizi zaten sıralanmışsa oluşur, dış döngü n sayısı kadar çalışır, iç döngü ise hiç çalışmaz. Sadece n sayıda karşılaştırma vardır. Bu nedenle, bu durumda karmaşıklık doğrusaldır.
• Ortalama Vaka Karmaşıklığı: O(n2): Bir dizinin elemanları, artan veya azalan olmayan, karışık bir sırada yer aldığında meydana gelir.

ÖZET

• Eklemeli sıralama, karşılaştırmaya dayalı bir sıralama algoritması yöntemidir.
• Kararlı bir sıralama tekniği olduğundan eşit elemanların göreceli sırasını değiştirmez.
• Her öğede, öğeyi sıralanmış alt listeye eklemek için ekleme işlemi kullanılır.
• Eklemeli sıralama, yerinde bir sıralama algoritmasıdır.
• Ekleme sıralamasının en kötü ve ortalama zaman karmaşıklığı ikinci derecedendir, yani O(N^2).
• Eklemeli sıralama herhangi bir yardımcı alan gerektirmez.