Bu yazımızda Insertion sort Algoritmasını ele alacağız. Ekleme sıralamasının çalışma prosedürü de basittir. Bu makale, sınavlarında bir soru olarak eklemeli sıralamayla karşılaşabilecekleri için öğrenciler için çok yararlı ve ilginç olacaktır. Bu nedenle konuyu tartışmak önemlidir.
Ekleme sıralaması, ellerdeki oyun kartlarının sıralamasına benzer şekilde çalışır. Kart oyununda ilk kartın zaten sıralandığı varsayılır ve ardından sıralanmamış bir kart seçeriz. Seçilen sıralanmamış kart ilk karttan büyükse sağ tarafa yerleştirilecektir; aksi takdirde sol tarafa yerleştirilecektir. Benzer şekilde, sıralanmamış tüm kartlar alınır ve tam yerlerine konur.
Aynı yaklaşım ekleme sıralamasında da uygulanır. Eklemeli sıralamanın arkasındaki fikir, ilk önce bir öğeyi alıp, onu sıralanmış dizi boyunca yinelemektir. Kullanımı basit olmasına rağmen, ortalama durumda ve en kötü durumda ekleme sıralamasının zaman karmaşıklığı nedeniyle büyük veri kümeleri için uygun değildir. Açık2) n, öğelerin sayısıdır. Eklemeli sıralama, yığın sıralama, hızlı sıralama, birleştirme sıralaması vb. gibi diğer sıralama algoritmalarından daha az verimlidir.
Ekleme sıralamasının aşağıdakiler gibi çeşitli avantajları vardır:
- Basit uygulama
- Küçük veri kümeleri için verimli
- Uyarlanabilir, yani zaten büyük ölçüde sıralanmış veri kümeleri için uygundur.
Şimdi ekleme sıralamasının algoritmasını görelim.
Algoritma
Ekleme sıralamasını gerçekleştirmenin basit adımları aşağıda listelenmiştir:
Aşama 1 - Öğe ilk öğeyse, zaten sıralandığını varsayalım. 1. dönüş
Java liste düğümü
Adım 2 - Bir sonraki öğeyi seçin ve onu ayrı bir yerde saklayın. anahtar.
Aşama 3 - Şimdi karşılaştırın anahtar sıralanmış dizideki tüm öğelerle birlikte.
Adım 4 - Sıralanan dizideki öğe geçerli öğeden küçükse sonraki öğeye geçin. Aksi halde dizideki daha büyük öğeleri sağa doğru kaydırın.
Adım 5 - Değeri girin.
Adım 6 - Dizi sıralanana kadar tekrarlayın.
Ekleme sıralama algoritmasının çalışması
Şimdi ekleme sıralama algoritmasının çalışmasına bakalım.
Eklemeli sıralama algoritmasının çalışmasını anlamak için sıralanmamış bir diziyi ele alalım. Bir örnek üzerinden ekleme sıralamasını anlamak daha kolay olacaktır.
Dizinin elemanları şöyle olsun:
Başlangıçta, ilk iki öğe ekleme sıralamasında karşılaştırılır.
Burada 31, 12'den büyüktür. Bu, her iki öğenin de zaten artan sırada olduğu anlamına gelir. Yani şimdilik 12, sıralanmış bir alt dizide saklanıyor.
Şimdi sonraki iki öğeye geçin ve bunları karşılaştırın.
Burada 25, 31'den küçüktür. Yani 31 doğru konumda değil. Şimdi 31'i 25 ile değiştirin. Ekleme sıralaması, değiştirmenin yanı sıra sıralanan dizideki tüm öğeleri de kontrol edecektir.
Şimdilik, sıralanan dizinin yalnızca bir öğesi vardır, yani 12. Yani 25, 12'den büyüktür. Dolayısıyla, sıralanan dizi, yer değiştirdikten sonra sıralanmış olarak kalır.
Şimdi sıralanan dizideki iki öğe 12 ve 25'tir. Sonraki öğeler olan 31 ve 8'e ilerleyin.
Hem 31 hem de 8 sıralanmamıştır. Öyleyse onları değiştirin.
Değiştirildikten sonra 25 ve 8 numaralı elemanlar sıralanmaz.
Öyleyse onları değiştirin.
Şimdi, 12 ve 8 numaralı öğeler sıralanmamıştır.
Öyleyse onları da değiştirin.
Artık sıralanan dizide 8, 12 ve 25 olan üç öğe var. Sonraki öğeler olan 31 ve 32'ye geçin.
Bu nedenle zaten sıralanmışlardır. Artık sıralanan dizi 8, 12, 25 ve 31'i içeriyor.
Sonraki 32 ve 17 numaralı öğelere geçin.
17, 32'den küçüktür. O halde yerlerini değiştirin.
Yer değiştirme 31 ve 17'yi sıralanmamış hale getirir. Öyleyse onları da değiştirin.
Şimdi, yer değiştirme 25 ve 17'yi sıralanmamış hale getiriyor. Bu nedenle, değiştirme işlemini tekrar gerçekleştirin.
Artık dizi tamamen sıralanmıştır.
Ekleme sıralama karmaşıklığı
Şimdi en iyi durumda, ortalama durumda ve en kötü durumda ekleme sıralamasının zaman karmaşıklığını görelim. Ayrıca ekleme sıralamasının uzay karmaşıklığını da göreceğiz.
1. Zaman Karmaşıklığı
| Dava | Zaman Karmaşıklığı |
|---|---|
| En iyi senaryo | Açık) |
| Ortalama Durum | Açık2) |
| En kötü durumda | Açık2) |
2. Uzayın Karmaşıklığı
| Uzay Karmaşıklığı | Ç(1) |
| Stabil | EVET |
- Ekleme sıralamasının uzay karmaşıklığı O(1)'dir. Bunun nedeni, ekleme sıralamasında takas için fazladan bir değişkenin gerekli olmasıdır.
Ekleme sıralamasının uygulanması
Şimdi farklı programlama dillerinde ekleme sıralamalı programlara bakalım.
Program: C dilinde eklemeli sıralamayı uygulayan bir program yazın.
#include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are -
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j >= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are -
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for ($i = 1; $i = 0 && $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> Çıktı:
Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.
Bu makale sadece algoritma ile sınırlı değildi. Ayrıca algoritmanın karmaşıklığını, çalışmasını ve farklı programlama dillerindeki uygulanmasını da tartıştık.