Eklemeli sıralama

Eklemeli Sıralama'nın rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek.

Eklemeli Sıralama (İngilizcesi: Insertion Sort), bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır. Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır. Ancak buna karşın bazı artıları da vardır:

• Uygulaması kolaydır.
• Küçük Veri kümeleri üzerinde kullanıldığında verimlidir.
• Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir.
• Karmaşıklığı $\mathcal{O}(n^2)$ olan seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir.
• Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez)
• Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez.
• Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur. Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir.

İnsanlar herhangi birşeyi (örneğin, iskambil kartları) sıralarken, çoğu durumda eklemeli sıralamaya benzer bir yöntem kullanırlar.

Sözde Kodu

insertionSort(array A)
    for i = 1 to length[A-1] do
        value = A[i]
        j = i-1
        while j >= 0 and A[j] > value
            A[j + 1] = A[j]
            j = j-1
        A[j+1] = value

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.1: Sorting by Insertion, pp. 80–105.

Dış Bağlantılar

• Analyze Insertion Sort in an online Javascript IDE
• Insertion Sort Java Applet
• An animated Java applet showing a step-by-step insertion sort.
• Literate implementations of insertion sort in various languages on LiteratePrograms
• Pointers to insertion sort visualizations
• Insertion sort explained and C++ code
• Page with visual demonstrations of sorting algorithms, all the implementation in Java.
• A graphical demonstration and discussion of insertion sort
• C/C++ implementation for a binary insertion sort