퀵 셀렉트와 효율성

Sundae·2023년 9월 9일

Data Structures and Algorithms

자료구조와 알고리즘

목록 보기

7/19

퀵 셀렉트

만약 많은 시험 점수가 있을 때 30번째 백분위수나 중간 점수를 알고 싶을 때 어떤 방법을 사용하면 좋을까?

만약 배열을 정렬한 다음 인덱스에 접근하는 방법을 사용하면 해결할 수 있을 것이다. 하지만, 빠른 정렬 알고리즘을 사용한다고 하여도 평균적으로 O(NlogN)이 걸린다.

이때 퀵 셀렉트(Quickselect)라 알려진 알고리즘을 사용한다면 더 나은 성능으로 문제를 풀 수 있다.

퀵 셀렉트는 분할에 기반하며, 퀵 정렬과 매우 유사하므로 퀵 정렬을 알고있다면 무리없이 구현할 수 있다.

분할 메소드에서 반환되는 피벗은 항상 해당 배열에 올바른 곳에 위치되게 정렬되는 것을 알 수 있다.

만약 8개의 인덱스를 가진 배열에서 첫 번째 피벗(숫자 10이라고 가정)은 6번째 인덱스에 있다고 가정해보자. 그리고 우리는 숫자 5가 몇 번째로 작은지 알고 싶다.

첫 번째 피벗인 숫자 10보다 숫자 5가 더 작으니 피벗의 왼쪽에 있음을 알 수 있다.

이런식으로 분할을 진행하다가, 피벗의 값과 찾고자 하는 값이 같다면 그 인덱스는 몇 번째로 작은지를 의미한다.

구현 - 퀵 셀렉트

public class SortableArray {
	
	private int[] array; 
	
	public SortableArray( int[] array) {
		this.array = array;
	}
	public int[] getArray() {
		return array;
	}
	public int getSize() {
		return array.length;
	}
	
	public int partition(int leftPointer , int rightPointer) {
		
		// 항상 가장 오른쪽에 있는 값을 피벗으로 선택한다.
		// 나중에 사용할 수 있게 피벗의 인덱스를 저장한다.
		int pivotIndex = rightPointer;
		
		// 피벗 값을 저장해둔다.
		int pivot = array[pivotIndex];
		
		// 피벗 바로 왼쪽에서 오른쪽 포인터를 시작시킨다.
		rightPointer--;
		
		while(true) {
			
			// 피벗보다 크거나 같은 값을 가리킬 때까지
			// 왼쪽 포인터를 오른쪽으로 옮긴다.
			while( array[leftPointer] < pivot ) {
				leftPointer++;
			}
			
			// 피벗보다 작거나 같은 값을 가리킬 때까지
			// 오른쪽 포인터를 왼쪽으로 옮긴다.
			while ( array[rightPointer] > pivot ) {
				rightPointer--;
			}
			// 이제 왼쪽 포인터와 오른쪽 포인터 모두 이동을 멈췄다.
			// 왼쪽 포인터가 오른쪽 포인터에 도달했거나 넘어섰는지 확인한다.
			// 그렇다면 루프를 빠져 나가 이후 코드에서 피벗을 교환한다.
			if( leftPointer >= rightPointer ) {
				break;
			}	
			else {
				int temp = array[leftPointer];
				array[leftPointer] = array[rightPointer];
				array[rightPointer] = temp;
				
				leftPointer++;
			}
			
		}// w
		// 분할의 마지막 단곓 왼쪽 포인터의 값과 피벗을 교환한다.
		int temp = array[leftPointer];
		array[leftPointer] = array[pivotIndex];
		array[pivotIndex] = temp;
		
		return leftPointer;
	}
}


public class QuickSelect extends SortableArray{
	
	public QuickSelect( int[] array ) {
		super( array );
	}
	
	public int quickSelect( int lowestValue , int leftIndex , int rightIndex ){
		// 하위 배열에 셀이 하나면 찾고 있던 값을 찾은 것이다.
		if( rightIndex - leftIndex <= 0 ) 
			return getArray()[leftIndex];
		
		// 배열을 분할하고 피벗을 가져온다.
		int pivotIndex = partition(leftIndex, rightIndex);
		
		
		// 찾고 있는 값이 피벗 왼쪽에 있다면
		if( pivotIndex > lowestValue )
			// 피벗 왼쪽의 하위 배열에 대해
			// 재귀적으로 퀵 셀렉트를 수행한다.
			return quickSelect( lowestValue , leftIndex , pivotIndex - 1 );
		// 찾고있는 값이 피벗 오른쪽에 있으면
		else if( pivotIndex < lowestValue )
			// 피벗 오른쪽의 하위 배열에 대해
			// 재귀적으로 퀵 셀렉트를 수행한다.
			return quickSelect( lowestValue , pivotIndex + 1 , rightIndex);
		else {
			// 분할 후 피벗의 인덱스가 k번 째 작은 값의 인덱스와 같다면
			// 찾고 있던 값을 찾은 것이다.
			return getArray()[pivotIndex];
		}							
	}
}