Java Soru Çözümü-Pivot Seçme Algoritması

Merhaba arkadaşlar,bugün javada bir soru çözeceğiz.Sorumuz şöyle :

 

Soru:Quicshort(çabuk sıralama) algoritmasında kullanılmak için bir pivot seçimi algoritması yazın.Bu pivot seçim algoritması,rastgele olarak 0.50 olasılıkla dizinin ilk,0.25 olasılıkla dizinin son  ya da 0.25 olasılıkla dizinin ortasındaki elemanı pivot seçsin.

 

Şimdi soruyu analiz edersek bizden rastgele olan bir şeye biraz olasılık katmamız isteniyor.Bunun için random bir şeyler kullanıp bunu düzenleyeceğiz.Javada random sayı elde etme için Random sınıfını kullanabiliriz.Fakat ben farklı olsun diye Math sınıfının bize sağlamış olduğu Math.random() fonksiyonunu kullanacağım.

 

Math.random() ==> 0 ile 1 arasında rastgele double değerler verir.Her çalıştığında bu değerler değişir.

Örnek Çıktısı :0.3475036084001629

 

Şimdi şöyle bir şey yapacağız.double bir değişkende Math.random ‘un dönderdiği değeri tutacağız.Sonra bu değer sıfır küsürlü bir  değer çıkacak.Biz bu küsürlü değerin  sıfırdan sonra ilk iki hanesini integere çevirip( mesela 0.2444.. ise 24 ü alacağız) .Eğer çıkan sayi 0 ile 50 arasındaysa ilk eleman,50 ile  75 arasındaysa ortancı eleman, 75 ile 100 arasındaysa son elemanı seçeceğiz.Sıfırdan sonra ilk iki hanesini almak için string sınıfını kullanmamız lazım.Bunun için de random değerimizin yanına boş iki tırnak( +””) ekleyip Stringe çevirdik.Bunları koda çevirirsek şöyle bir şey çıkıyor:

 


public class Pivot_Sec {

public static void main(String[] args) {
int[] arrTmp = {1, 23, 5};
double oran = Math.random();
int sayi = Integer.parseInt((oran + "").substring(2, 4));

if (sayi >= 0 && sayi < 25) {
System.out.println("Pivot Eleman : " + arrTmp[arrTmp.length - 1]);
} else if (sayi >= 25 && sayi < 50) {
System.out.println("Pivot Eleman : " + arrTmp[(arrTmp.length - 1) / 2]);
} else if (sayi >= 50 && sayi < 100) {
System.out.println("Pivot Eleman : " + arrTmp[0]);
}
}

}

Çıktı:Pivot Eleman : 1

Unutmayalım ki bu çıktı her çalıştığında pivot elemanın değişme olasılığı var(0.25,0.25,0.50)

Ekstra olarak kodumuzun her 100 denemedeki çıkan sonuçların dağılımı incelemek için de şöyle bir kod kullandım.


public static void oranlariGor() {
int[] oranlar = {0, 0, 0};
for (int i = 0; i < 100; i++) {
double oran = Math.random();
int sayi = Integer.parseInt((oran + "").substring(2, 4));

if (sayi >= 0 && sayi < 25) {
oranlar[0]++;
} else if (sayi >= 25 && sayi < 50) {
oranlar[1]++;
} else if (sayi >= 50 && sayi < 100) {
oranlar[2]++;
}

}
System.out.println(Arrays.toString(oranlar));
}

 

Çıktı:[28, 24, 48]

Yani pivot seçme kodumuz 100 sefer çalıştığında 28 defa sonuncu ,24 defa ortancı ,48 defa de baştaki elamanı seçmiş.Bu da bizim istediğimiz olasıklara yakın değerler(0.25,0.25,0.50)

 

Şimdilik bu kadar.Sorunuz olursa yorum olarak sorabilirsiniz.Kolay gelsin..

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir