[알고리즘] 선택 알고리즘 - 퀵 정렬과 함께하다

선택 알고리즘

n개의 원소가 불규칙하게 저장된 배열에서

i번재 큰(or 작은)원소를 찾는 알고리즘

정렬과 비슷하다

 

두 가지 알고리즘

• 평균적으로 선형시간이 소용되는 알고리즘
• 최악의 경우에 선형시간이 소요되는 알고리즘

 

평균적으로 선형시간이 소용되는 알고리즘

배열 A에서 i 번째 원소 찾기

1. 원소가 하나뿐인 경우, 하나 리턴
2. 원소가 다수의 경우, 파티션(퀵 정렬)을 통해 중간값이 몇 번째인지 확인
3. 중간값이 i와 같을 경우, A[파티션 통해 얻은 중간]값 리턴
4. 중간값이 i보다 클 경우, 오른쪽 그룹으로 범위를 좁혀 재귀
5. 중간값이 i작을 경우, 왼쪽 그룹으로 범위를 좁혀 재귀

예시 1

2번째 작은 원소 찾기

[31] [8] [48] [73] [11] [3] [20] [29] [65] [15]

 

마지막수 15를 기준으로 퀵정렬 해준다.

이 말은 15보다 작으면 왼쪽, 크면 오른쪽으로 정렬해주는거다.

이렇게 정렬되겠지

[8] [11] [3] [15] [31] [48] [20] [29] [65] [73]

 

문제를 다시 읽어보자 2번째 작은 원소니까

왼쪽 그룹 [8] [11] [3]에서 찾으면 되겠다.

다시 마지막 수 3을 기준으로 잡고 퀵정렬을 해준다.

그럼

[3] [8] [11]

 

뒤에 [8] [11]을 비교해서

8이 2번째 작은 수로 판명이 났다.

 

예시 2

7번째 작은 원소 찾기

[31] [8] [48] [73] [11] [3] [20] [29] [65] [15]

 

다시 한번 마지막수 15를 기준으로 퀵정렬 해준다.

[8] [11] [3] [15] [31] [48] [20] [29] [65] [73]

 

15를 포함해서 왼쪽 그룹 [8] [11] [3] [15]는,

순서가 필요없이 제일 작은 4개의 원소다.

그 말은 남은 [31] [48] [20] [29] [65] [73]에서 3번째 작은 원소를 찾는다!