[알고리즘] 퀵 정렬(quick sort) 쉽게 이해하기!

퀵정렬 (quick sort)

 

퀵정렬을 설명하는 글을 보면,

 

피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로,

 

피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮기는 것이라고 적혀있는데,

 

이 때 피벗(pivot)은 단순히 '먼저 선택된 성분' 정도로만 생각해도 될 것 같다.

 

다시말해, 먼저 특정 원소가 피벗으로 선정되고 그 원소에 따라 배열이 진행되는 것이 퀵정렬이다.

 

 

'팀 나누기' 라고 생각하면 쉬울 것 같다. 

 

배열 [5, 7, 3, 6, 2, 1] 이 있을 경우를 예로 들어보겠다.

 

맨 왼쪽의 원소 5를 피벗으로 정한 뒤,

 

피벗보다 작거나 같은 원소를 A팀,

 

피벗보다 큰 원소를 B팀으로 나누어보겠다.

 

 

이 때, 원소들은 차례로 줄을 서 있고, 

 

앞에 서있는 원소부터 자리를 찾아가야 한다.

 

 

그렇다면 5 다음 원소인 7은 5보다 크므로 B팀으로 가고,

 

 

 

7 뒤에 서있던 3은 5이하이므로 A팀으로 간다.

 

 

그렇게 맨 뒤에 서 있던 1까지 자리를 찾아가면 첫 번째 과정은 거의 끝이다.

 

( 중요: 피벗을 기준으로 값을 나눌 때, 값의 크기에 상관없이 차례로 적어주어야 한다.

            예를 들어, 5를 초과한 값을 적을 때, 마음대로 정렬하여 6 ,7 이라 적으면 안 된다.)

 

배열로 나타내면 피벗, A팀, B팀 순으로, [5, 3, 2, 1, 7, 6] 이 된다. 

 

이렇게 되면 A팀과 B팀의 경계가 불분명하므로 컴퓨터는 다시 이를

 

A팀, 피벗, B팀으로 재배열한다. (코딩할 때 중요하다!!) 

 

 

머릿속으로 알고리즘을 익히는 중이라면 바로 이렇게 생각해도 된다.

 

 

그럼 현재 배열의 상태는 [3, 2, 1, 5,  7, 6] 이고,

 

5를 기준으로 큰 값과 작은 값은 잘 나뉘어진 상태이다.

 

따라서 피벗의 자리가 고정된 것이다.

 

그럼 이제 피벗을 다른 값으로 설정해주어야 하는데,

 

이제 A, B팀 각각에 피벗이 하나씩 생긴다고 생각하면 된다.

 

아까 정한 방식처럼, 각 팀에서 맨 왼쪽에 있는 값을 피벗으로 정해주면,

 

 A팀의 배열은 [2, 1, 3] 이렇게 될 것이고

 

B팀의 배열은 [6, 7] 이 된다.

 

피벗이었던 3과 7의 값도 고정되고, 

 

다시 피벗을 정해주도록 하자.

 

 

 

6은 좌 우의 값이 모두 피벗이었던 값으로, 

 

이미 자리가 확정된 값들이므로 더이상 비교할 필요가 없어

 

자리가 확정 되었다.

 

하지만 2는 아직 비교 대상이 남았으니, 피벗으로 설정해주고 비교를 하면,

 

배열은 [1, 2, 3, 5, 6, 7] 로 알맞게 정렬된다는 것을 알 수 있다.