Aşağıdaki sayıları göz önünde bulundurun:
50 60 30 10 80 70 20 40
Bu liste artan düzende sıralanırsa şöyle olur:
10 20 30 40 50 60 70 80
Azalan düzende sıralanırsa, şöyle olur:
80 70 60 50 40 30 20 10
Ekleme sıralama, listeyi artan veya azalan düzende sıralamak için kullanılan bir sıralama algoritmasıdır. Bu makale yalnızca artan düzende sıralama ile ilgilidir. Azalan düzende sıralama, bu belgede verilen aynı mantığı takip eder. Bu makalenin amacı, ekleme sıralamasını açıklamaktır. Programlama aşağıdaki örnekte C'de yapılmıştır. Ekleme sıralaması burada bir dizi kullanılarak açıklanmıştır.
Ekleme Sıralaması için Algoritma
Sıralanmamış bir liste verilir. Amaç, aynı listeyi kullanarak listeyi artan düzende sıralamaktır. Aynı diziyi kullanarak sıralanmamış bir diziyi sıralamanın yerinde sıralama olduğu söylenir. Sıfır tabanlı indeksleme burada kullanılır. Adımlar aşağıdaki gibidir:
-
- Liste baştan taranır.
- Tarama devam ederken, öncekinden daha az herhangi bir sayı, öncekiyle değiştirilir.
- Bu takas, takas artık mümkün olmayana kadar liste boyunca devam eder.
- Tarama sona ulaştığında, sıralama tamamlanmıştır.
Ekleme Sıralama İllüstrasyon
Zaman karmaşıklığı ile uğraşırken, normalde dikkate alınan en kötü durumdur. Bir önceki liste için en kötü düzenleme şudur:
80 70 60 50 40 30 20 10
Sıfırdan 7'ye kadar indeksli sekiz eleman vardır.
İndeks sıfırda tarama 80'e gider. Bu bir harekettir. Bu tek hareket bir operasyondur. Şimdiye kadar toplam bir işlem var (bir hareket, karşılaştırma yok ve takas yok). Sonuç:
| 80 70 60 50 40 30 20 10
Birinci indekste 70'e bir hareket var. 70, 80 ile karşılaştırılıyor. 70 ve 80 takas ediliyor. Bir hareket bir işlemdir. Bir karşılaştırma aynı zamanda bir işlemdir. Bir takas da bir işlemdir. Bu bölüm üç işlem sağlar. Şimdiye kadar toplam dört işlem (1+3=4) yapılmıştır. Sonuç aşağıdaki gibidir:
70 | 80 60 50 40 30 20 10
İkinci endekste 60'a bir hareket var. 60, 80 ile karşılaştırılır, ardından 60 ve 80 değiştirilir. 60, 70 ile karşılaştırılır, ardından 60 ve 70 değiştirilir. Bir hareket bir işlemdir. İki karşılaştırma iki işlemdir. İki takas iki işlemdir. Bu bölüm beş işlem sağlar. Şimdiye kadar toplam dokuz işlem (4+5=9) yapılmıştır. Sonuç aşağıdaki gibidir:
60 70 | 80 50 40 30 20 10
Üçüncü endekste 50'ye bir hareket var. 50, 80 ile karşılaştırılır, ardından 50 ve 80 değiştirilir. 50, 70 ile karşılaştırılır, ardından 50 ve 70 değiştirilir. 50, 60 ile karşılaştırılır, ardından 50 ve 60 değiştirilir. Bir hareket bir işlemdir. Üç karşılaştırma üç işlemdir. Üç takas üç işlemdir. Bu bölüm yedi işlem sağlar. Şimdiye kadar toplam on altı işlem yapılmıştır (9 + 7 = 16). Sonuç aşağıdaki gibidir:
50 60 70 | 80 40 30 20 10
Dördüncü endekste 40'a bir hareket var. 40, 80 ile karşılaştırılır, ardından 40 ve 80 değiştirilir. 40, 70 ile karşılaştırılır, ardından 40 ve 70 değiştirilir. 40, 60 ile karşılaştırılır, ardından 40 ve 60 değiştirilir. 40, 50 ile karşılaştırılır, ardından 40 ve 50 değiştirilir. Bir hareket bir işlemdir. Dört karşılaştırma dört işlemdir. Dört takas dört işlemdir. Bu bölüm dokuz işlem sağlar. Şu ana kadar toplam yirmi beş işlem yapılmıştır (16+9=25). Sonuç aşağıdaki gibidir:
40 50 60 70 80 | 30 20 10
Beşinci endekste 30'a bir hareket var. 30, 80 ile karşılaştırılır, ardından 30 ve 80 değiştirilir. 30, 70 ile karşılaştırılır, ardından 30 ve 70 değiştirilir. 30, 60 ile karşılaştırılır, ardından 30 ve 60 değiştirilir. 30, 50 ile karşılaştırılır, ardından 30 ve 50 değiştirilir. 30, 40 ile karşılaştırılır, ardından 30 ve 40 değiştirilir. Bir hareket bir işlemdir. Beş karşılaştırma beş işlemdir. Beş takas beş işlemdir. Bu bölüm on bir işlem sağlar. Şimdiye kadar toplam otuz altı işlem var (25 + 11 = 36). Sonuç aşağıdaki gibidir:
30 40 50 60 70 80 | 20 10
Altıncı endekste 20'ye bir hareket var. 20, 80 ile karşılaştırılır, ardından 20 ve 80 değiştirilir. 20, 70 ile karşılaştırılır, ardından 20 ve 70 değiştirilir. 20, 60 ile karşılaştırılır, ardından 20 ve 60 değiştirilir. 20, 50 ile karşılaştırılır, ardından 20 ve 50 değiştirilir. 20, 40 ile karşılaştırılır, ardından 20 ve 40 değiştirilir. 20, 30 ile karşılaştırılır, ardından 20 ve 30 değiştirilir. Bir hareket bir işlemdir. Altı karşılaştırma altı işlemdir. Altı takas, altı işlemdir. Bu bölüm on üç işlem sağlar. Şimdiye kadar toplam kırk dokuz işlem var (36 + 13 = 49). Sonuç aşağıdaki gibidir:
20 30 40 50 60 70 80 | 10
Yedinci endekste 10'a bir hareket var. 10, 80 ile karşılaştırılır, ardından 10 ve 80 değiştirilir. 10, 70 ile karşılaştırılır, ardından 10 ve 70 değiştirilir. 10, 60 ile karşılaştırılır, ardından 10 ve 60 değiştirilir. 10, 50 ile karşılaştırılır, ardından 10 ve 50 değiştirilir. 10, 30 ile karşılaştırılır, ardından 10 ve 40 değiştirilir. 10, 30 ile karşılaştırılır, ardından 10 ve 30 değiştirilir. 10, 20 ile karşılaştırılır, ardından 10 ve 20 değiştirilir. Bir hareket bir işlemdir. Yedi karşılaştırma yedi işlemdir. Yedi takas yedi işlemdir. Bu bölüm on beş işlem sağlar. Şimdiye kadar toplam altmış dört işlem yapılmıştır (49 + 15 = 64). Sonuç aşağıdaki gibidir:
10 20 30 40 50 60 70 80 10 |
İş bitti! 64 operasyon düzenlendi.
64 = 8 x 8 = 8 iki
Ekleme Sıralaması için Zaman Karmaşıklığı
Ekleme Sıralaması ile sıralanacak n öğe varsa, daha önce gösterildiği gibi maksimum olası işlem sayısı n2 olacaktır. Ekleme Sıralama Zamanı karmaşıklığı:
Açık iki )
Bu, Big-O notasyonunu kullanır. Big-O notasyonu büyük harfle O ile başlar, ardından parantezler gelir. Parantez içinde, mümkün olan maksimum işlem sayısı ifadesi bulunur.
C'de kodlama
Taramanın en başında, ilk eleman konumunu değiştiremez. Program esas olarak aşağıdaki gibidir:
#includegeçersiz eklemeSıralama ( int A [ ] , int N ) {
için ( int i = 0 ; i < N; ben++ ) {
int j = ben;
süre ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
int sıcaklık = A [ j ] ; A [ j ] = bir [ j- 1 ] ; A [ j- 1 ] = sıcaklık; // takas
j--;
}
}
}
insertionSort() işlev tanımı, açıklandığı gibi algoritmayı kullanır. while döngüsü için koşullara dikkat edin. Bu program için uygun bir C ana işlevi:
{
int n = 8 ;
int A [ ] = { elli , 60 , 30 , 10 , 80 , 70 , yirmi , 40 } ;
eklemeSıralama ( Bir ) ;
için ( int i = 0 ; i < n; ben++ ) {
baskı ( '%ben ' , A [ i ] ) ;
}
baskı ( ' \n ' ) ;
dönüş 0 ;
}
Çözüm
Ekleme Sıralaması için zaman karmaşıklığı şu şekilde verilir:
Açık iki )
Okuyucu, daha kötü durum zaman karmaşıklığı, ortalama durum zaman karmaşıklığı ve en iyi durum zaman karmaşıklığı hakkında bir şeyler duymuş olabilir. Ekleme Sıralama Zamanı Karmaşıklığının bu varyasyonları, web sitemizdeki bir sonraki makalede tartışılmaktadır.