Sıralama ekle
Ekleme sıralama (Ekleme sıralama) — ;girdi dizisinin öğelerinin birer birer arandığı ve her yeni gelen öğenin daha önce sıralanan öğeler arasında uygun yere yerleştirildiği sıralama algoritması.
Sıralamayı ekle – çok basit ama verimsiz bir algoritmadır ve yine de genel olarak daha verimli birçok başka algoritma geliştirildikten sonra bile onu alakalı kılan birkaç özel avantaja sahiptir.
Araya eklemeli sıralamada, sıralamadan önce tüm dizinin ön planda olması gerekmez. Algoritma, sıralama sırasında her seferinde bir öğe alabilir. Bu sıralama sırasında daha fazla öğe eklememiz gerekirse çok kullanışlıdır. Algoritma, yeni öğeyi "yeniden çalıştırmadan" doğru yere yerleştirecek tüm diziyi sıralama.
Ekleme sıralaması, küçük (~10 öğeli) veri kümelerindeki verimliliği nedeniyle pratikte kullanılabilir.
Sorun şu ki: dizinin zaten sıralanmış bir kısmı var ve sırayı korurken dizinin geri kalan öğelerini sıralanan kısma eklemek istiyorsunuz. Bunu yapmak için, algoritmanın her adımında, giriş verisi öğelerinden birini seçeriz ve onu, tüm girdi veri seti sıralanana kadar dizinin zaten sıralanmış bölümünde istenen konuma yerleştiririz. Girdi dizisinden bir sonraki öğeyi seçme yöntemi isteğe bağlıdır, ancak genellikle (ve kararlı bir sıralama algoritması elde etmek için), öğeler girdi dizisindeki görünüm sırasına göre eklenir.
Bu algoritmanın algoritmik uygulaması
// Boş öğe zaten sıralanmış bir dizi olarak kabul edilir.
// Bu nedenle, döngü 1'den başlar
I=1 İLE N-1 İÇİN DÖNGÜ ADIM 1
X=A[I]
J=ben
WHEN J>0 AND A[J-1]>X //eklenecek yer aranıyor
DEĞİŞİM A[J],A[J-1]
J=J-1
Güle güle
A[J]=X
SONRAKİ ben
Hesaplama karmaşıklığı:
\(\displaystyle O(n^{2})\).