#003_자료구조와 알고리즘_누구보다 빠르게 Quick 정렬

안녕하세요 삽잡이 입니다.

이번시간에는 '누구보다 빠르게 난 남들과는 다르게' ...

이름 그대로 빠른, Quick Sort (퀵 정렬)에 대해서 알아보려고 합니다.

얼마나 빠르길래.... 하하...

퀵 정렬을 이해하기 위해서는 우선, 알고리즘의 설계 방법들에 대해서 알아볼 필요가 있습니다.

알고리즘을 설계하는 방법은 여러가지가 있습니다.

예를 들어 볼까요? 이전 시간에 본 삽입 정렬을 보도록 해봅시다.

"i 장의 카드를 삽잡이는 손에 쥐고 있습니다.

이때 한 장의 순서가 눈에 거슬리는 삽잡이는 그 카드 한 장을 뺀 나머지 i-1장들 사이에 

비교를 통해 적절한 위치에 삽입을 하게 되죠."

이와 같이 '점진적'인 방법을 삽입 정렬에서는 사용하고 있습니다...

설계하는 방법이 한가지는 아니겠죠 하하...

그러다면, 이번에는 점진적인 방법과 다른... 분할 정복 접근법에 대해서 알아보겠습니다.

알고리즘에는 재귀적 구조를 가진 알고리즘들이 참으로 많다고 합니다.

'재귀'란 "원래의 자리로 되돌아가거나 되돌아옴." 이라는 뜻을 국어사전에서 알려주고 있습니다.

그렇습니다. 해당 문제를 풀기 위해 자기 자신을 계속해서 참조하는 것이죠...

끝나지 않는 돌림노래와 같이 말입니다...

이렇게 재귀적 구조를 가진 알고리즘들은 전형적으로, '분할 정복' 접근법을 따릅니다.

문제를 해결하기 위해 잘게 쪼갠다... 

쪼갠 것을 풀고 결과를 결합하여 기존의 문제에 대한 답을 만들어낸다...

음... 간략하게 분할 정복 접근 방법에대해서 설명을 해본 것입니다. 정말 간략하죠...

그런데 분할 정복 접근 방법에 대해서 왜 언급을 했느냐...

눈치를 채신 분들이 다반사겠죠... 바로 퀵정렬이 분할 정복에 기반을 둔 알고리즘이기 때문입니다.

퀵정렬은 우선 정렬을 하는데 기준점이 될 pivot 이 필요합니다.

아래에서 소개할 퀵정렬의 예시에서 pivot의 값은 p로 지정하겠습니다.

퀵정렬의 수행 방법은 다음과 같습니다. Sap이라는 배열의 범위를 (b -> e)라고 가정해보도록 하겠습니다.

1. 배열을 2 개의 부분 배열로 분할 합니다. Sap(e ... p-1), Sap(p ... e)

2. 중심인 pivot을 기준으로 pivot의 값보다 작은 값은 전자에, 

큰 값은 후자의 분할된 배열에 배치하도록 합니다. 

3. 나뉘어진 2 개의 배열에 임의의 pivot을 지정하고 재귀호출하여 두 부분에 대한 정렬을 진행합니다.

4. 더이상 나뉘어지지 않는다면 끝... 왜냐? 이미 정렬되어있는 상태에서 분할이 되는 것이기 때문에 

따로 결합하는 작업이 필요하지는 않기 때문입니다.

자... 이해가 가시는지요...

그렇다면, 그림으로 이해한 순서를 구현해 보도록 하겠습니다.

우선, 기준이 될 pivot 값을 선택합니다.

기준이 된 pivot을 맨 처음으로 이동시킵니다.

자... 이제 시작을 해볼까요.... left 친구와 right 친구를 등장시키도록 하겠습니다.

짜잔!

파란색을 left, 빨간색을 right라고 하겠습니다.

pivot을 기준으로 왼쪽은 pivot보다 작은 값, 오른쪽은 큰 값이 정렬되도록... 작업을 시작해야합니다..

여기서 작업을 위해 지켜야 할 약속! 

우리는 left와 right 화살표를 한칸씩 이동 시킬 것입니다.

아래와 같이 진행할 것입니다.

1. pivot 값 보다 큰 값이라면 left 는 이동 종료 후 right 이동 시작.

2. pivot 값 보다 작은 값이라면 right 는 이동 종료 후 left와 right 값 비교를 통해 교환.

자... left를 이동시키다가 left를 중지 시켰습니다. pivot 값 보다 크니깐요...

그렇다면 약속대로 right 값을 이동시켜봅시다.

흠... 그런데 우선 시작하자마자 right 값이 pivot 값보다 작습니다.

그러면 어떻게 한다? 이제 left값과 right 값을 비교 후 서로 교환을 할 것입니다.

자.. 값을 교환했습니다.

이제 다시 left 값을 움직여보도록 하겠습니다.

흠... 멈췄습니다. 왜 멈춘지 알겠지요? pivot 값보다 크니깐요... 

이제 그럼 다시 right 값을 움직여보도록 하죠...

right 값이 pivot 값보다 작습니다. 따라서 left와 right 의 값을 비교하겠습니다.

교환을 해야겠죠?

교환을 했으니, left 값을 다시 이동시키도록 하겠습니다.

어랏, 화살표가 겹쳤습니다. 이때에 약속이 하나 또 추가됩니다.

3. left와 right 가 같은 위치에 있을 때, pivot값이 해당 위치 기준으로 

작으면 오른쪽 값과 변경 크면 왼쪽 값과 변경.

해당 예시에서 pivot 값을 가리키는 값 

즉, 9보다 작지요? 그럼 왼쪽 값인 1과 교환을 해야겠습니다.

자... 이제 pivot을 기준으로 좌, 우로 나누어 똑같이 진행하면 됩니다.

이렇게 나뉘어 똑같이 진행하게 되는 것이지요...

좌, 우 새로운 정렬을 진행합니다.

그렇다면 결국은 pivot을 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 정렬이 되기때문에

아래와 같이 정렬이 완료됩니다.

자... 지금까지 그림으로 quick 정렬에 대해 설명을 해봤습니다.

어찌... 이해가 가셨는지요? 

음... 코드는 그림을 이해해보셨다면 스스로 구현해보는 것이 어떨 까요?

저도 quick 정렬에 대한 코드를 다시한번 짜보려고 합니다.

저는 quick 정렬에 대해 이해하는데 좀 애를 먹었거든요...

아무튼... 제 설명이 도움이 되었다면 좋겠군요...

이상 삽잡이였습니다!