퀵 소트/ quick sort / quick select : 백준 11004번 문제

백준 11004번 문제부터 얘기하자면 어렵지 않은 난이도인데 시간 초과로 계속 풀지못했던 문제

 

일단 학교에서 배운 quick sort와 quick select에 대해서 설명해보고자 한다.

 

1. quick sort (퀵 정렬)

1) 배열 나누기

임의의 값을 기준으로, 기준 값보다 작은 값들은 배열의 앞부분으로 이동하고, 기준 값보다 큰 값들은 배열의 뒷부분으로 이동하는 알고리즘.

 

기준 값: 입력 배열의 끝 값 (혹은 중간 값)

1구역: 기준 값보다 작거나 같은 값들이 위치할 곳

2구역: 기준 값보다 큰 값들이 위치할 곳

3구역: 아직 비교하지 않아서 위치가 정해지지 않은 값들

 

2) partition 구현

static void swap(int[] a, int i, int j) { 
  int temp = a[i];
  a[i] = a[j];
  a[j] = temp; 
} 
static int partition(int[] a, int start, int end) { 
  int value = a[end]; // 기준값 
  int i = start - 1; // i는 1구역의 끝지점
  for (int j = start; j <= end - 1; ++j) // j는 3구역의 시작 지점 
  if (a[j] < value) // a[j] 값이 1구역에 속하면 
    swap(a, ++i, j); // a[j] 값을 1구역의 끝에 추가한다. 1구역 크기 1증가. 
  swap(a, i + 1, end); // 기준값인 a[end] 원소와 2구역의 시작 원소를 교환한다. 
  return i + 1; // 기준값 위치 리턴 
}

3) 퀵 정렬 구현

static void quickSort(int[] a, int start, int end) {
  if (start >= end) 
    return; 
  int middle = partition(a, start, end); // 배열 나누기 
  quickSort(a, start, middle-1); // 1구역 정렬 
  quickSort(a, middle+1, end); // 2구역 정렬 
}

4) 퀵 정렬 수행 시간

partition 메서드의 수행시간은 O(n)이다.

평균

quickSort 메서드의 재귀 호출 횟수의 평균은 logn이다.

따라서 퀵정렬의 평균 수행시간은 O(nlogn)이다.

 

최선

partition 메서드가 배열을 정확히 1/2로 나눈다면, 재귀호출 횟수는 logn이고

따라서 퀵정렬의 최선일 때 수행시간은 O(nlogn)이다.

 

최악

partition 메서드가 배열을 0: n-1 크기로 나눈다면, 재귀호출 횟수는 n이다.

따라서 최악일 때, 퀵 정렬 수행시간은 O(n^2)이다.

 

 

=> 최악인 경우가 있기 때문에 기준값을 중간값으로 바꾸고 해보았지만 역시 시간 초과

 

2. quick select 

static void swap(int[] a, int i, int j) { 
  int temp = a[i]; 
  a[i] = a[j]; 
  a[j] = temp; 
} 

static int partition(int[] a, int left, int right) {
  int mid = (left + right) / 2;
  swap(a, mid, right);
  int pivot = a[right];

  int j = left - 1;
  for (int i = left; i < right; i++) {
    if (a[i] < pivot) {
		swap(a, i, ++j);
	}
  }
  j++;
  swap(a, right, j);
  return j;
}

// a 배열의 start~end 에서 nth 번째 작은 값을 리턴한다. 
static int select(int[] a, int start, int end, int nth) {
  if (start >= end) 
    return a[start]; // 찾을 배열의 크기가 1 이면 리턴 
  int middle = partition(a, start, end); // 배열 나누기 
  int middle_nth = middle - start + 1; // middle 위치의 값이 start~end 에서 middle_nth 번째 작은 값 
  if (nth == middle_nth) 
    return a[middle]; // 찾았으면 리턴 
  if (nth < middle_nth) 
    return select(a, start, middle-1, nth); // 앞 부분에서 찾는다.
  else 
    return select(a, middle+1, end, nth - middle_nth); // 뒷 부분에서 찾는다. 
}

근데 이렇게 해도 안된다. 대체 왜 (띠용)

partition 메소드에서 위 코드처럼 기준값을 중간값으로 바꿔줬는데도 시간초과가 뜬다.

 

3. 백준 11004번 문제

partition 메소드에 문제가 있는 것 같아서 아래의 메소드로 바꿨는데 시간초과가 뜨지 않는다.

사실 무슨 차이가 있는지 모르겠다. 암튼 아래 메소드로 바꾸니 됨...

(위 partition 메서드와 아래 partition 메소드의 차이점을 모르겠어요.. 아시는 분 댓글, 메일, 아무거나 부탁드립니다ㅜㅜ)

public static int partition(int[] array, int left, int right) {
	int mid = (left + right) / 2;
	swap(array, left, mid); // 중앙 값을 첫 번째 요소로 이동

	int pivot = array[left];
	int i = left, j = right;

	while (i < j) {
		while (pivot < array[j]) { // j는 오른쪽에서 왼쪽으로 피봇보다 작거나 같은 값을 찾는다.
			j--;
		}

		while (i < j && pivot >= array[i]) { // i는 왼쪽에서 오른쪽으로 피봇보다 큰 값을 찾는다.
			i++;
		}
		swap(array, i, j); // 찾은 i와 j를 교환
	}
	// 반복문을 벗어난 경우는 i와 j가 만난경우
	// 피봇과 교환
	array[left] = array[i];
	array[i] = pivot;
	return i;
}

 

 

전체 코드 확인 백준 11004번 문제 자바

jeon9825/TIP