정렬알고리즘 비교하기와 안정성

정렬 알고리즘은 자료구조에서 가장 중요한 부분입니다. 중요하고 종류가 많아서 정렬 알고리즘을 잘 이해하고 것이 컴퓨터공학에서는 매우 중요합니다. 여러 가지 특징으로 정렬 알고리즘을 비교하면서 장단점을 비교해 보는 것이 공부에 도움이 됩니다. 또한 정렬 알고리즘의 성질 중에서 안정성이라는 것이 있는데요, 이게 뭔지, 왜 중요한지 한번 정리해 보겠습니다.

정렬 알고리즘의 안정성

어떤 정렬 알고리즘은 안정적이다(stable) 또는 안정성(Stability)을 만족한다고 얘기하는데요, 이것은 동일한 요소에 대해 정렬할 때 어떻게 처리하는가를 다루는 문제입니다. 안정적 알고리즘은 동일한 값의 순서가 정렬에 의해 바뀌지 않습니다. 즉 같은 값이라면 앞에 있던 것이 먼저 나오게 정렬하는 것입니다. 원래 값의 순서를 지켜주는 것이지요.

그럼 정렬 알고리즘의 안정성이 어떤 경우에 필요할까요? 엑셀에서 키 정렬하는 경우를 생각해 보겠습니다. 여러 개 필드를 가지는 값에 대해 지정된 키의 순서로 정렬할 때 같은 키 값을 가지는 행들이 여러 있다면 그들의 순서가 뒤섞이는 경우 혼란스럽겠죠? 아래 그림처럼 왼쪽의 데이터를 제품명으로 정렬했을 때 정렬된 오른쪽 리스트에서 월일 순서는 유지되는 것이 바람직할 것입니다. 엑셀은 반드시 안정성을 만족하는 정렬 방법을 써야 합니다.

어떤 정렬 알고리즘이 안정성을 만족하는가?

정렬 알고리즘들은 두 요소를 비교하여 필요할 때 위치를 바꾸면서 정렬을 하게 됩니다.

예를 들어 삽입 정렬은 어떨까요? 앞부분은 정렬되어 있고 다음 값이 들어갈 위치를 찾아 한칸씩 밀면서 그 값을 집어넣습니다. 이 때 들어갈 위치는 같은 값이 있다면 그 뒤에 들어가게 되겠죠? 그러니까 안정성을 만족합니다. 다음 값이 같은 값보다 앞으로 자리를 바꾸어 들어갈 일은 없으니까요. 대신에 삽입정렬은 정렬된 부분의 요소들을 모두 뒤로 한칸씩 밀어야 하므로 요소의 개수가 많은 경우 이동이 많습니다. 

삽입정렬에서 같은 값이 자리를 찾아 들어가는 과정

선택 정렬은 어떨까요? 선택된 부분을 제외하고 나머지 중에서 가장 작은 값(오름차순, 그림에서 11)을 찾고 다음 값(그림에서 18)과 자리를 바꿉니다. 한칸씩 미는 게 아니므로 다음 값이 훨씬 뒤쪽에 있는 값과 바뀔 수 있죠? 그 앞에 같은 크기의 값(18)이 있을 가능성이 얼마든지 있습니다. 그러므로 원본에서 앞에 있던 18이 두번째 18보다 뒤쪽으로 가게 되었으므로 안정적이지 않습니다. 여기서 안정적이지 않다는 의미는 다음과 같습니다. 이후의 정렬 과정에서 값이 다른 것은 확실하게 순서가 보장되지만 같은 값에 대해서는 바뀌기를 반복하는 과정에서 어떻게 될지 알수 없다는 뜻입니다.

선택정렬에서 값은 크기의 값이 뒤로 가게 되는 경우

즉 안정적이지 않은 정렬은 멀리 있는 값과 자리를 바꾸는 경우임을 알수 있습니다. 버블 정렬은 옆에 있는 값과 비교하여 자리를 바꾸고 같은 값이면 바꾸지 않으니까 안정적입니다. 합병정렬은 좀 다른 경우인데, 분할된 두 리스트가 정렬된 후 합쳐질 때를 생각해 보면 우리는 두 리스트 간에 순서가 있어서 같은 값이 나타나면 앞쪽 리스트 것을 먼저 합병리스트에 넣을 것입니다. 연속된 값은 값이 있는 경우도 순서대로 들어올 것이구요. 그러므로 같은 값의 순서가 바뀔 일은 없습니다.

버블정렬과 합병정렬에서 같은 값의 처리

그럼 안정적이지 않은 정렬을 생각해 볼까요? 

쉘정렬은 기본 아이디어가 멀리 있는 것들과 먼저 순서를 정리하게 하자는 것입니다. 그래서 멀리 있는 요소들과 자리를 바꾸는 일이 많이 생기게 됩니다(아래 그림에서 33과 18이 자리를 바꾸게 됨). gap이 줄어들면서 비교하게 되는 값들이 달라지게 하는 것이 중요합니다. 그래서 gap을 홀수로 정하라고 하지요? 즉 매 단계마다 비교하여 자리를 바꾸는 값의 그룹이 달라지게 됩니다. 이 경우 멀리 있는 요소와 값을 바꾸어 뒤로 간 요소가 그 앞쪽에 있는 동일한 값의 요소와 순서가 바뀌는 일이 얼마든지 발생할 수 있습니다.

퀵정렬은 어떨까요? 피봇을 정한 후 왼쪽에서 피봇보다 큰 첫 값(그림에서 69)을 오른쪽 끝에서 피봇보다 작은 첫번째 값(18)과 자리를 바꿉니다. 이것도 멀리 있는 요소와 자리를 바꾸게 되는데요, 그러니까 뒤의 작은 값이 같은 값을 가지는 요소보다 앞으로 가버릴 가능성이 얼마든지 있지요. 

퀵정렬에서 뒤에 있던 같은 값 18이 앞으로 가게되는 경우

힙정렬은 부모와 자식이 순서를 바꾸어 업힙 또는 다운힙하게 되므로 역시 멀리 있는 요소와 위치를 바꾸는 정렬 알고리즘이 됩니다.

정리하면 멀리 있는 요소와 값을 바꾸는 정렬 알고리즘은 안정적이지 않습니다. 같은 값을 가지는 요소를 건너뛰어 훨씬 뒤쪽에 있는 요소와 자리를 바꾸게 되는 선택이나 쉘, 퀵, 힙정렬은 안정적이지 않은 정렬알고리즘이 됩니다. 반면에 차례로 밀거나(삽입) 옆에 있는 요소와 자리를 바꾸거나(버블) 합병처럼 별도의 메모리를 이용하여 차례로 모으는 알고리즘은 원본의 순서를 유지할 수 있게 되지요.

TimSort 알고리즘

타임소트(또는 팀소트라고 읽음)는 삽입정렬과 합병정렬을 합친 방법으로 2000년 이후 파이썬이나 자바의 언어구현에서 사용하는 정렬 알고리즘으로 알려져 있습니다. 타임소트는 작은 사이즈의 데이터에 대해서는 삽입정렬을쓰고 큰 데이터에 대해서는 반씩 쪼개서 합병정렬 방법으로 정렬을 하게 됩니다. 즉  입력 리스트를 반씩 쪼개다가 쪼개진 단위가 정해진 길이보다 같거나 작아지면 쪼개는 것을 멈추고 각 부분을 삽입정렬로 정렬합니다. 그 다음 두 개의 쪼개진 단위를 합병정렬로 합칩니다. 이때 원래의 합병 정렬과 약간 다른 방식을 써서 정렬된 부분에서 다음 값이 들어갈 위치를 한개씩 찾지 않고 건너뛰면서 찾는galopping(갈로핑) 방식을 사용한다고 합니다.

파이썬이나 자바 같은 언어구현에서 사용하는 타입소트가 왜 삽입정렬과 합병정렬을 합쳤을까요? 합병정렬은 O(nlogn)으로 성능이 좋은 정렬알고리즘입니다. 추가 메모리를 필요로 하지만 그래도 성능이 워낙 좋으니 그것을 택했겠지요? 그리고 삽입정렬은  O(n2)이지만 일정 크기 이하의 리스트에 대해서는 잘 동작합니다. (단, 들어갈 위치를 만들기 위해 정렬된 부분을 한칸씩 밀어야 하는 일이 생기는데, 비교보다는 이동이 더 비싼 연산이므로 배열 구현이라면 문제가 되겠지요? 이것도 연결리스트로 구현되어 있다면 삽입을 위해 한칸씩 미는 것이 부담이 되지 않습니다.)

마지막으로 중요한 점, 삽입정렬과 합병정렬은 안정적인 정렬이라는 점입니다. 위에서 엑셀의 예로 살펴본 것처럼 원본 데이터의 순서는 매우 중요한 경우가 많습니다. 우리가 여러 후보 중에서 점수를 매겨 하나를 선정할 때는 동점 규정이라는 것이 있습니다. 안정성은 동점일 때 선착순(원래 순서 유지)으로 하는 가장 상식적인 방법을 보장해 주는 알고리즘이라고 할 수 있습니다.

P.S.

[질문] 정렬 알고리즘은 왜 이렇게 많을까요?

역사적으로 발명되어온 알고리즘들이 쌓이면서 많아졌겠죠? 새로 나온 방법보다 모든 면에서 못한 알고리즘은 사라졌을 것이고 지금까지 살아남은 이 알고리즘들은 여러 가지 이유로 장점을 가지고 있기에 자료구조 교재에 등장을 할 것입니다. 구현이 간단하거나, 이해하기 쉬워서일 수도 있고 자료구조의 특징이나 특정 환경에서 잘 맞을 수도있고 성능이 꼭 필요한 경우, 메모리가 부족한 경우 등 상황에 따라 다른 알고리즘을 선택할 수 있습니다. 프로그래밍 언어가 그렇게 많은 이유와 비슷하겠죠? 약간씩 장단점이 있고 특징이 있으니까 그런 것을 비교해보는 것도 재미있는 주제가 됩니다.

[질문] "정렬 알고리즘을 이렇게 외워서 써야 하는 이유가 뭔가요?" 

학생들이 질문한 것 중에 이런 것도 있습니다. 알고리즘을 공부해야 하는 이유겠죠? 우리는 바퀴를 재발견하고 싶지 않습니다. 컴퓨터공학의 빛나는 유산인 뛰어난 알고리즘들을 우리가 머리를 싸매고 새로 발견해 보는 것도 좋지만 공학도로서 좋은 방법을 배우고 익혀 잘 써먹는 것이 더 좋은 경우가 되겠지요? 실제 문제에 부딪히면 응용하고 변형해야 하는 경우가 많습니다. 머리써야 할 일들이 많으니까... 공부하는 만큼 실력이 되겠죠...