764. sorting algorithm

2015-05-22 12:28:55

---

정렬은 자료를 지정한 순서로 나열하는 것을 말한다. 퀵 정렬 알고리즘으로 정렬을 진행하는 모습

정렬이란 자료들을 지정된 순서로 나열하는 것을 의미한다. 여기서 지정된 순서는 작은 것부터 큰 것으로 나열하는 오름차순이거나 큰 것에서 작은 것으로 나열하는 내림차순이 될 수 있다. 정렬하는 데 있어서 가장 큰 장점은 원하는 자료를 쉽고 빠르게 찾을 수 있다는 점이다. 대표적인 예로 영어사전을 들 수 있다. 영어사전에서 'quick‘이라는 단어를 찾는다고 가정해보자. 영어사전의 단어들은 알파벳순으로 정렬되어있기 때문에 사전의 뒷부분에서 ’quick‘을 쉽게 찾을 수 있다.
만약 단어들이 정렬되어있지 않고 막 섞여있다면 그 많은 단어들 사이에서 원하는 단어를 찾는다는 것은 거의 불가능할 것이다.

이러한 정렬의 장점을 체감할 수 있는 예는 인터넷에서 흔히 찾아볼 수 있다. 여러분은 한번쯤은 인터넷으로 쇼핑을 해보았을 것이다. 쇼핑을 하다 보면 검색한 상품들을 높은 가격 혹은 낮은 가격으로 정렬해 본적이 있을 것이다. 이 또한 내가 원하는 가격대의 상품을 여러 페이지에 걸쳐 찾기보단 한 눈에 보이도록 하는 것이 편리하기 때문에 정렬하는 것이다. 이렇듯 정렬은 우리 생활에서 필수적이고 쉽게 찾아볼 수 있다.

인터넷 쇼핑은 가격 등 여러 가지 순서로 정렬하는 기능을 제공한다.

 

정열을 하는 여러 방법

정렬하는 방법에는 여러 가지가 있다. 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬 등 다양한 정렬 알고리즘이 개발되었다. 그러나, 가장 대표적인 방법이라면 퀵 정렬(Quick Sort)을 꼽을 수 있다. 퀵 정렬 알고리즘은 다른 알고리즘에 비해 자료들을 서로 비교하고 교환하는 횟수가 적다는 장점을 가지고 있다. 이는 수행 시간의 단축으로 이어지게 되고, 이는 자료를 관리하는 데 있어 필수적이다. 따라서 대용량 데이터베이스 처리 시스템 등 다양한 분야에서 활용되고 있다.

 

 

https://youtu.be/ZZuD6iUe3Pc

여러 가지 정렬 알고리즘의 속도를 비교한 동영상. 가운데에 표시된 퀵 정렬이 대체로 가장 빠른 결과를 보여준다. 그러나 자료에 따라서는 퀵 정렬 보다 다른 정렬이 더 빠를 수도 있다. <출처: Viktor Bohush, 유튜브>

 

퀵 정렬

퀵 정렬은 어떠한 자료를 기준으로 작거나 같은 값을 지닌 자료는 앞으로, 큰 값을 지닌 자료는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. 이는 오름차순으로 정렬할 때의 정의를 설명한 것이다. 아직 정의가 쉽게 와 닿지 않을 것이다. 일단, 작은 값은 앞으로 보내고 큰 값은 뒤로 보낸다는 점만 기억하고 따라 와보자. 오름차순이기 때문에 작은 것이 앞으로 가고 큰 것이 뒤로 가는 점은 당연하지 않겠는가?

 

https://youtu.be/8hEyhs3OV1w

퀵 정렬을 보여주는 동영상. 처음에는 방법을 알 수 있도록 천천히, 뒤로 갈수록 점점 빨리 정렬하는 영상이다. <출처: Timo Bingmann / 유튜브>

 

퀵 정렬의 알고리즘 이해

퀵 정렬(Quick Sort)에 대해 자세히 알아보자. 아무렇게 나열된 10개의 수들을 퀵 정렬 알고리즘을 통해 오름차순으로 정렬하려고 한다고 가정해보자. 퀵 정렬을 하기 위해서는 먼저 10개 의 수들에 다음과 같이 4개의 레이블을 달아줘야 한다.

각각의 레이블들이 의미하는 바는 다음과 같다.

위의 그림에서는 right와 high는 같은 값을 가리키고 있다. 정렬 대상이 정해지면 left와 right는 고정되지만 low와 high는 다음의 규칙에 따라 계속 이동하게 된다.

이는 오름차순으로 정렬할 경우의 규칙을 나타낸 것이다. 만약 내림차순으로 정렬한다면, low와 high의 규칙은 서로 바뀌게 될 것이다. 이제 퀵 정렬의 기본적인 과정에 대해 알아보자.

1) 피벗보다 우선순위가 낮은 값이 나올 때까지 low를 오른쪽으로 이동한다.
2) 피벗보다 우선순위가 높은 값이 나올 때까지 high를 왼쪽으로 이동한다.
3-1) 만약, low와 high가 교차되었다면, 피벗의 값과 high가 가리키는 값을 교환한다.
3-2) 그렇지 않다면, low와 high가 가리키는 값을 서로 바꾼다.

과정을 글로만 보니 쉽게 와 닿지 않을 것이다. 다음 그림으로 과정에 대해 구체적으로 알아보자.

필자는 피벗을 가장 왼쪽에 있는 6을 선택했다. 10개의 수들 중 아무 값을 피벗으로 선택해도 되지만 이에 대한 설명은 먼저 과정을 배운 다음에 설명하도록 하겠다.

위의 규칙에 따라서 low와 high는 한 칸씩 이동한 것이다. 먼저 low의 위치에 대해 살펴보자. low는 피벗(6)보다 큰 값인 9를 만나서 그 자리에서 잠시 멈추었다. high도 피벗(6)보다 작은 값인 1을 만나서 그 자리에서 잠시 멈춘 것이다. 여기서는 우연히 low와 high가 서로 동일하게 한 칸씩 이동했는데 그럴 필요는 없다. low와 high의 이동은 서로 독립적이므로 각각 규칙에 맞게 이동하면 된다. 즉, low는 한번에 3칸 이동하고 high는 1칸 이동해도 상관없다는 뜻이다.

아직 low가 high은 서로 교차하지 않았으므로 다음과 같이 low와 high가 가리키는 값을 서로 바꿔준다.

다시 low는 위의 규칙에 따라 계속해서 오른쪽으로 high는 왼쪽으로 이동한다. 먼저 low는 피벗(6)보다 큰 값인 7에서 멈춘다. 이제 high를 이동하려 하는데 다음과 같이 high가 low를 앞서는 상황이 일어나게 된다.

이전까지의 과정에 의하면 low와 high의 값을 서로 바꿔주어야 한다. 하지만 high가 low를 앞서는 순간 3-1의 과정으로 넘어간다. 피벗과 high가 가리키는 값을 바꿔주는 것이다. 다음 그림을 살펴보자.

맨 앞에 있던 6과 high가 가리키던 5가 서로 바뀌었다. 지금까지 low와 high를 이동하고 서로 값을 바꿔주는 이러한 과정은 처음에 맨 앞에 있던 피벗의 위치를 바로잡기 위한 과정이었다. 6의 위치를 다시 한 번 살펴보자. 6 앞으로는 모두 6보다 작은 값들이고, 6 뒤로는 모두 6보다 큰 값들이다. 이는 앞으로의 어떠한 정렬 과정을 거치더라도 6의 위치는 변함없다는 뜻이다.

이제 다음 과정은 무엇일지 감이 오는가? 6 앞에 있는 값들과 뒤에 있는 값들을 대상으로 각각 지금까지 한 과정을 반복하면 되는 것이다. 계속 지금까지의 과정을 반복하다 보면 모든 수들이 자기 위치를 찾는 때가 오지 않겠는가? 아직 과정이 익숙하지 않을 수 있으므로 한 번 더 과정을 그림으로 설명하고자 한다. 먼저 6보다 작은 값들을 정렬해보자. 이전의 과정과 동일하게 다음과 같이 시작하면 된다.

이제 피벗(5)보다 큰 값이 나올 때까지 low를 오른쪽으로 이동시켜보자. 하지만 이전과는 다르게 계속 하나씩 비교하면서 정렬 대상의 마지막까지 가도 5보다 큰 값이 나오질 않는다.

그리고 동시에 low는 high를 지나치게 된다. 즉, low와 high가 교차된 것이다. 교차되면 바로 피벗의 값과 high가 가리키는 값을 바꾼다.

이제 5도 자기 위치를 찾았다는 것이 보이는가? 5 앞으로는 모두 5보다 작은 수들이다. 계속 이런 식으로 반복해나가는 것이다. 전체적인 정렬 과정을 그림으로 나타내면 다음과 같다.

피벗(6)을 정한다.

low(1)와 high(9)를 교환한다.

피벗(6)과 high(5)를 교환한다.

6을 기준으로 앞뒤로 각각 피벗(5,7)을 정한다.

앞에서는 피벗(5)과 high(4)를 교환한다. 뒤에서는 교환할 것이 없으므로 그대로 나둔다.

피벗(4,9)을 정한다.

앞에서는 피벗(4)과 high(2)를 교환한다. 뒤에서는 피벗(9)과 high(8)을 교환한다.

피벗(2)을 정한다.

피벗(2)과 high(1)을 교환한다.

정렬 완료

앞서서 피벗을 정할 때 가장 왼쪽을 선택한다고 말한 바 있다. 하지만 이는 여러분의 이해를 돕기 위해 편의상 그래온 것이지 꼭 맨 앞의 값을 선택할 필요는 없다.

 

퀵 정렬의 속도는 피벗이 영향을 준다

그렇다면 어떤 값을 피벗으로 정해야할까? 이것에 대한 정답은 없다. 어느 값을 피벗으로 하든 결과적으로는 모두 정렬이 되기 때문이다. 하지만 피벗을 어느 것으로 하는지에 따라 수행 속도에 차이가 생기게 된다. 예를 들어 다음과 같이 숫자들이 나열되어 있다고 가정해보자. 이 경우 정렬의 과정에서 앞에서부터 하나씩 자기 위치만 잡아갈 뿐, 피벗이 중간의 어느 값과 교환되어 둘로 나뉘게 되는 일이 생기지 않는다. 퀵 정렬의 빠른 성능을 보장하는 것은 분할인데 이 경우는 그러한 장점을 살리지 못하게 된다.

 

퀵 정렬 슈도코드

다음은 지금까지 그림을 알아본 퀵 정렬 알고리즘을 간략하게 슈도코드로 나타낸 것이다. 아래의 코드가 쉽게 와 닿지 않을 수 있지만 차근차근 살펴보면 이해할 수 있을 것이다.

줄코드

1	Quick Sort Algorithm
2
3	Partition // ‘분할’의 뜻을 가지고 있다.
4	{
5	low = left + 1 // low의 위치는 left보다 한 칸 오른쪽이다.
6	high = right // high의 위치는 right와 동일하다.
7	pivot = arr[left] // 피벗의 위치는 가장 왼쪽이다.
8
9	while (low <= high) // low와 high가 교차되지 않을 때까지 계속 반복한다.
10	{
11	while (pivot >= arr[low] and low <= right) // 피벗보다 큰 값을 찾을 때까지
12	low++ // low를 한 칸 오른쪽으로 이동한다.
13
14	while (pivot <= arr[high] and high >= (left + 1) // 피벗보다 작은 값을 찾을 때까지
15	high-- // high를 한 칸 왼쪽으로 이동한다.
16
17
18	if (low <= high) // low와 high가 교차되지 않았다면,
19	low가 가리키는 값과 high가 가리키는 값 교환
20	}
21	피벗의 값과 high가 가리키는 값 교환 // low와 high가 교차되었다면
22	return high // high의 위치를 가져온다.
23	}

글안성진 | 성균관대학교 컴퓨터교육과 교수성균관 대학교 정보공학과를 졸업하고 동 대학원에서 박사학위를 받았다. 한국컴퓨터교육학회 회장, 미래창조과학부 ICT인재양성전문위원회 위원장 등을 역임했고, 행정안전부장관표창, 대통령표창을 받았다. 현재 성균관대학교 컴퓨터교육과 교수이다. [Naver 소프트웨어야 놀자] 캠페인에 자문을 하고 있다.인물정보 더보기

글고근호 | 성균관대학교 컴퓨터교육과 재학

발행2015.05.22