www.fatihkabakci.com

Personal Website and Computer Science TUR EN

BIRLESTIREREK SIRALAMA(MERGE SORT)

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

Yazan:Fatih KABAKCI

Sıralama algoritmalarından özyinelemeli(recursive) yapısı ile tasarlanan merge sort,diğer sıralama algoritmalarında olduğu gibi aynı veri türlerinden oluşan bir eleman grubunu sıralamada kullanılır.Grubundaki elemanlarını tekli gruba kadar bölerek onları uygun şekilde sıralamaya sokar.Yani fonksiyonların böl ve yönet mantığını burada görmekteyiz.Algoritmamızı her zamanki gibi örneklerimizle açıklamaya çalışalım.

Yine kolay anlaşılması açısından int türünde bir dizimiz olsun ve bu karmaşık şekilde yerleşmiş sayılarımızı küçükten-büyüğe doğru sıralayalım.

8  3  4  1  10  12  2  şeklinde sıralanmış sayılarımız olsun.Ilk olarak bu sayılarımızı ortadan 2’ye bölelim.

8  3  4  1  &  10  12  2  ilk bölünmemiz gerçekleşti.Şimdi bir kez daha 2’ye bölerek gruplara ayırmaya çalışalım.

8  3  &  4  1 	  &	10  12  &  2   Aynı şekilde bölmeye devam edelim.      

8 & 3 /  4  & 1   //    10 & 12 & 2   Sayılarımız iki gruba ayrıldı(Sol grup,Sağ grup)
Dikkat edilirse şuana kadar sayılarımızı sadece ayırdık,onları daha sıralamadık! Önce sol grubumuzu sıralayacağız.

8 ile 3 kıyaslanıyor.3 < 8 olduğu için 2’li grubun içerisine ilk olarak 3 geliyor. 
3  8  &  4  1 (1.ADIM)
Şimdi 4 ile 1 kıyaslanıyor.1<4 olduğu için bu 2’li grubun içerisine ilk olarak 1 geliyor. 
Yeni durumda sol taraf,(2.ADIM)
3  8  &  1  4  şeklinde birleşmiş oldu.
Şimdi ise aradaki &(ampersand) karakterini kaldırarak bu 2’li 2 grubumuzu birleştirmeye çalışalım.Birleştirirken önce iki grubun da ilk sayılarını karşılaştırarak bakacağız. İlk olarak 3 ile 1 karşılaştırılır.1<3 olduğundan 1 yeni satırın ilk bölmesine yerleşmiş olur. 
1   *   *   *
3 8 & 4 şimdi 3 ile 4 sayıları karşılaştırılacak.3<4 olduğundan dizimizin sol tarafındaki 2.sayımızda belli oldu.(3) 
1   3   *   *
8 & 4 Son olarak bu iki sayı karşılaştırılır.4<8 olduğundan sırasıyla 4 sayısı dizinin 2.bolmesine,8 sayısı ise dizinin 3.bölmesine adını yazdırır. 
1 	 3	 4	 8
Nihayetinde dizimizin sol tarafı sıralanmış oldu.Aynı işlemler dizinin Sağ tarafı içinde yapılır. 
10  12  &  2
10  &  12  & 2
10 ile 12 karşılaştırılıyor.10 < 12 olduğu için 10 sayısı kendi grubunun(12 ile oluşturduğu 2’li grup) ilk sayısı oluyor.
10 12 & 2. şimdi 2 gurubun ilk elemanları karşılaştırılacak.10 > 2 olduğu için dizimizin sağ tarafının ilk elemanı belli oluyor.(2) 
2   *   *
10 < 12 olduğu için dizimizin sağ tarafıda tamamlanmış oluyor. 
2 	10	12

Dizimizin sol tarafı ->	1	 3	 4	 8 
Dizimizin sağ tarafı -> 2 	 10	 12
Şimdi bu iki tarafıda daha önceden yapmış olduğumuz teknik ile,ilk elemanlarını karşılaştırarak sıralamaya koyulalım. 
1  3  4  8   &   2  10  12
İlk olarak 1 ile 2 karşılaştırılır.1 < 2 olduğundan 1 sayısı ana diziye alınır. 
1  *  *  *  *  *  *					
3  4  8  &  2  10  12  .  Sıra ile devam ediyoruz.3 ile 2 karşılaştırılıyor.3 > 2 olduğu için 2 alınıyor.
1  2  *  *  *  *  *					

3  4  8  &  10  12  .   3  ile 10 karşılaştırılmasından 3 gelecektir.
1  2  3  *  *  *  *			

4  8  &  10  12   .  4 ile 10 var sırada.4<10 olma nedeniyle yeni gelecek sayı 4.
1  2  3  4  *  *  *			

8  &  10  12. 8 < 10 olduğundan yeni sayımız 8.
1  2  3  4  8  *  *		

10  12   . Son olarak 10 sayısı 12 sayısından küçük olduğu için,dizimiz niyahi sıralanmasını tamamlamış oluyor.
1	2	3	4	8	10
	
1	2	3	4	8	10	12
Algoritmanın karmaşıklığı ise O(n logn) dir.

Yukarıda belirtilen Merge Sort algoritmasının C dilindeki karşılığı aşağıdaki gibi verilebilir.
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.