[알고리즘] 기본 정렬 알고리즘 (Sorting Algorithms)

전윤혁·2024년 5월 11일

목록 보기

3/4

정렬 알고리즘이란?

정렬 알고리즘은 데이터 요소들을 특정 순서대로 정렬하는 알고리즘이다. 일반적으로 리스트나 배열 같은 데이터 구조에 저장된 요소들을 오름차순이나 내림차순 같은 순서로 재배열하는 데 사용된다.

선택 정렬 (Selection Sort)
삽입 정렬 (Insertion Sort)
버블 정렬 (Bubble Sort)
합병 정렬 (Merge Sort)
퀵 정렬, 퀵소트 (Quick Sort)

1. 선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 작은(또는 가장 큰) 요소를 찾아서 리스트의 가장 앞, 또는 가장 뒤로 옮기고, 정렬되지 않은 나머지 리스트 부분에 같은 과정을 반복하여 전체 배열을 정렬하는 방식이다. 예시는 단순히 최댓값을 찾은 후 리스트의 뒤로 옮기는 과정을 반복하고 있다.

선택 정렬의 시간 복잡도

선택 정렬은 모든 상황에서 $O(n^2)$ 의 시간 복잡도를 가진다. 각 자리에 와야하는 최솟값, 또는 최댓값을 구하기 위하여 n-1, n-2, n-3, ... , 1번의 비교연산을 수행하기 때문이다.

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입함으로써 배열을 정렬하는 방법이다. 아래 예시 리스트는 이미 정렬된 부분(색칠된 부분)에 31을 삽입하는 과정을 보여준다.

삽입 정렬의 시간 복잡도

모든 원소가 이미 정렬되어 있는 경우: $O(n)$
모든 원소가 이미 정렬되어 있는 경우, 각 원소를 삽입하는 과정에서 비교 연산은 1번씩만 수행된다. 원소를 삽입하는 과정은 n-1번 이루지므로, 시간 복잡도는 $O(n)$ 이 된다.

모든 원소가 역순으로 정렬되어 있는 경우: $O(n^2)$
각 원소를 n-1번 삽입하는 동안 비교연산은 1, 2, 3, ... , n-1번 수행된다. 따라서 최악의 경우, 삽입 정렬의 시간 복잡도는 $O(n^2)$ 이 된다.

3. 버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 2개의 원소를 비교하여, 크기가 순서대로 되어 있지 않으면 서로 교환하는 과정을 반복하여 전체 배열을 정렬하는 방식이다. 아래의 예시는 배열을 오름차순으로 정렬할 때, 인접한 2개의 원소를 비교하여 왼쪽의 원소가 오른쪽의 원소보다 클 경우 교환을 진행한다.

예시의 결과, 가장 큰 원소인 93이 배열의 가장 끝에 위치하게 된다. 이와 같이 버블 정렬을 1회전 수행할 때마다 정렬된 원소가 하나씩 늘어나게 되고, n회전을 수행하면 배열이 전부 정렬되게 된다.

버블 정렬의 시간 복잡도

버블 정렬은 모든 상황에서 $O(n^2)$ 의 시간 복잡도를 가진다. 배열이 얼마나 정렬되었는지의 여부와 관계 없이, n-1, n-2, n-3, ... , 1번의 비교연산을 수행한다는 점을 알 수 있다.

4. 합병 정렬 (Merge Sort)

합병 정렬은 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다. 합병 정렬은 하나의 배열을 두 개의 균등한 크기의 배열로 분할하고, 분할된 부분 배열들을 정렬한 다음, 정렬된 하위 배열들을 결합하는 방식으로 전체 배열을 정렬한다. 정렬은 아래의 단계로 이루어진다.

분할 (Divide)
배열을 두 개의 동일한 크기의 하위 배열로 나눈다. 배열의 크기가 1이 될 때까지 이 과정을 재귀적으로 반복한다.
정복 (Conquer)
나누어진 두 개의 배열을 정렬한다. 이 과정에서, 두 배열의 요소들을 각각 비교하여 결과 배열에 차례대로 배치한다.
결합 (Combine)
분할된 배열을 순차적으로 합병하면서 최종적으로 하나의 정렬된 배열로 만든다.

아래의 예시는 위의 과정을 구체적으로 보여준다. 먼저 배열의 크기가 1이 될 때까지 분할 과정을 반복한다. 이후, 나누어진 두 개의 배열을 정렬한다. 예시의 일부를 설명하면, [26, 54] 와 [17, 93] 을 정렬하는 과정은 각 배열의 원소를 모두 비교하여 최소값 17을 먼저 위치시키고, 그 다음 26, 54, 93을 순차적으로 위치시키는 방식으로 진행된다. 결과적으로 분할된 배열을 합병하는 방식으로 정렬이 수행된다.

합병 정렬의 시간 복잡도

합병 정렬은 모든 상황에서 $O(n\ log\ n)$ 의 시간 복잡도를 가진다.

크기가 n인 배열을 분할하는 작업 자체에는 상수 시간, 즉 O(1)이 소요된다. 하지만 중요한 것은 분할의 깊이, 즉 재귀의 깊이이다. 배열의 크기를 계속 반으로 나누면, 로그(log) 스케일로 깊이가 결정된다. 따라서 분할의 최대 깊이는 $log\ n$ 이다.

각 분할 단계에서, 합병 작업은 두 하위 배열의 전체 길이에 비례하는 시간이 소요된다. 각 분할 레벨에서 배열의 총 길이는 n이므로 각 레벨의 합병 작업에는 $O(n)$ 의 시간이 필요하다.

따라서 합병 정렬의 시간 복잡도는 각 레벨에서 n의 작업을 수행하고, 그 레벨이 $log\ n$ 만큼 있으므로 전체 시간 복잡도는 $O(n\ log\ n)$ 이 된다.

5. 퀵 정렬 (Quick Sort)

퀵 정렬 또한 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다. 퀵 정렬은 이름에서 볼 수 있듯이 평균적으로 매우 빠르며, 대규모 데이터셋에 적합한 성능을 보여준다. 퀵 정렬은 특정 요소 피벗(Pivot)를 기준으로 배열을 두 부분으로 나누고. 각 부분을 재귀적으로 정렬하는 방식으로 작동한다.

아래의 예시에서는 54를 피벗으로 설정하였다. 54를 기준으로 더 작은 원소는 왼쪽으로, 더 큰 원소는 오른쪽으로 분할한다. 구체적으로 설명을 하면 아래와 같다.

left 포인터를 배열의 두 번째 요소(인덱스 1)에 위치시킨다.
right 포인터를 배열의 마지막 요소에 위치시킨다.
left 포인터를 오른쪽으로 이동시키면서 피벗보다 큰 같은 값을 찾는다.
right 포인터를 왼쪽으로 이동시키면서 피벗보다 작은 값을 찾는다.
left와 right 포인터가 가리키는 값이 서로 교차하기 전까지, 즉 left 포인터가 right 포인터보다 작거나 같은 동안, 두 포인터가 가리키는 값을 교환한다.
left와 right 포인터가 교차하는 지점을 찾았다면, right 포인터가 가리키는 값과 피벗(첫 번째 요소)을 교환한다. 이렇게 하면 피벗은 배열의 중간 어딘가로 이동하며, 피벗 왼쪽의 모든 값은 피벗보다 작거나 같고, 피벗 오른쪽의 모든 값은 피벗보다 크게 된다.

퀵 정렬의 시간 복잡도

최선의 경우, 평균적인 경우: $O(n\ log\ n)$
퀵 정렬에서 최선의 경우는 피벗이 매번 정확히 배열을 두 동등한 부분으로 나누는 경우이다. 이 경우, 각 재귀 호출마다 처리해야 할 데이터의 양이 절반으로 줄어들게 된다. 이로 인해 시간 복잡도는 $O(n\ log\ n)$ 이 된다. 평균적인 경우, 피벗이 배열을 완벽하게 반반으로 나누지는 않지만, 대체로 균형 잡힌 분할을 유지한다.

최악의 경우: $O(n^2)$
퀵 정렬의 최악의 경우는 피벗이 매번 최소 또는 최대 요소로 선택될 경우이다. 예를 들어, 이미 정렬된 배열에서 첫 번째 또는 마지막 요소를 피벗으로 선택하면, 한 쪽 분할은 0개의 요소를 가지고 다른 쪽 분할은 n−1개의 요소를 가지게 된다. 이 경우, 퀵 정렬은 단순히 각 요소를 제자리로 이동시키는 작업만 하게 되며, 각 단계에서 n−1,n−2,...,1의 비교를 수행해야 하므로, 시간 복잡도는 $O(n^2)$ 가 된다.