Menü

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

  • Ana
  • Diğer
  • Örneklerle C ++ 'da Ekleme Sıralaması

insertion sort c with examples

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Klasik Örneklerle Sıralamaya Derinlemesine Bir Bakış.

Yerleştirme sıralaması, elimizdeki kartları oynadığımız şekilde görülebilen bir sıralama tekniğidir. Bir desteye herhangi bir kartı yerleştirme veya çıkarma şeklimiz, 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 etkilidir, ancak Hızlı Sıralama ve Birleştirme sıralaması gibi diğer tekniklerden daha az etkilidir.

=> En İyi C ++ Eğitim Öğreticilerine Buradan Göz Atın.

EKLEME SIRALAMA

Ne öğreneceksin:

Genel Bakış

Eklemeli sıralama tekniğinde, ikinci öğeden başlayıp onu birinci öğeyle karşılaştırıp uygun bir yere koyuyoruz. Daha sonra bu işlemi sonraki elemanlar için gerçekleştiriyoruz.

Her bir öğeyi önceki tüm öğeleriyle karşılaştırırız ve öğeyi uygun konumuna yerleştirir veya yerleştiririz. Ekleme sıralama tekniği, daha az sayıda öğeye sahip diziler için daha uygundur. Bağlantılı listeleri sıralamak için de kullanışlıdır.

php röportaj sorusu ve deneyim için cevap

Bağlı listelerin bir sonraki öğeye bir gösterici (tekil bağlantılı bir liste olması durumunda) ve önceki öğeye de bir gösterici (çift bağlantılı bir liste olması durumunda) vardır. Bu nedenle, bağlantılı bir liste için ekleme sıralaması uygulamak daha kolay hale gelir.

Bu eğiticide Ekleme sıralaması hakkında her şeyi inceleyelim.

Genel Algoritma

Aşama 1 : K = 1 ila N-1 için Adım 2 ila 5'i tekrarlayın
Adım 2 : sıcaklığı ayarla = A (K)
Aşama 3 : J = K - 1 olarak ayarlayın
4. adım : Sıcaklık sırasında tekrarlayın<=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) = sıcaklık olarak ayarlayın
(döngünün sonu)
6. Adım : çıkış

Böylece, ekleme sıralama tekniğinde, ilk öğenin her zaman sıralandığını varsaydığımız için ikinci öğeden başlarız. Sonra ikinci elemandan son elemana kadar, her bir elemanı önceki tüm elemanlarıyla karşılaştırır ve o elemanı uygun konuma getiririz.

Sözde kod

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

procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure

Yukarıda verilen, Ekleme sıralaması için sözde koddur, daha sonra bu tekniği aşağıdaki örnekte göstereceğiz.

İllüstrasyon

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

sıralanacak dizi

Şimdi her geçişte, mevcut öğeyi önceki tüm öğeleriyle karşılaştırıyoruz. Yani ilk geçişte ikinci elementle başlıyoruz.

Ekleme Sıralaması - İllüstrasyon

Bu nedenle, N sayıda öğe içeren bir diziyi tamamen sıralamak için N sayıda geçişe ihtiyacımız var.

Yukarıdaki çizim tablo şeklinde özetlenebilir:

GeçmekSıralanmamış listekarşılaştırmaSıralanmış liste
1{12,3,5,10,8,1}{12.3}{3,12,5,10,8,1}
iki{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 şekilde gösterildiği gibi, 2 ile başlıyoruzndilk elemanın her zaman sıralandığını varsaydığımız gibi. Bu nedenle, ikinci öğeyi birinciyle karşılaştırarak başlıyoruz ve ikinci öğe birinciden küçükse konumu değiştiriyoruz.

Bu karşılaştırma ve takas işlemi iki öğeyi uygun yerlerine konumlandırır. Daha sonra, üçüncü öğeyi önceki (birinci ve ikinci) öğeleriyle karşılaştırıyoruz ve üçüncü öğeyi uygun yere yerleştirmek için aynı prosedürü uyguluyoruz.

Bu şekilde her geçiş için yerine bir eleman yerleştiririz. İlk geçiş için ikinci elemanı yerine yerleştiriyoruz. Bu nedenle, genel olarak, N elementi uygun yerlerine yerleştirmek için N-1 geçişlerine ihtiyacımız var.

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

ürünleri şirketler için test etmek istiyorum

C ++ Örneği

#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<' Input list is '; for(int i=0;i<10;i++) { cout <

Çıktı:

Giriş listesi

12 4 3 1 15 45 33 21 10 2

Sıralanmış liste

1 2 3 4 10 12 15 21 33 45

Ardından, Ekleme sıralama 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('Input list of elements ...'); 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(' sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } }

Çıktı:

Elemanların giriş listesi…

12 4 3 1 15 45 33 21 10 2

sıralı öğe listesi…

1 2 3 4 10 12 15 21 33 45

Her iki uygulamada da, 2'den sıralamaya başladığımızı görebiliriz.nddizinin öğesi (döngü değişkeni j = 1) ve mevcut öğeyi tekrar tekrar önceki tüm öğeleriyle karşılaştırın ve ardından geçerli öğe önceki tüm öğeleriyle uyumlu değilse öğeyi doğru konumuna yerleştirmek için sıralayın.

Ekleme sıralaması en iyi sonucu verir ve dizi kısmen sıralanırsa daha az geçişle tamamlanabilir. Ancak liste büyüdükçe performansı azalır. Ekleme sıralamanın bir başka avantajı da Kararlı bir sıralama olmasıdır, yani listedeki eşit öğelerin sırasını korur.

android'de apk dosyası nasıl açılır

Ekleme Sıralama Algoritmasının Karmaşıklık Analizi

Sözde koddan ve yukarıdaki resimden, eklemeli sıralama, balonla sıralama veya seçim sıralamasıyla karşılaştırıldığında verimli algoritmadır. For döngüsü ve mevcut koşulları kullanmak yerine, dizi sıralandığında fazladan adım gerçekleştirmeyen bir while döngüsü kullanır.

Bununla birlikte, sıralı diziyi Ekleme sıralama tekniğine iletsek bile, dış for döngüsünü çalıştıracak ve böylece önceden sıralanmış bir diziyi sıralamak için n sayıda adım gerektirecektir. Bu, yerleştirme sıralaması için en iyi zaman karmaşıklığını, N'nin dizideki öğelerin sayısı olduğu N'nin doğrusal bir işlevi yapar.

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 vaka süresi karmaşıklığıO (n)
Ortalama zaman karmaşıklığıO (n 2)
Uzay karmaşıklığıO (1)

Bu karmaşıklıklara rağmen, Kabarcık sıralama ve Seçim sıralama gibi diğer sıralama teknikleriyle karşılaştırıldığında, Ekleme sıralamanın 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 öğenin sıralandığını ve ardından her öğeyi önceki tüm öğeleriyle tekrar tekrar karşılaştırdığımızı ve ardından geçerli öğeyi dizideki doğru konumuna yerleştirdiğini varsayıyoruz.

Bu eğiticide, Ekleme sıralaması tartışılırken, öğeleri 1 artışını kullanarak karşılaştırdığımızı ve aynı zamanda bitişik olduklarını fark ettik. Bu özellik, sıralı listeyi almak için daha fazla geçiş gerektirmesine neden olur.

Yaklaşan eğitimimizde, Seçim sıralamasına göre bir gelişme olan 'Kabuk sıralaması' nı tartışacağız.

Kabuk sıralamasında, 'artış' veya 'boşluk' olarak bilinen bir değişken ekliyoruz ve bunu kullanarak listeyi birbirlerinden 'boşluk' olan bitişik olmayan öğeleri içeren alt listelere böleriz. Kabuk sıralama, Eklemeli sıralamaya kıyasla daha az geçiş gerektirir ve ayrıca daha hızlıdır.

Gelecekteki eğitimlerimizde, veri listelerini sıralamak için 'Böl ve yönet' stratejisini kullanan iki sıralama tekniği, 'Hızlı Sırala' ve 'Birleştirme' hakkında bilgi edineceğiz.

=> Yeni Başlayanlar C ++ Eğitim Kılavuzuna Buradan Dikkat Edin.

Önerilen Kaynaklar

^