퀵 정렬 vs 삽입 정렬 차이

컴퓨터 정렬에서 실제로 가장 많이 쓰이는게 바로 내장 정렬 함수 퀵 정렬이다. 퀵 정렬은 매우 빠른 알고리즘으로 특히 평균 시나리오 에서 효율적이다.

 

분할

분할은 배열로부터 임의의 수를 가져와(이 수를 피벗이라 부름) 피벗보다 작은 모든 수는 왼쪽, 큰 수는 오른쪽에 둔다.

1

4

2

3

임의의 수 를 선택(2선택 피벗지정) 후 왼쪽 포인터(1)과 오른쪽 포인터(3)을 고른다.

1. 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.

2. 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다.

3. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다.

4. 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽으로 이동할때까지 반복한다.

5. 왼쪽 포인터가 가리키는 값과 피벗값을 교환한다.

 

퀵 정렬

1. 분할된 배열

2. 피벗의 왼쪽과 오른쪽에 있는 하위배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다. 즉, 각 하위 배열을 분할하고 각 하위배열에 있는 피벗의 왼쪽과 오른쪽에서 더 작아진 하위배열을 얻는다. 이어서 이러한 하위 배열을 다시 분할하는 과정을 반복한다.

3. 하위 배열이 원소를 0개 또는 1개 포함하면 기저 조건이므로 아무것도 하지 않는다.

 

퀵 정렬의 단계는 비교와 교환으로 나뉜다

비교는 최소 N번 비교하고, 교환은 얼마나 정렬되어 있나에 달렷는데 최소 한번 교환이며 모두 교환할지라도 왼쪽 반, 오른쪽 반 값을 교환하므로 최악일땐 N/2 교환이 일어난다.

 

무작위로 정렬된 데이터에 (N/2)/2 (왼, 오로 나누어 분할하니) 즉, N/4 교환이 일어난다.

비교 N + 분할 N/4 = 1.25단계고 빅 오표현에선 상수는 무시하니 O(N)단계라 말할 수 있다.

 

원소가 8개인 배열에서 1.25N단계를 적용하면(분할시 배열이 0 또는 1일땐 기저조건이니 수식엔 넣지않음)

8개 원소 / 1.25 단계 = 10단계

3개 원소 / 1.25 단계 = 3.75단계

4개 원소 / 1.25 단계 = 5단계

2개 원소 / 1.25 단계 = 2.5단계

 

합 21단계 즉, 원소 N일때 약 N*log N 단계임을 알 수 있다.

N	log N	N * log N
4	2	8
8	3	24
16	4	64

 

여기서 최악의 시나리오일경우, 원소가 8개면 8+7+6+5+4+3+2 = 35의 분할과 35번의 비교를 한다. 즉 퀵 정렬은 O(N^2)라고도 할 수 있다.

 

삽입정렬

yju7257.tistory.com/44

 

퀵 정렬 vs 삽입 정렬 차이

	최선의 시나리오	평균 시나리오	최악의 시나리오
삽입 정렬	O(N)	O(N^2)	O(N^2)
퀵 정렬	O(N log N)	O(N log N)	O(N^2)

최악의 시나리오 삽입=퀵

최선의 시나리오 삽입>퀵

평균의 시나리오 삽입<퀵

 

현실적으론 평균의 시나리오가 훨씬 많이 일어나기에 퀵 정렬이 더 우수하다 말할 수 있다.

 

퀵 셀렉트

퀵 정렬은 배열을 반으로 나눌 때마다 원래 배열의 모든 셀을 다시 분할해야하므로 O(N log N)이 걸린다.

그러나 퀵 셀렉트는 배열을 반으로 나눌 때마다 필요한 반쪽 즉, 찾고 있는 값이 있을 반쪽만 분할한다.

퀵 셀렉트의 평균 시나리오에서의 단계는 O(N)이다.

 

만약 원소 8개인 배열에선 8 + (8/2) + (8/2/2) = 14 단계가 걸린다.

즉, N + (N/2) + (N/4) ... = 2N 즉,(상수무시) O(N)단계이다.