[알고리즘] 1-4. 퀵 정렬 [재귀 함수 이용]

1. 퀵정렬

: 기준값[pivot]을  선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬

 

-> 기준값을 선택하는 함수가 시간 복잡도에 영향을 미치며, 평균적으로 시간복잡도는 O(nlogn)이다.

-> 퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다.

[컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나]

 

(1) 구현 과정

-> 기준값 pivot을 중심으로 데이터를 2개의 집합으로 나누는 것을 반복해 정렬 

1. 데이터를 분할하는 pivot 설정  [방법에 따라 다르지만 여기서는 가장 오른쪽 끝 값으로 설정]
2. 기준값을 기준으로 2개의 집합으로 분리하는 과정
   1. start 데이터< pivot 데이터 -> start를 오른쪽으로 1칸 이동 [우측 shift 연산]
   2. end 데이터> pivot 데이터 -> end를 왼쪽으로 1칸 이동 [좌측 shift 연산]
   3. start 데이터>pivot 데이터 && end 데이터<pivot 데이터 -> start 데이터와 end 데이터 swap 연산 후,
      start는 오른쪽으로 1칸 이동 [우측 shift 연산], end는 왼쪽으로 1칸 이동 [좌측 shift 연산]
   4. start와 end가 만날때까지 해당 과정 반복
   5. start == end인 경우 만난 지점의 데이터와 pivot의 데이터를 비교
      1. index 데이터 < pivot 데이터 -> index +1 지점에 데이터 삽입
         
         
      2. index 데이터 > pviot 데이터 -> index -1 지점에 데이터 삽입
   6. 분리 집합에서 각각 다시 pivot 선정 [기준값 변경]
   7. 분리집합이 1개 이하가 될 때까지 해당 과정 반복

---

문제 19. K번째 수 구하기

수 N개(A1 ~ AN)가 주어진다. A를 오름차순 정렬했을 때 앞에서부터 K번째에 있는 수를 구하는 프로그램을 작성하시오.

 

입력
첫 번째 줄에 N(1 <= N <= 5,000,000)과 K(1 <= K <= N), 두 번째 줄에 A1 ~ AN이 주어진다(-109 <= Ai <= 109)

 

출력
A를 정렬했을 때 앞에서부터 K번째에 있는 수를 출력한다.

예제 입력 1

5 2 //데이터 개수，K번째 수 2
4 12 3 5

 

예제 출력 1

2

---

1단계. 문제 분석하기

-> N의 범위를 보면 5,000,000이므로 O(nlogn)의 시간 복잡도인 퀵 정렬 이용

-> 퀵 정렬을 사용해 오름차순 정렬 후, K번째 수 출력

-> 먼저 기준값인 pivot을 구하는 방법 찾기

 

# pivot을 구하는 방법

pivot == K : K번째를 찾았으므로 알고리즘 종료
pivot >  K : K가 pivot보다 작기 때문에 왼쪽 집합만 정렬 수행      [S ~ pivot -1]
pivot <  K : K가 pivot보다 크기 때문에 오른쪽 집합만 정렬 수행	[pivot - 1 ~ E]

-> 데이터가 정렬되어있는 경우에 pivot의 위치가 앞에 존재할 경우 불필요한 연산이 많아진다

-> 따라서, 예시의 경우 배열의 중간 위치를 pivot으로 설정

 

2단계. 손으로 풀어 보기

1. 중간 인덱스를 pivot으로 설정 후, 맨 앞에 있는 값과 swap연산 수행
   -> pivot을 맨 앞으로 옮겨서 i, j 이동을 편하게 하기 위해서
   -> i와 j를 pivot을 제외한 그룹에서 왼쪽과 오른쪽 끝으로 설정
   [즉, i는 1번 인덱스, j는 마지막 인덱스에 위치]
2. 먼저 j를 이동시키기 위해, j보다 pivot보다 크면 j-- 연산을 반복
   -> 반복 결과 j는 1에 위치하게 된다
   -> j를 이동 후, i<pivot && i<j일 경우, i++연산 반복
3. pivot을 i와 j가 만나는 위치와 swap 연산 수행
4. K가 2이므로 정렬하지 않고 A[2] 출력

3단계. 슈도 코드 작성하기

N（숫자의 개수） K（K번째 수）
A（숫자 데이터 저장 배열）
for（N만큼 반복하기） {
	A 배열 저장하기
}
퀵 소트 실행하기
K번째 데이터 출력하기

[별도의 함수 구현 부분]
퀵 소트 함수（시작，종료，K）
{
    피벗 구하기 함수（시작, 종료）
    if（피벗 == K） 종료
    else if（K < 피벗） 퀵 소트 수행하기（시작, 피벗 - 1, K）
    else 퀵 소트 수행하기（피벗 + 1, 종료，K）
}

피벗 구하기 함수（시작, 종료）
{
        중앙값을 피벗으로 설정하기
        i（시작점）, j（종료점）
        while（i < j）
        {
        피벗보다 큰 수가 나올 때까지 i++
        피벗보다 작은 수가 나올 때까지 j찾은
        i와 j 데이터를 swap
        }
	피벗 데이터를 나눠진 두 그룹의 경계 index에 저장하기
}

 

package sorting.ch04;

import java.util.Scanner;

public class sorting_q19_sol {
	public static void main(String[] args) {
		sorting_q19_sol T = new sorting_q19_sol();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int k = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();

		sort(arr, 0, n - 1, k - 1);
		System.out.println(arr[k - 1]);
	}

	public static void sort(int[] arr, int start, int end, int k) {
		if (start < end) {
			int pivot = part(arr, start, end);
			if (pivot == k)
				return;
			else if (k < pivot)
				sort(arr, start, pivot - 1, k);
			else
				sort(arr, pivot + 1, end, k);
		}
	}

	public static int part(int[] arr, int start, int end) {
		int mid = (start + end) / 2;
		swap(arr, start, mid);
		int pivot = arr[start];
		int i = start, j = end;
		while (i < j) {
			while (pivot < arr[j]) {
				j--;
			}
			while (i < j && pivot >= arr[i]) {
				i++;
			}
			swap(arr, i, j);
		}
		arr[start] = arr[i];
		arr[i] = pivot;
		return i;
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}