Merhaba,
Sıralama algoritmaları yazı dizisinin ikincisi, Eklemeli sıralama algoritması ile karşınızdayım. Eklemeli sıralamanın detaylarını beraber inceleyelim.
Sıralama ve arama tekniklerinden pek çok programda yararlanılmaktadır. Günlük yaşamımızda elemanların sıralı tutulduğu listeler yaygın olarak kullanılmaktadır. Sıralama, sıralanacak elemanlar bellekte ise içsel kayıtların bazıları ikincil bellek ortamında ise dışsal sıralama olarak adlandırılır.
Sıralama Algoritmaları hakkında yazdığımız başlığı da alıntı yaptıktan sonra genel bir tanım ile giriş yapalım.
Insertion Sort
Yerleştirerek sıralama işlevi belirli bir anda dizinin belirli bir kısmını sıralı tutarak ve bu kısmı her adımda biraz daha genişleterek çalışmaktadır Sıralı kısım işlev son bulunca dizinin tamamına ulaşmaktadır. Elemanların sırasına uygun olarak listeye tek tek eklenmesi ile gerçekleşen sıralama tipidir.
Insertion Sort Kodu
void insertSort(int x[ ], int n) { int i,k,y; for( k=1; k<n; k++) { y=x[k]; for(i=k-1;i>=0&&y<x[i]; i--) { x[i+1]=x[i]; } x[i+1]=y; } }
Insertion Sort Performansı
•Eğer veriler sıralı ise her turda bir karşılaştırma yapılacaktır ve O(n) olacakır.
•Veriler ters sıralı ise toplam karşılaştırma sayısı: (n-1)+(n-2)+….+3+2+1= n*(n+1)/2= O(n²) olacaktır.
•Simple Insertion Sort’un ortalama karşılaştırma sayısı ise O(n²)’dir.
•Selection sort ve Simple Insertion sort, Bubble sort a göre daha etkidir. Selection Sort insertion sort’tan daha az atama işlemi yaparken daha fazla karşılaştırma işlemi yapar.
•Bu nedenle Selecton Sort, az elemanlı veri grupları için(atamaların süresi çok fazla olmaz) ve karşılaştırmaların daha az yük getireceği asit anahtarlı durumlarda uygundur.
•Tam tersi için, insertion sort uygundur. Elemanlar bağlı listedeler ise araya eleman eklemelerde veri kaydırma olmayacağından insertion sort mantığı uygundur.
•n’in büyük değerleri içi quicksort , insertion sort ve selection sort’tan daha etkindir Quick Sort’u kullanmaya başlama noktası yaklaşık 30 elemanlı durumlardır. Daha az elemanın sıralanması gerektiğinde insertion sort kullanılabilir.
Bu yazımızda da insertion sort nasıl çalışır, insertion sort nedir, performans durumu ve çalışma zamanı nelerdir bunlardan bahsettik. Anlayamadığınız ya da eksik gördüğünüz kısımlar var ise bana yorumlar aracılığı ile iletebilirsiniz.
Teşekkürler!