[알고리즘-공부] 3. 분할 정복 알고리즘(2) - 퀵정렬

3.2 퀵정렬(Quick Sort)

퀵정렬은 분할 정복 알고리즘으로 분류되나, 사실 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘 이다. 퀵정렬 알고리즘은 문제를 2개의 부분문제로 분할하는데, 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘이다.

 

퀵정렬은 다음과 같은 과정으로 분할 정복을 이용해 정렬을 수행합니다.

(1) 데이터 집합 내에서 임의의 기준요소(pivot)를 선택하고, 기준요소보다 작은 요소들은 순서에 관계없이 무조건 기준요소의 왼편에, 큰 값은 오른편에 위치시킨다.

(2) 기준 요소 왼편에는 기준 요소보다 작은 요소들이 모여 있고 오른편에는 큰 요소들이 모여 있겠쥬??이렇게 나눈 집합들을 다시 (1)번에서와 같이 임의의 기준요소를 선택하고 같은 방법으로 데이터 집합을 분할 한다.

(3) (1),(2)번의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터를 얻게 된다.

자, 글로보면 이해가 안될것 같으니 그림으로 설명할게요

 

밑에 그림과 같이 정렬되지 않은 데이터 집합이 있다고 해 봅시다. 먼저 기준 값을 선택 해야겠죠?? 기준요소를 선택하는 방법에는 여러가지가 있지만, 여기 예시에서는 데이터 집합의 첫 번째 요소를 사용하겠습니다.  (기준요소 선택방법은 뒤에서 설명할게요!)

기준요소 조건이 데이터 집합의 첫번째 요소라고 하니 5가 기준이 되겠죠?

요소 5를 기준으로, 5보다 작은 요소들은 왼쪽에 큰 요소들은 오른쪽에 '닥치는 대로' 모읍니다. 이 결과로 왼쪽과 오른쪽에 정렬되지는 않았지만, 범위가 한정되어 있는 데이터 집합이 생깁니다. 이렇게 생긴 왼쪽과 오른쪽 의 데이터 집합에 대해 분할을 수행합니다. 왼쪽이든 오른쪽이든 어느쪽을 먼저해도 상관없습니다. 전 왼쪽부터..ㅎㅎ

분리를 위해서는 먼저 기준 요소를 선택해야 한다는 사실을 기억하고 계시죠..?? 가장 처음에 있는 요소인 1을 기준으로 지정합니다.

그런데 1,4,3,2 중에 1요소보다 작은 요소는 없고 1보다 큰 요소는 모두 1의 오른쪽에 와 있으니 이미 분할되어 있는 상태라 할 수 있습니다. 이번엔 이제 새로 생긴 오른쪽의 데이터 집합 4,3,2에 대해 분할 수행합니다.

4,3,2 중 첫 번째 요소인 4를 기준요소로 선택하여 분할을 수행합니다.

4보다 큰 요소는 하나도 없고 모두 작은 요소들 뿐이니 4를 2뒤에 위치시킵니다. 분할 결과로 왼쪽에만 데이터 집합이 생겼습니다. 이제 3,2에 대해 분할을 해봅시다.

3,2 중 첫번째 요소에 위치한 3을 선택하여 분할을 수행합니다.

 2는 3보다 작으니 3의 왼쪽에 와야겠죠? 이렇게 해서 최초의 분할에서 생긴 왼쪽 데이터 집합이 모두 정렬되었습니다! 남아있는 오른쪽 데이터 집합의 분할을 계속 해볼까요??

6을 기준요소로 선택했는데, 6보다 작은 요소가 없네요 이대로 6의 오른쪽에 있는 데이터 집합에 대해 분할 수행을 합니다.

8,7,9 중 첫 번째 요소인 8을 기준으로 지정하고 분할을 수행합니다.

더 이상 분할할 수 없는 단계가 왔습니다. 이제는 완전히 정렬된 데이터 집합을 얻었어요!!!!!!!!!!

<기준요소를 선택하는 방법>

무작위로 뽑는 경우도 있지만 대부분 처음 데이터 집합의 처음 세 개 요소 중에서 중간값을 기준요소로 지정한다고 합니다. 그래야 최악의 경우를 피할 수 있다고 합니다!

 

여기서 잠깐!! (빠밤)

내가 알던 퀵정렬이 아냐!!라고 생각하시는 분들이 계실텐데요. (계실런지.. 그냥 내가 정리하는건데 뭐)  맞습니다. 위에 방식이 틀렸다는 얘기가 아니라 데이터 집합이 배열인지 리스트인지에 따라 퀵정렬하는 방법이 조금 달라질 뿐입니다. 위에 예제는 데이터 집합의 자료구조가 리스트인경우에 해당이 되는데요 리스트는 배열처럼 데이터 집합을 보관하는 기능을 가지면서 배열과 달리 유연하게 크기를 바꿀 수 있고, 삽입 삭제가 자유로운 자료구조 입니다. 따라서 위에 예제의 데이터 집합이 리스트인 경우에는 포인터로 메모리 주소만 바꾸면 데이터 집합내에서 노드 이동이 가능하기 떄문에 상관없습니다만, 저희 학교 전공책에서 쓰는 것은 데이터 집합 자료구조가 '배열' 이기때문에 위에 예제처럼 할 수가 없습니다. 조금 바꿔서 생각해보죠!

과정은 이렇습니다.

정찰병 2명을 투입해서 한명은 왼쪽부터 오른쪽 방향으로 데이터 집합을 검사하면서 기준보다 큰 요소를 찾고, 또 한명은 오른쪽 부터 왼쪽방향으로 검사하면서 기준보다 작은 요소를 찾습니다. 그리고 이 두 정찰병이 찾아낸 두 요소를 교환하는 겁니다. 그리고 두 정찰병이 접선할 때까지 검사를 계속 진행하면서 교환해야 될 요소를 찾아내고 교환을 수행합니다. 두 정찰병이 접선하면 기준 요소를 왼쪽 데이터 집합의 마지막 요소와 교환하는 것으로 종료합니다.

이런 방식으로 정렬을 해 나가면 됩니당. 굳이 저렇게 A,B로 나눠서 풀지 않아도 되고, 결국에 퀵 정렬은 기준요소 보다 작은건 왼쪽, 큰 건 오른쪽으로 배열 위치를 바꿀수 있기만 하면 됩니다!!

혹시나 저거 다음에는 어떻게 정렬함? 이라고 잘 모르시는 분이 계시다면 댓글 남겨주세요. 최대한 자세하게 알려드릴게요! 

 

파이썬 코드부분은 나중에 올릴게요~! 같이보면 이해가 잘 될 겁니당. 그럼 다음엔 선택정렬과 최근접 점의 쌍문제로 들고 올게요. 모두 수고링 바바링

 

 

 

출처 : [알기쉬운 알고리즘-양성봉] 전공책입니다. [뇌를 자극하는 알고리즘 - 박상현]을 참조하였습니다.