www.fatihkabakci.com

Personal Website and Computer Science TUR EN

EKLEYEREK SIRALAMA(INSERTION SORT)

Last update: 10/7/2014 10:44:00 PM

Yazan:Fatih KABAKCI

Sıralama algoritmalarının içerisinde yer alan Insertion Sort yani ekleyerek sıralama algoritmasının iki farklı metodu bulunmaktadır.Anlatımımı algoritmanın iki ozelliği ile ayrı ayrı betimleyeceğim.Bir Array’a elemanlar atanırken önce büyüklük-küçüklük durumuna göre bakılır.Eklenecek sayı,dizide bulunan elemanlardan büyük bir sayı ise sorun yoktur ve dizinin boş indeksine eklenir.Fakat eklenecek sayı dizideki herhangi bir sayıdan küçük ise,ekleneceği konumdan itibaren listedeki sayılar 1’er sıra kaydırılacaktır ki ekleyeceğimiz sayıya yer açılmış olsun.Bir örnekle konumuzu anlatmaya devam edelim.Aynı veri türlerinden oluşacak ve içi boş olan bir kümemiz olsun.Şimdi bu kümemize elemanlar ekleyelim.

Örneğin,ilk olarak 7 sayısını ekliyoruz.

7 - - - -. -> 7 sayısı listemizde oluşturuldu.

Daha sonra 5 sayısını eklemek istediğimizi varsayalım.Ekleme yapılmadan önce eklenecek sayı ile listedeki elemanlar karşılaştırılacaktır.Listemizde şuan sadece 7 sayısı bulunduğundan yalnızca 1 sefer tarama yapılacaktır.Ekleyeceğimiz 5 sayısı 7 sayısından küçük olduğu için listemizde bulunan 7 sayısı bir kayarak 5 sayısına yer açmış olur.Dolayısıyla 5 sayısı yeni yerine yerleşecektir.

5 7 - - -

Eklemeye yeni sayımız 8 ile devam ediyoruz.8 sayısı önce 5 ile test edecektir. 5<8 olduğu için,sıra 7’ye gelir.7<8 olduğu için ve başka test edecek sayı olmadığı için 8 sayısı listedeki ilk boş yere yerini alacaktır.Yeni durumda görünüm,

5 7 8 - - olacaktır.

Şimdi ise 6 sayısını eklemeye çalışalım.Dikkat edilirse 6 sayısı arada kalacak bir sayıdır ve 5’ten büyük fakat 7’den küçük bir sayıdır.O yüzden 5’ten sonraki tüm sayılar 1’er sıra kaydırılır.

5 – 7 8 - ancak 6 sayısına bu şekilde yer açılabilir,yeni durumda görünüm,

5 6 7 8 - olacaktır.

Son olarak 2 sayısını ekleyeceğimizi düşünelim.2 sayısı,listedeki ilk eleman olan 5 sayısı ile test edilecektir.2<5 olduğu için 2 sayısının yeri belirlenmiş olup, artık diğer elemanlarla test edilmesine gerek kalmaz.Çünkü 2 sayısı diğer elemanlardan zaten küçük olacaktır ve bakmak gereksizdir. Dolayısıyla listedeki 5 sayısından itibaren tüm sayılar 1’er sıra kaydırılacaktır. Nihayi dörünüm 2 5 6 7 8 şeklinde olacaktır.

Ekleyerek sıralama algoritmasının ilk versiyonu yukarıda anlatılan mantıkla çalışır.

2.Versiyon

Algoritmanın bir de 2.versiyonu bulunmaktadır.Bu versiyon derki,dizide bir sıralı bölüm olsun bir de düzensiz bölüm olsun.Yukarıdaki örneklerde bahsi geçen sayılar tek seferde diziye yerleştirilir.Yukarıdaki örneğimizdeki elemanların ekleme sırası ile dizimize elemanları yerleştirelim. 
7	5	8	6	2
Dizimizin bölmelerine bakılacak olursa siyah bölmedeki elemanlarımız düzensiz kısmımızdır,yani bu bölmeler taramaya tabi tutulmamış,henüz el atılmamış kısımlarıdır. Algoritmamızı yukarıda örneğimiz ile anlamaya çalışalım.İlk olarak yerleşik 7 sayısı ile bir sonraki dizi elemanı olan 5 karşılaştırılır.7>5 olduğundan yer değişikliği gerçekleşecektir ve ilk adımda tarama sona erecektir.(1.Adım) 
5	7	8	6	2
Bir sonraki adıma geçelim.dizimizin 1.indeksli elemanı olan 7 sayısı 8 ile kıyaslanacaktır.7<8 olduğundan değişiklik olmayacaktır.7 sayısı 5 sayısından büyük olduğu için değişiklik olmayacaktır.8 sayısı 7’den büyük olduğu için yer değiştirme işlemi sonlanacaktır.(2.Adım) 
5	7	8	6	2
İşleme 3.adımız ile devam ediyoruz.8 sayısı 6 ile kıyaslanacak.8>6 olduğundan yer değiştirilir. 
5	7	6	8	2
Fakat işlem bitmedi!Çünkü 6 sayısı 7 sayısından da küçüktür.bir değişiklik daha gerçekleşir ve yeni görünüm 
5	6	7	8	2
Şeklinde olacaktır.6>5 olduğu için 3.adımızda sonlanacaktır.(3.Adım)

Siyah bölmemizde kalan tek sayı 2. sırayla 8 sayısı 2 ile karşılaştırılacaktır.8>2 olduğu için yer değişikliği olacaktır.2 sayısı bakılmaya daha sonra 7,6 ve 5 ile bakılıp onlarla da sırasıyla değişikliğe gidecektir çünkü dizimizin en küçük elemanı görüldüğü üzere 2 dir. 
5	6	7	2	8
  
5	6	2	7	8

5	2	6	7	8

2	5	6	7	8
Görüldüğü üzere Insertion Sort algoritmasının 2.sıralanış modeli ilede sayılarımız sıralanmış oldu.

İki model arasında şu farkbulunur.ilk modelimizde hatırlanacağı gibi sayılarımız önce taratılıp sonra yerleştiriliyor idi.Fakat 2.modelimizde sayılar once rastgele yerleştirilerek,ilk sayıdan başlanır ve indeks numarasının 1 fazlası kadar sayı taraması yapılır. Yukarıdaki örnekte sayılarımızı tekrar ele alırsak,ilk sayımız dizimizin 0 numaralı indeksi 5 idi.5 sayısı 8 ile kıyaslandı ve ilk adım tamamlanmıştı.Yani 1 sefer tarama yapıldı.(Bilindiği üzere diziler 0 numaralı indis değerleri ile başlar).

Insertion sort algoritmasının en kötü durumda çalışacağı yer tersten sayıları düzenlerkendir.Örneğin, 5 4 3 2 1 olarak verilen bir sayı dizisinde N elemanlı bir dizi 2N tarama yaparak sonuca ulaşacaktır.

Analizi yapılan algoritmanın C dilindeki karşılığı verilmiştir.


Bağlı liste modeli kullanıldığında aynı algoritma aşağıdaki gibi verilebilir.


Son olarak algoritmanın 2.versiyonu yine aynı dilde verilirse,


şeklinde bir kod dilimi gerçeklenmiş olacaktır.
There has been no comment yet
Name:


Question/Comment
   Please verify the image




The Topics in Computer Science

Search this site for





 

Software & Algorithms

icon

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Programming Languages

icon

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. It can be used to create programs to control the behavior of a machine. Java,C, C++,C#

Database

icon

A database is an organized collection of data. The data are typically organized to model aspects of reality in a way that supports processes requiring information.

Hardware

icon

Computer hardware is the collection of physical elements that constitutes a computer system. Computer hardware refers to the physical parts or components of a computer such as the monitor, memory, cpu.

Web Technologies

icon

Web development is a broad term for the work involved in developing a web site for the Internet or an intranet. Html,Css,JavaScript,ASP.Net,PHP are one of the most popular technologies. J2EE,Spring Boot, Servlet, JSP,JSF, ASP

Mobile Technologies

icon

Mobile application development is the process by which application software is developed for low-power handheld devices, such as personal digital assistants, enterprise digital assistants or mobile phones. J2ME

Network

icon

A computer network or data network is a telecommunications network that allows computers to exchange data. In computer networks, networked computing devices pass data to each other along data connections.

Operating Systems

icon

An operating system is software that manages computer hardware and software resources and provides common services for computer programs. The OS is an essential component of the system software in a computer system. Linux,Windows

Computer Science

icon

Computer science is the scientific and practical approach to computation and its applications.A computer scientist specializes in the theory of computation and the design of computational systems.