Gruntle Software & Testing

Örneklerle C++'da Ekleme Sıralaması

Tarafından Stewart TristianYayınlanma tarihi Yayınlandı Kılavuzlar

Klasik Örneklerle Ekleme Sıralamasına Derinlemesine Bir Bakış.

Ekleme sıralaması, elde kart oynadığımız şekilde görülebilen bir sıralama tekniğidir. Bir desteye herhangi bir kartı nasıl yerleştirir veya çıkarırsak, ekleme sıralaması da benzer şekilde çalışır.

Ekleme sıralama algoritması tekniği, Kabarcık sıralama ve Seçim sıralama tekniklerinden daha verimlidir, ancak Quicksort ve Merge sort gibi diğer tekniklerden daha az verimlidir.

Genel Bakış

Ekleme sıralama tekniğinde, ikinci elemandan başlarız ve onu ilk elemanla karşılaştırır ve uygun bir yere koyarız. Daha sonra bu işlemi sonraki elemanlar için gerçekleştiririz.

Her elemanı önceki tüm elemanlarıyla karşılaştırır ve elemanı uygun konumuna yerleştirir veya ekleriz. Ekleme sıralama tekniği, daha az sayıda elemana sahip diziler için daha uygundur. Ayrıca bağlantılı listeleri sıralamak için de kullanışlıdır.

Bağlı listelerde bir sonraki elemana (tek bağlı liste olması durumunda) ve bir önceki elemana (çift bağlı liste olması durumunda) bir işaretçi bulunur. Bu nedenle, bir bağlı liste için ekleme sıralamasını uygulamak daha kolay hale gelir.

Bu eğitimde Insertion sort hakkında her şeyi keşfedelim.

Genel Algoritma

Adım 1 : K = 1 ila N-1 için 2 ila 5. Adımları tekrarlayın

Adım 2 : set temp = A[K]

Adım 3 : J = K - 1 kümesi

Adım 4 : Repeat while temp <=A[J]

A[J + 1] = A[J] olarak ayarlayın

J = J - 1 olarak ayarlayın

[iç döngünün sonu]

Adım 5 : A[J + 1] = temp olarak ayarlayın

[döngü sonu]

Adım 6 : Çıkış

Bu nedenle, ekleme sıralama tekniğinde, ilk elemanın her zaman sıralı olduğunu varsaydığımız için ikinci elemandan başlarız. Daha sonra ikinci elemandan son elemana kadar, her elemanı önceki tüm elemanlarla karşılaştırır ve o elemanı uygun konuma yerleştiririz.

Sözde kod

Ekleme sıralaması için sözde kod aşağıda verilmiştir. 

 yordam insertionSort(dizi,N ) dizi - sıralanacak dizi N- eleman sayısı begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = dizi[i] freePosition = i //elemanı yerleştirmek için boş konumu bul whilefreePosition> 0 and dizi[freePosition -1]>insert_val do: dizi [freePosition] = dizi [freePosition -1] freePosition = freePosition -1 end while //insertserbest konumdaki sayı dizi [freePosition] = insert_val end for end procedure

Yukarıda Insertion sort için sözde kod verilmiştir, şimdi bu tekniği aşağıdaki örnekte göstereceğiz.

İllüstrasyon

Sıralanacak dizi aşağıdaki gibidir:

Şimdi her geçiş için mevcut elemanı önceki tüm elemanlarla karşılaştırıyoruz. Yani ilk geçişte ikinci elemanla başlıyoruz.

Bu nedenle, N sayıda eleman içeren bir diziyi tamamen sıralamak için N sayıda geçişe ihtiyacımız vardır.

Yukarıdaki örnek tablo şeklinde özetlenebilir:

Geçmek Sıralanmamış liste karşılaştırma Sıralanmış liste
1 {12,3,5,10,8,1} {12,3} {3,12,5,10,8,1}
2 {3,12,5,10,8,1} {3,12,5} {3,5,12,10,8,1}
3 {3,5,12,10,8,1} {3,5,12,10} {3,5,10,12,8,1}
4 {3,5,10,12,8,1} {3,5,10,12,8} {3,5,8,10,12,1}
5 {3,5,8,10,12,1} {3,5,8,10,12,1} {1,3,5,8,10,12}
6 {} {} {1,3,5,8,10,12}

Yukarıdaki resimde gösterildiği gibi, ilk elemanın her zaman sıralı olduğunu varsaydığımız için 2. elemanla başlıyoruz. Bu nedenle, ikinci elemanı birinciyle karşılaştırarak başlıyoruz ve ikinci eleman birinciden küçükse konumu değiştiriyoruz.

Bu karşılaştırma ve değiştirme işlemi iki elemanı uygun yerlerine yerleştirir. Daha sonra, üçüncü elemanı önceki (birinci ve ikinci) elemanlarla karşılaştırırız ve üçüncü elemanı uygun yere yerleştirmek için aynı prosedürü uygularız.

Bu şekilde, her geçişte bir elemanı yerine yerleştiririz. İlk geçişte, ikinci elemanı yerine yerleştiririz. Bu nedenle, genel olarak, N elemanı uygun yerlerine yerleştirmek için N-1 geçişe ihtiyacımız vardır.

Daha sonra, C++ dilinde Insertion sort tekniği uygulamasını göstereceğiz.

C++ Örneği 

 #include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<"\nGirdi listesi \n"; for(int i=0;i<10;i++) { cout < ="" 
 Çıktı: 
 Girdi listesi 
 12 4 3 1 15 45 33 21 10 2 
 Sıralanmış liste 
 1 2 3 4 10 12 15 21 33 45 
 Daha sonra, Insertion sort tekniğinin Java uygulamasını göreceğiz. 
 Java Örneği 
 public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println("Girilen eleman listesi..."); for(int i=0;i<10;i++) { System.out.print(myarray[i] + " "); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println("\sıralanmış eleman listesi..."); for(inti=0;i<10;i++) { System.out.print(myarray[i] + " "); } } } 
 Çıktı: 
 Girdi öğe listesi ... 
 12 4 3 1 15 45 33 21 10 2 
 öğelerin sıralanmış listesi ... 
 1 2 3 4 10 12 15 21 33 45 
 Her iki uygulamada da sıralamaya dizinin 2. elemanından başladığımızı (döngü değişkeni j = 1) ve mevcut elemanı önceki tüm elemanlarla tekrar tekrar karşılaştırdığımızı ve ardından mevcut eleman önceki tüm elemanlarla aynı sırada değilse, elemanı doğru konuma yerleştirmek için sıraladığımızı görebiliriz. 
 Ekleme sıralaması en iyi sonucu verir ve dizi kısmen sıralanmışsa daha az geçişle tamamlanabilir. Ancak liste büyüdükçe performansı düşer. Ekleme sıralamasının bir başka avantajı da Kararlı bir sıralama olmasıdır, yani listedeki eşit öğelerin sırasını korur. 
 Ekleme Sıralama Algoritmasının Karmaşıklık Analizi 
 Sözde koddan ve yukarıdaki çizimden, ekleme sıralaması, kabarcık sıralaması veya seçim sıralaması ile karşılaştırıldığında verimli bir algoritmadır. for döngüsü ve mevcut koşulları kullanmak yerine, dizi sıralandığında daha fazla ekstra adım gerçekleştirmeyen bir while döngüsü kullanır. 
 Bununla birlikte, sıralanmış diziyi Ekleme sıralama tekniğine aktarsak bile, dış for döngüsünü yürütmeye devam edecek ve böylece zaten sıralanmış bir diziyi sıralamak için n sayıda adım gerektirecektir. Bu, ekleme sıralamanın en iyi zaman karmaşıklığını N'nin doğrusal bir fonksiyonu haline getirir; burada N dizideki eleman sayısıdır. 
 Bu nedenle, Ekleme sıralama tekniği için çeşitli karmaşıklıklar aşağıda verilmiştir: 
 En kötü durum zaman karmaşıklığı  O(n 2 ) 
 En iyi durum zaman karmaşıklığı  O(n) 
 Ortalama zaman karmaşıklığı  O(n 2 ) 
 Uzay karmaşıklığı  O(1) 
 Bu karmaşıklıklara rağmen, Bubble sort ve Selection sort gibi diğer sıralama teknikleriyle karşılaştırıldığında Insertion sort'un en verimli algoritma olduğu sonucuna varabiliriz. 
 Sonuç 
 Ekleme sıralaması, şimdiye kadar tartışılan üç teknik arasında en verimli olanıdır. Burada, ilk elemanın sıralandığını ve ardından her elemanı önceki tüm elemanlarla tekrar tekrar karşılaştırdığını ve ardından mevcut elemanı dizideki doğru konumuna yerleştirdiğini varsayıyoruz. 
 Bu eğitimde, Ekleme sıralamasını tartışırken, öğeleri 1'lik bir artış kullanarak karşılaştırdığımızı ve ayrıca bitişik olduklarını fark ettik. Bu özellik, sıralanmış listeyi elde etmek için daha fazla geçiş gerektirmesine neden olur. 
 Gelecek eğitimimizde, Seçim sıralamasına göre bir iyileştirme olan "Kabuk sıralaması" konusunu ele alacağız. 
 Kabuk sıralamada, listeyi birbirinden "aralıklı" bitişik olmayan öğeler içeren alt listelere böldüğümüz "artış" veya "boşluk" olarak bilinen bir değişken kullanırız. Kabuk sıralama, Ekleme sıralamasına kıyasla daha az geçiş gerektirir ve ayrıca daha hızlıdır. 
 Gelecek derslerimizde, veri listelerini sıralamak için "Böl ve yönet" stratejisini kullanan iki sıralama tekniği olan "Quicksort" ve "Mergesort" hakkında bilgi edineceğiz.
Başa dön