Vamos ser Programador com Devfon

[Sorting Algorithm]

정렬이란 데이터를 특정 순서에 따라 나열하는 일련의 과정으로, 대개 우리는 배열 요소에 저장되어 있는 값에 따라 정렬을 한다. 이러한 정렬에 있어 그 기준은 수가 될 수도 있고, 단어 혹은 배열에 인접한 쌍(pairs)이 될 수 있다. 이를테면, 우리는 학급에 속한 학생들을 키에 따라 정렬해볼 수 있다. 혹은 우리나라의 도시를 영문 알파벳 순으로 혹은 도시에 거주하는 시민의 수에 따라 정렬해볼 수도 있을 것이다. 그리고 이러한 정렬 과정에 있어 가장 많이 사용되는 기준은 수의 크기에 따른 정렬(numerical order) 혹은 알파벳순에 따른(alphabetical order) 정렬이다.

다음 그림과 같이 정수로 이루어진 간단한 배열을 생각해보자

우리는 이 배열을 다음과 같은 오름차순으로 정렬하고자 한다.

Computer Science의 Algorithm에는 위같은 정렬을 위한 많은 정렬 알고리즘이 있으며, 각각의 알고리즘들은 시간 복잡도와 메모리 사용에 있어 큰 차이를 가진다. 다음, 정렬 알고리즘의 몇 가지 예를 살펴보자.

1) Selection Sort

# Code in Python3

-      개념: 배열의 첫 번째 원소에서 시작하여, 첫 번째 원소를 포함한 배열의 모든 값들 중 최소값을 찾은 후 이 최소값을 배열의 첫 번째 원소와 교환한다. 이후 두 번째 원소로 넘어가 첫 번째 원소를 제외한 배열의 값들 중 다음 최소값을 찾는다. 이러한 과정을 마지막 원소까지 반복하게 된다.

배열의 원소 개수가 k개라면, 첫 번째 원소는 k번의 반복 이후 자기의 자리(right order)를 찾아가게 된다. 이러한 성질을 ‘loop invariant’라고 하며, 자세한 내용은 링크 참조.

* 시간 복잡도는 두 번의 반복문이 중첩되어 있으므로, O(n²)

2) Counting Sort

[Input으로 받은 배열에서 0이 5번, 1이 3번, 2가 4번, 3이 0번 그리고 4가 2번 발생하였기 때문에 count array에 5, 3, 4, 0, 2가 기록되게 된다. 이 기록을 가지고 정렬된 배열을 Output으로 return 한다]

# Code in Python3

-      개념: Counting Sort를 이용하기 위해서는 정렬할 배열의 최대 크기 k를 알아야 한다. 이후 0을 포함하기 위해 배열의 최대 크기인 k에 1을 더한 크기 만큼의 [0]자 배열 count를 생성한다.

이후, 배열 A의 크기 만큼 반복문을 돌며 count의 index에 맞는 요소에 각 숫자의 등장 횟수를 count 해준다. 이후, count된 숫자를 그 등장 횟수만큼 배열 A에 삽입해주면, 오름차순 + 등장 횟수에 따른 배열 A가 정렬되게 된다.

* 시간 복잡도는 O(n + k). 배열의 모든 요소들을 정리하기 위해, O(k) 크기 만큼의 추가 메모리가 필요하다. 따라서 위 코드의 실행을 위해 필요한 시간 복잡도가 크게 느껴질 수 있다. 그러나 결국 이중 중첩된 아래 반복문의 연산(line 11, 12)은 O(n) 이상으로 수행되지 않는다.

3) Merge Sort * 아래 간단한 설명보다 구현이 복잡하기 때문에 wikipedia를 참고하는 것을 추천드립니다.

-      개념: 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 간주하지만, 그렇지 않은 경우 정렬되지 않은 리스트를 절반(홀수라면 한 개의 차이가 발생하도록)으로 잘라 비슷한 크기의 2개의 리스트로 나눈다. 이후 나뉘어진 두 개의 부분 리스트를 recursive 하게 합병 정렬을 이용해 정렬한다. 마지막으로 나누어진 두 부분 리스트들이 다시 재귀적으로 하나의 정렬된 리스트로 합병하도록 한다.

* 시간 복잡도는 O(n log n)

4) Sorting functions

-      만약 정렬하고자 하는 배열에 속한 값들의 그 범위를 모를 경우, O(n log n)의 시간 복잡도를 가지는 내장 정렬 함수를 통해 모든 값들을 정렬할 수 있다. 우리가 사용하는 많은 다양한 프로그래밍 언어들의 장점은 그것들이 가지는 내장 정렬 함수 기능에 있다. 만약 Python에서 list를 정렬하고 싶다면 우리는 아래의 한 줄 코드로 이같은 정렬을 수행할 수 있다.

* 시간 복잡도 O(n log n)

* 결론: 일반적으로, 정렬 알고리즘은 다른 알고리즘 문제에도 사용될 수 있는 흥미로운 수학적 개념들을 사용한다. 따라서 위와 같은 정렬 알고리즘이 내부적으로 어떻게 작동하는지 아는 것은 큰 배움이 될 수 있다. 그리고 더 나아가 이 알고리즘들을 스스로 구현해보는 것 역시 작동 방식을 아는 것 이상의 가치를 가진다! 또한 미래에는 내장된 정렬 함수를 사용해도 좋을 것이다. 내장 정렬 함수는 점점 빠른 성능을 보이게 될 것이며, 내장함수를 사용하는 것이 여러분의 코드를 보다 짧고 읽기 쉽게 만들어줄 것이기 때문이다.