Eklemeli Sıralama (İngilizce: Insertion Sort), bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır. Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır. Ancak buna karşın bazı artıları da vardır:
- Uygulaması kolaydır.
- Küçük Veri kümeleri üzerinde kullanıldığında verimlidir.
- Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir.
- Karmaşıklığı olan seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir.
- Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez)
- Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez.
- Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur. Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir.
Eklemeli sıralama | |
---|---|
Eklemeli sıralama algoritmasının rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek. | |
Sınıf | Sıralama algoritması |
Veri yapısı | Dizi |
Zaman karmaşıklığı | O(n²) |
En iyi | Genellikle değil |
Alan karmaşıklığı | O(1) |
İnsanlar herhangi bir şeyi (örneğin, iskambil kartları) sıralarken, çoğu durumda eklemeli sıralamaya benzer bir yöntem kullanırlar.
Çalışma Prensibi
Eklemeli Sıralama dizi içerisindeki bir girdinin ait olduğu yere oturtularak ilerlenmesi ve bu sayede her döngüde kontrol edilmesi gereken girdi sayısını azaltması prensibi ile çalışır. Bu durumu iskambil kağıtlarını elimizde dizmeye benzetebiliriz. İşaretlenen kağıt/girdi kendisinden önce ve kendisinden daha büyük bir sayı kalmayana kadar başa çekilir. Arkasında kalan bütün indisler ise birer adım geriye düşer böylece bu döngü içerisindeki her adım bize, işaretlenen tüm girdilerin kendi sıralarında, kendilerinden önce sadece bu girdiden küçük sayıların kaldığını garanti eder.
Aşama aşama bir örnek
8 2 4 9 3 6 --- > Bu sırasız, ham dizimiz.
8* 2 4 9 3 6 --- > Dizinin ilk indisi olan 8 seçildi. Öncesinde başka bir değer olmadığı için bir sonraki aşamaya geçiliyor.
8 2* 4 9 3 6 --- > Dizinin ikinci indisi olan 2 seçildi ve dizinin daha önce şu an tuttuğumuz 2 sayısından daha büyük bir değer oldukça başa taşınacak ve 8 ile yer değişecektir.
2 8 4* 9 3 6 --- > Benzer işlemleri bütün indislere sırası ile uyguluyoruz.
2 4 8 9* 3 6
2 4 8 9 3* 6
2 3 4 8 9 6*
2 3 4 6 8 9 --- > Sıralanmış dizimiz.
Bu örnekte * ile işaretlenmiş sayılar elde tutulan ve gerisinde kalanlar ile kıyaslanan sayıyı ; _ ile işaretlenmiş indisler ise elde tutulan sayının çekilebildiği en geri indisi göstermektedir.
Sözde Kodu(Pseudo Code)
insertionSort(array A) for i = 1 to length[A-1] do value = A[i] j = i-1 while j >= 0 and A[j] > value A[j + 1] = A[j] j = j-1 A[j+1] = value
Karmaşıklık Hesabı
Eklemeli sıralama algoritmasının zaman karmaşıklığı hesaplanırken, yapılan karşılaştırmalar ve yer değiştirmeler dikkate alınır. Eklemeli sıralama algoritması elemanlı bir listede, ikinci eleman için en fazla 1 karşılaştırma ve 1 yer değiştirme yapar, üçüncü eleman için 2 karşılaştırma ve 2 yer değiştirme, dördüncü eleman için 3 karşılaştırma ve 3 yer değiştirme yapar. Bu şekilde son eleman için en fazla karşılaştırma ve yer değiştirme yapar. Listedeki bütün elemanlar için yapılan karşılaştırmaların ve yer değiştirmelerin toplamı
yapar. Hesaplamalar sonucunda elde edilen değerinin asimptotik üst sınırı değerini verir.
En kötü başarım: Eklemeli sıralama algoritması en kötü durumda, örneğin liste tersten sıralıysa karmaşıklıkla çalışır.
En iyi başarım: Eklemeli sıralama algoritması en iyi durumda, örneğin liste sıralıysa sadece karşılaştırma yapar ve karmaşıklıkla çalışır.
Ortalama başarım: Eklemeli sıralama algoritması ortalama karmaşıklıkla çalışır.
Notlar
Kaynakça
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. . Section 5.2.1: Sorting by Insertion, pp. 80–105.
Dış bağlantılar
- Analyze Insertion Sort in an online Javascript IDE 10 Mayıs 2008 tarihinde Wayback Machine sitesinde .
- Insertion Sort Java Applet 29 Ekim 2007 tarihinde Wayback Machine sitesinde .
- on LiteratePrograms
- Pointers to
- , all the implementation in Java.
- C/C++ implementation for a binary insertion sort[]
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Eklemeli Siralama Ingilizce Insertion Sort bilgisayar bilimlerinde kullanilan ve sirali diziyi her adimda oge oge olusturan bir siralama algoritmasidir Buyuk dizilerle calisildiginda hizli siralama birlestirmeli siralama ve yigin siralamasi gibi daha gelismis siralama algoritmalarindan daha verimsiz calisir Ancak buna karsin bazi artilari da vardir Uygulamasi kolaydir Kucuk Veri kumeleri uzerinde kullanildiginda verimlidir Cogunlugu zaten siralanmis olan diziler uzerinde kullanildiginda verimlidir Karmasikligi O n2 displaystyle mathcal O n 2 olan secmeli siralama ve kabarcik siralamasi gibi cogu yalin siralama algoritmalarindan daha verimlidir Kararli bir siralama algoritmasidir degeri esit olan ogelerin asil listedeki goreceli konumlarini degistirmez Siralanacak diziyi yerinde siralar ek bir bellek alani gerektirmez Siralanacak dizinin hepsinin algoritmanin girdisi olmasina gerek yoktur Dizi parca parca da alinabilir ve siralama islemi sirasinda diziye yeni veriler eklenebilir Eklemeli siralamaEklemeli siralama algoritmasinin rastgele uretilmis sayilari nasil siraya dizdigini gosteren bir ornek SinifSiralama algoritmasiVeri yapisiDiziZaman karmasikligiO n En iyiGenellikle degilAlan karmasikligiO 1 Insanlar herhangi bir seyi ornegin iskambil kartlari siralarken cogu durumda eklemeli siralamaya benzer bir yontem kullanirlar Calisma PrensibiEklemeli Siralama dizi icerisindeki bir girdinin ait oldugu yere oturtularak ilerlenmesi ve bu sayede her dongude kontrol edilmesi gereken girdi sayisini azaltmasi prensibi ile calisir Bu durumu iskambil kagitlarini elimizde dizmeye benzetebiliriz Isaretlenen kagit girdi kendisinden once ve kendisinden daha buyuk bir sayi kalmayana kadar basa cekilir Arkasinda kalan butun indisler ise birer adim geriye duser boylece bu dongu icerisindeki her adim bize isaretlenen tum girdilerin kendi siralarinda kendilerinden once sadece bu girdiden kucuk sayilarin kaldigini garanti eder Asama asama bir ornek 8 2 4 9 3 6 gt Bu sirasiz ham dizimiz 8 2 4 9 3 6 gt Dizinin ilk indisi olan 8 secildi Oncesinde baska bir deger olmadigi icin bir sonraki asamaya geciliyor 8 2 4 9 3 6 gt Dizinin ikinci indisi olan 2 secildi ve dizinin daha once su an tuttugumuz 2 sayisindan daha buyuk bir deger oldukca basa tasinacak ve 8 ile yer degisecektir 2 8 4 9 3 6 gt Benzer islemleri butun indislere sirasi ile uyguluyoruz 2 4 8 9 3 6 2 4 8 9 3 6 2 3 4 8 9 6 2 3 4 6 8 9 gt Siralanmis dizimiz Bu ornekte ile isaretlenmis sayilar elde tutulan ve gerisinde kalanlar ile kiyaslanan sayiyi ile isaretlenmis indisler ise elde tutulan sayinin cekilebildigi en geri indisi gostermektedir Sozde Kodu Pseudo Code insertionSort array A for i 1 to length A 1 do value A i j i 1 while j gt 0 and A j gt value A j 1 A j j j 1 A j 1 valueKarmasiklik HesabiEklemeli siralama algoritmasinin zaman karmasikligi hesaplanirken yapilan karsilastirmalar ve yer degistirmeler dikkate alinir Eklemeli siralama algoritmasi n textstyle n elemanli bir listede ikinci eleman icin en fazla 1 karsilastirma ve 1 yer degistirme yapar ucuncu eleman icin 2 karsilastirma ve 2 yer degistirme dorduncu eleman icin 3 karsilastirma ve 3 yer degistirme yapar Bu sekilde son eleman icin en fazla n 1 textstyle n 1 karsilastirma ve n 1 textstyle n 1 yer degistirme yapar Listedeki butun elemanlar icin yapilan karsilastirmalarin ve yer degistirmelerin toplami 2 1 2 3 4 n 2 n 1 2 n n 1 2 n n 1 displaystyle 2 1 2 3 4 n 2 n 1 2 n n 1 2 n n 1 yapar Hesaplamalar sonucunda elde edilen n n 1 displaystyle n n 1 degerinin asimptotik ust siniri O n2 textstyle O n 2 degerini verir En kotu basarim Eklemeli siralama algoritmasi en kotu durumda ornegin liste tersten siraliysa O n2 textstyle O n 2 karmasiklikla calisir En iyi basarim Eklemeli siralama algoritmasi en iyi durumda ornegin liste siraliysa sadece n 1 textstyle n 1 karsilastirma yapar ve O n textstyle O n karmasiklikla calisir Ortalama basarim Eklemeli siralama algoritmasi ortalama O n2 textstyle O n 2 karmasiklikla calisir Notlar Robert Sedgewick Algorithms Addison Wesley 1983 chapter 8 p 95 6 006 Introduction to Algorithms PDF 1 Mayis 2015 tarihinde kaynagindan PDF erisim tarihi 17 Mart 2021 Robert Sedgewick Kevin Wayne Algorithms 4th Edition Addison Wesley 2011 chapter 2 p 250 KaynakcaDonald Knuth The Art of Computer Programming Volume 3 Sorting and Searching Second Edition Addison Wesley 1998 ISBN 0 201 89685 0 Section 5 2 1 Sorting by Insertion pp 80 105 Dis baglantilarAnalyze Insertion Sort in an online Javascript IDE 10 Mayis 2008 tarihinde Wayback Machine sitesinde Insertion Sort Java Applet 29 Ekim 2007 tarihinde Wayback Machine sitesinde on LiteratePrograms Pointers to all the implementation in Java C C implementation for a binary insertion sort olu kirik baglanti