Quick Select

Kategori: Popular Algorithms , 17 Kasım 2019 , JanFranco


Problem:

Bir dizideki en küçük k. elemanı bulmak.

Yaklaşım:

Bu problemi brute-force ile çözmek isterksek diziyi sıralamamız ve baştan k kadar ilerleyip elemanı return etmemiz yeterli olacaktır. Fakat en küçük k. eleman için bütün diziyi sıralamamız gerekmiyor. Quick Select ve Lomuto Partition algoritmalarını kullanabiliriz:

ALGORITHM LomutoPartition(A[l..r])

p <- A[l]
s <- l
for i <- l + 1 to r do
    if A[i] < p
    s <- s + 1
    swap(A[s], A[i])
swap(A[l], A[s])
return s

ALGORITHM QuickSelect(A[l..r], k)

s <- LomutoPartition(A[l..r])
if s = k - 1 
    return A[s]
else if s > l + k - 1
    QuickSelect(A[l..s-1], k)
else
    QuickSelect(A[s+1..r], k - 1 - s)

Bu iki algoritmayı da Algoritma Tasarım ve Analiz bölümünde detaylıca açıkladım, oradan inceleyebilirsiniz. 

Çözüm:




public class QuickSelect {
		
	private static int[] swap(int[] arr, int i1, int i2) {
		int temp = arr[i1];
		arr[i1] = arr[i2];
		arr[i2] = temp;
		return arr;
	}
	
	private static int LomutoPartition(int[] arr, int l, int r) {
		int p = arr[l], s = l;
		for(int i=l+1; i<=r; i++) {
			if(arr[i] < p) {
				s++;
				arr = swap(arr, s, i);
			}
		}
		arr = swap(arr, l, s);
		return s;
	}	
	
	private static int quickSelect(int[] arr, int l, int r, int k) {
		int s = LomutoPartition(arr, l, r);
		if(s == k) {
			return arr[s];
		}
		else if(s > l + k - 1) {
			return quickSelect(arr, l, s-1, k);
		}
		else {
			return quickSelect(arr, s+1, r, k);
		}
	}

	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7};
		System.out.println(quickSelect(arr, 0, arr.length - 1, arr.length/2));
	}

}


Sonraki Yazı: Interpolation Search
Yorumlar

Henüz bir yorum bulunmuyor.