Bir diziyi sıralama sorununu çözmek için birkaç temel algoritma vardır. Aralarında en ünlüsü eklemeli sıralamadır. Açıklığı ve basitliği, ancak düşük verimliliği nedeniyle, bu yöntem esas olarak programlama öğretiminde kullanılır. Temel sıralama mekanizmalarını anlamanızı sağlar.
Algoritmanın açıklaması
Eklemeli sıralama algoritmasının özü, ilk dizi içinde uygun şekilde sıralanmış bir segment oluşturulmasıdır. Her eleman kontrol edilen parça ile tek tek karşılaştırılır ve doğru yere yerleştirilir. Böylece, tüm öğeleri yineledikten sonra doğru sırada sıralanırlar.
Öğeleri seçme sırası herhangi biri olabilir, rastgele veya bir algoritmaya göre seçilebilirler. Çoğu zaman, sıralı numaralandırma, sıralı bir segmentin oluşturulduğu dizinin başlangıcından itibaren kullanılır.
Sıralamanın başlangıcı şöyle görünebilir:
- Dizin ilk öğesini alın.
- Karşılaştırılacak hiçbir şey olmadığından, öğenin kendisini sipariş edildiği gibi alınsıra.
- İkinci öğeye git.
- Sıralama kuralına göre ilkiyle karşılaştırın.
- Gerekirse öğeleri yerlerde değiştirin.
- İlk iki öğeyi sıralı bir dizi olarak alın.
- Üçüncü öğeye git.
- İkincisiyle karşılaştırın, gerekirse değiştirin.
- Değiştirme yapılırsa, ilkiyle karşılaştırın.
- Üç öğeyi sıralı bir dizi olarak alın.
Orijinal dizinin sonuna kadar böyle devam eder.
Gerçek hayat ekleme sıralama
Açıklık olması açısından, bu sıralama mekanizmasının günlük hayatta nasıl kullanıldığına dair bir örnek vermeye değer.
Örneğin, bir cüzdan alın. Banknot bölmesinde yüz, beş yüz ve bin dolarlık banknotlar düzensiz bir şekilde yatıyor. Bu bir karmaşa, böyle bir karışıklıkta doğru kağıdı hemen bulmak zor. Banknot dizisi sıralanmalıdır.
İlki 1000 rublelik bir banknot ve hemen ardından - 100. Yüz tane alıp önüne yerleştiriyoruz. Arka arkaya üçüncü 500 ruble, bunun için doğru yer yüz ile bin arasındadır.
Aynı şekilde, gezinmeyi kolaylaştırmak için "Aptal" oynarken alınan kartları sıralıyoruz.
Operatörler ve yardımcı işlevler
Eklemeli sıralama yöntemi, sıralanacak bir ilk diziyi, bir karşılaştırma işlevini ve gerekirse öğeleri numaralandırma kuralını belirleyen bir işlevi girdi olarak alır. Bunun yerine en sık kullanılannormal döngü ifadesi.
İlk öğenin kendisi sıralı bir kümedir, dolayısıyla karşılaştırma ikinciden başlar.
Algoritma genellikle iki değeri değiş tokuş etmek (takas) için bir yardımcı işlev kullanır. Bellek tüketen ve kodu biraz yavaşlatan ek bir geçici değişken kullanır.
Bir alternatif, bir grup öğeyi kütle kaydırmak ve ardından mevcut olanı boş alana eklemektir. Bu durumda, bir sonraki öğeye geçiş, karşılaştırma, doğru sırayı gösteren olumlu bir sonuç verdiğinde gerçekleşir.
Uygulama örnekleri
Belirli uygulama büyük ölçüde kullanılan programlama diline, sözdizimine ve yapılarına bağlıdır.
Değer alışverişi yapmak için geçici bir değişken kullanan klasik C uygulaması:
int i, j, sıcaklık; for (i=1; i =0; j--) { if (dizi[j] < temp) break; dizi[j + 1]=dizi[j]; dizi[j]=sıcaklık; } }
PHP Uygulaması:
function insertion_sort(&$a) { for ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Burada, önce sıralama koşuluyla eşleşmeyen tüm öğeler sağa kaydırılır ve ardından mevcut öğe boş alana eklenir.
while döngüsü kullanan Java kodu:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=dizi[öncekiAnahtar]; dizi[öncekiAnahtar]=currElem; öncekiAnahtar--; } } }
Kodun genel anlamı değişmeden kalır: dizinin her elemanı sırayla öncekilerle karşılaştırılır ve gerekirse onlarla değiştirilir.
Tahmini çalışma süresi
Açıkçası, en iyi durumda, algoritmanın girişi zaten doğru şekilde sıralanmış bir dizi olacaktır. Bu durumda, algoritmanın değişim yapmadan her bir elemanı doğru yerde olduğundan emin olmak için kontrol etmesi gerekecektir. Bu nedenle, çalıştırma süresi doğrudan orijinal O(n) dizisinin uzunluğuna bağlı olacaktır.
En kötü durum girişi, ters sırada sıralanmış bir dizidir. Bu, çok sayıda permütasyon gerektirecektir, çalışma zamanı işlevi, karesi alınan öğelerin sayısına bağlı olacaktır.
Tamamen sırasız bir dizi için tam permütasyon sayısı şu formül kullanılarak hesaplanabilir:
n(n-1)/2
burada n orijinal dizinin uzunluğudur. Bu nedenle, 100 öğeyi doğru sırada düzenlemek için 4950 permütasyon gerekir.
Ekleme yöntemi, küçük veya kısmen sıralanmış dizileri sıralamak için çok etkilidir. Ancak, hesaplamaların yüksek karmaşıklığı nedeniyle her yere uygulanması önerilmez.
Algoritma, daha birçok karmaşık sıralama yönteminde yardımcı olarak kullanılır.
Eşit değerleri sırala
Ekleme algoritması, sözde kararlı türlere aittir. Anlamı,özdeş öğeleri değiştirmez, ancak orijinal sıralarını korur. Kararlılık indeksi birçok durumda doğru sıralama için önemlidir.
Yukarıdaki, bir dansta eklemeli sıralamanın harika bir görsel örneğidir.
