www.fatihkabakci.com

Personal Website and Computer Science TUR EN

HIZLI SIRALAMA(QUICK SORT)

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

Yazan:Fatih KABAKCI

Sıralama Algoritmalarından biri olan quick sort algoritması aynı veri türlerine sahip elemanları böl ve yönet(divide and conquere) anlayışına göre sıralamakla yükümlü bir algoritmadır.Özyineli(recursive) bir algoritma olmasından dolayı kendi kendini tekrar ederek sectiği elemana göre sıralama işlevini yürütmektedir.

Bir örnek ile algoritmamızı daha iyi anlamaya çalışalım.Örneğimizde her zaman ki gibi konunun net anlaşılması açısından tam sayıları kullanacağız.
Örneğin 4 2 1 5 7 6 0 3 sayılarından oluşan bir dizimiz olsun.Algoritma her uygulanışında bir pivot sayı seçer.Bu sayı baştaki,ortadaki,sondaki veya herhangi bir sıradaki sayı olabilir yani pivot seçimi fark etmeyen bir durumdur.Biz bu örneğimizde kolay görülebilme adına baştaki sayıyı seçerek işleme başlayacağız.

Dizinin pivot sayısı=4

Şimdi bu pivot sayıdan küçükler ve büyükler şeklinde sıralamaya başlayalım.4 ten sonra gelenler ile bakıyoruz..ilk olarak 2 sayısı 4 ten küçük olduğu için 4 ün soluna.. 

 		4
	    2	

1<4 olduğu için yine 4 ün soluna..
                 4
        2    1


5>4 olduğu için 4 ün sağına..
		4
2	1		5


7>4 olduğu için 4 ün sağına..
		4
2	1		5	7


6>4 olduğu için 4 ün sağına..
		4
2	1		5	7	6


0<4 olduğu için 4 ün soluna..
		           4
2	1	0		5	7	6


Son olarak 3<4 olduğu için soluna..
				4
2	1	0	3		5	7	6


				4
2	1	0	3		5	7	6
Dizimiz ilk gruplandırmada 4 ten küçükler ve büyükler olarak sıralanmış oldu.Fakat bu algoritma recursive bir algoritmadır ve aynı işlemleri dizi gruplanamayacak konuma gelene kadar devam edecektir.Şuan bu diziye 2 farklı bölüme sahip bir dizi şeklinde bakabiliriz,yani 2 gruplu dizi(4 ten küçükler – 4 ten büyükler).
Şimdi ilk grubumuz olan 4 ten küçükleri yine baştaki sayıyı pivot sayı olarak seçelim ve sıralamaya bu grup üzerinden devam edelim.

Sol dizinin Pivot sayısı=2 Şimdi sıralama işlemine başlayalım,bakacağımız ilk sayı 1 olacaktır. 
1<2 olduğu için 2 nin soluna..
	2
1	


0<2 olduğu için 2 nin soluna..
		2
1	0	


3>2 olduğu için 2 nin sağına..
		2
1	0		3
Başka eleman kalmadığı için sol dizimizin yeni hali yukarıdaki gibi olacaktır.Fakat işlem bitmedi! Dizimizin bu bölümünün sol tarafı hala sıralı değil.O halde son kez pivot işlemi başlatılacak.(sağ tarafta 1 eleman kaldı (3 sayısı) onu gruplandırmaya gerek yok)

Pivot sayısı=1 
0<1 olduğu için 1 in soluna..
	1
0
Şuan dizimizin sol tarafı(yani 4 ten küçükler bölümü) sıralanmış oldu.Fakat buraya daha sonra döneceğiz çünkü dizimizin sağ tarafı halen sıralı değil.O yüzden buraya bir ** işareti koyuyorum ve daha sonra toplamaya başlarken hatırlayalım diye. 
Şimdi 4 ten büyükler grubunu sıralamaya başlayalım.

5	7	6
Pivot sayı=5

7>5 olduğu için 5 in sağına..
	5
		7

6>5 olduğu için 5 in sağına..
	5
		7	6
Şuanda 5 ten büyükleri belirledik.Şimdi pivot sayımızı 7 olarak seçerek bu kısmın sağ tarafını da sıralamış olalım. 
Pivot sayısı=7

7>6 olduğu için 7 nin soluna..

	7
6
Evet artık gruplandırma işlemini bitirmiş oluyoruz yani dizimiz sıralanmıştır!Artık gruptaki sayılarımızı teker teker toplamaya başlayalım. 
5	6	7
Hatırlarsanız ** işaretini koyarak bu kısma döneceğiz hatırlatmasını yapmıştık.Şimdi buraya dönerek dizinin kalan sol tarafını da toplamaya başlayalım. Teker teker
 	0	1	2	3
sayılarını sırası ile alıyoruz.Tekrar belirtmekte yarar var ki bu algoritma recursive bir algoritma olduğu için çözümü kendi kendini tekrar edebilmesinden dolayı doğasına çok yatkındır.Bilindiği gibi recursive algoritmalar gidebileceği en alt noktaya giderek oradan return ettiği sonuçları toplamaya başlar.Bizde quick sort algoritmasında sayılarımızı sıralarken recursive yaklaşıma dayanarak işlemlerimizi yürütüyoruz. Dizimizin sol tarafı + 4 + dizimizin sağ tarafı şeklinde yapılan son toplama ile dizimiz nihai sonucuna ulaşmış olur. 
0	1	2	3	4	5	7	6
Algoritmamızın karmaşıklığını incelemiş olursak,hatırlanacağı gibi her adımda N sayıya bakıyoruz ve sürekli ikili şekilde gruplamaya çalışıyoruz.Bundan dolayı, O(nlogn) algoritmamızın performansını belirlemiş olur.Fakat tesadüfen seçilen her pivot sayı dizinin en büyük veya en küçük elemanı olur ise,o zamanda performans O(n’2) olacaktır.Çünkü her adımda pivot sayıdan küçükler veya büyükler şeklinde tek bir grup olacaktır.Her adımda N-1 sayıya bakılacağından dolayı toplam N sayıya bakılmış olur. 
				10
			9
		8
	7
6
Şeklinde gittiğini düşünür isek,her geçişte N tane sayı ele aldığımızdan dolayı,algoritma en kötü durumda O(n 2) ifadesini alacaktır.

Yukarıda analizi yapılan algoritmanın C dilindeki karşılığı aşağıdaki gibi verilebilir.
MemberCommentDate:
guest 
ellerine sağlık gardaım ankaradan selamlar mslm gürses den ustam şarkısını rica ediyorum

yaralı b0yacı
3/30/2019 7:49:00 AM
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.