Skip to content

Quicksort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//Quick sort alghoritması ortalama zamanda n(log n)
//de çalışan büyük arrayler için çok iyi sonuçlar
//veren bir sıralama algoritmasıdır.
public static void quicksort(int array[],int left,int right){
   	//Başta verilen left ve right değerlerini geçici olarak 
   	//tutabilmek için l ve r'ye atıyoruz. Aynı zamanda array'
   	//in içinde yer değiştirmeler içinde temp adlı değişkeni
   	//kullanıyoruz.
   	int l = left,r=right,temp;
   	//pivot olarak baştaki elemanı seçiyoruz
   	int pivot = array[left];
   	//partition algorithm
   	//Bu bölümde arrayimizi 2 ye ayırıyoruz
   	//Birinci bölümde pivottan küçük olanları,
   	//ikinci bölümde ise pivottan büyük elemanları
   	//tutuyoruz. 
   	while(r>=l){
   		//l değişkenini pivottan daha büyük bir eleman
   		//karşımıza çıkana kadar artırıyoruz.
   		while(pivot>array[l])
   			l++;
   		//r değişkenini pivottan daha küçük bir eleman
   		//karşımıza çıkana kadar azaltıyoruz.
   		while(pivot<array[r])
   			r--;
   		//Eğer sol tarafta pivottan daha büyük ve sağ
   		//tarafta pivottan daha küçük bir elemanla
   		//karşılaşırsak bunları temp değişkeni 
   		//yardımıyla yer değiştiriyoruz.
   		if(r>=l){
   			temp = array[r];
   			array[r] = array[l];
   			array[l] = temp;
   			//arrayin bir sonraki elamanına 
   			//ulaşabilmek için sol tarafta l'yi 
   			//artırırken  r'yi de azaltıyoruz.
   			l++;r--;
   		}
   		//En dıştaki loop sayesinde birinci grupta hep
   		//pivottan küçükleri ikinci grupta da pivottan
   		//hep büyükleri toplamış oluyoruz.
   	}
   	//Eğer l right kadar büyük olmuşsa veya right'tan 
   	//küçükse bu büyük grupta sıralanabilecek sayılar
   	//olabileceğini gösterir. Dolayısıyla 2. grup için
   	//quick sort tekrar çağrılır. 1. grup için se l değiş
   	//keninin solunda kalan kısım kullanılır. Onun için de
   	//aynı şekilde quick sort çağrılır.
   	if(right>=l){
   		quicksort(array,l,right);
   		quicksort(array,left,l-1);
   	}
}

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *