정렬 알고리즘

나혜수·2023년 1월 27일

자료구조와 알고리즘

목록 보기

5/7

정렬 : 요소들을 일정한 순서대로 열거하는 알고리즘
정렬 알고리즘의 핵심은 데이터의 교환, 선택, 삽입이다.

버블 정렬

단순 선택 정렬

단순 삽입 정렬

셀 정렬

퀵 정렬

병합 정렬

힙 정렬

도수 정렬

정렬의 안전성

안정적 정렬 알고리즘은 값이 같은 원소의 순서가 정렬 후에도 유지된다. 하지만 안정적이지 않은 알고리즘은 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없다.

내부 정렬과 외부 정렬

내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우
외부 정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우
앞으로 다룰 정렬은 모두 내부 정렬이다.

1. 버블 정렬

이웃한 두 원소의 대소 관계를 비교해 필요에 따라 교환을 반복하는 알고리즘 = 단순 교환 정렬
버블 정렬은 이웃한 원소만 교환하므로 안정적이다.
원소 n개인 배열에서 n-1번 비교 or 교환하는데 이러한 과정을 패스라고 한다. 모든 정렬이 끝나려면 패스를 n-1번 수행해야 한다.

원소를 비교하는 횟수는 1번째 패스에서 n-1, 2번째 패스에서 n-2, ... 이므로 총 n(n-1)/2 이다. (패스를 한 번 수행할 때마다 정렬할 대상이 1개씩 줄어들기 때문)
실제 원소를 교환하는 횟수는 원소 값에 따라 영향받으므로 그 평균값은 n(n-1)/4 이다.
→ 시간복잡도 : O(n2)

개선 1
만약 k번째 패스에서 정렬을 마쳤다면 그 이후 패스에 대해선 원소 교환을 하지 않는다. 따라서 어떤 패스의 원소 교환 횟수가 0이면 정렬을 종료하여 알고리즘 실행 시간을 단축시킬 수 있다.

개선 2

마지막 교환에서 1,3,4는 정렬된 상태이다. 어떤 특정 원소(4) 이후 교환하지 않는다면 그 원소보다 앞의 원소는 이미 정렬을 마친 것이다. 따라서 두번째 패스는 6개를 비교하는 것이 아니라 1,3,4를 제외한 4개만을 비교하면 된다.
각 패스에서 마지막으로 교환한 두 원소 중 오른쪽 원소의 인덱스를 저장하여 다음 수행할 패스의 스캔 범위를 제한하면 된다.

셰이커 정렬 = (칵테일 정렬, 양방향 버블 정렬)
9 1 3 4 6 7 8
정렬이 거의 완료된 배열이지만 가장 큰 원소 9가 한 패스에 하나씩 뒤로 이동하기 때무에 정렬 작업을 빠르게 마칠 수 없다. 만약 9를 빠르게 맨 뒤로 이동시키면 속도는 훨씬 빨라질 것이다.
홀수 패스에서는 작은 원소를 앞으로 이동시키고, 짝수 패스에서는 큰 원소를 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾼다면 보다 적은 비교 횟수로 정렬할 수 있다.

2. 단순 선택 정렬

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하여 정렬하는 알고리즘이다.
정렬하지 않은 범위에서 가장 작은 값의 원소를 선택하고, 범위의 맨 앞 원소와 교환하는 작업을 반복한다. 이 알고리즘은 서로 떨어져 있는 원소를 교환하므로 안정적이지 않다.

이 과정을 n-1번 반복하면 전체 정렬을 완료한다. 원소 값을 비교하는 횟수는 n(n-1)/2번이다.
→ 시간복잡도 : O(n2)

3. 단순 삽입 정렬

선택한 요소보다 더 앞쪽에 알맞은 위치에 삽입하며 정렬하는 알고리즘이다. 단순 선택 정렬과 비슷하지만 가장 작은 값의 원소를 선택하지 않는다는 점이 다르다.
서로 떨어져 있는 원소를 교환하지 않으므로 안정적이다.

즉, 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입하는 작업을 n-1번 반복하며 각 반복마다 i번의 비교가 수행된다. 따라서 원소의 비교 횟수는 n(n-1)/2번이다.
→ 시간복잡도 : O(n2)

장점 : 정렬이 거의 끝나가는 상태에서는 속도가 매우 빠르다.
단점 : 삽입할 위치가 멀리 있으면 이동 횟수가 많아진다.

4. 셸 정렬

셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완해 빠르게 정렬하는 알고리즘이다.
정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복해 원소 이동 횟수를 줄인다.
셸 정렬은 이웃하지 않고 떨어져 있는 원소를 교환하므로 안정적이지 않다.

5. 퀵 정렬

퀵 정렬은 가장 빠른 정렬 알고리즘으로 널리 사용된다.
피벗을 기준으로 두 그룹으로 나눈다. 피벗은 그룹을 나누는 기준으로 임의로 선택할 수 있고, 2개로 나눈 그룹 어디에 넣어도 상관없다.

피벗 이하인 원소를 왼쪽으로, 이상인 원소를 오른쪽으로 이동시킨다. 나뉜 그룹에서 다시 피벗을 정하고, 피벗을 기준으로 두 그룹으로 나누는 과정을 반복한다. 그룹들이 더 이상 분할이 불가능할 때까지 반복한다.

피벗을 어떤 값으로 선택하느냐에 따라 성능이 달라진다.

피벗 선택하기

피벗 선택 방법은 퀵 정렬의 실행 효율에 큰 영향을 미친다. 빠른 정렬을 원한다면 배열의 중앙값을 피벗으로 하는 것이 이상적이지만, 중앙값을 구하려면 이에 대한 처리가 필요하고 처리를 위한 많은 시간이 걸린다. 따라서 피벗을 선택하는 의미가 없어진다. 이 문제 해결을 위해 다음 방법을 사용해 최악의 경우를 피하도록 한다.

방법 1
배열 원소 수가 3개 이상이라면, 임의의 원소 3개를 꺼내 중앙값인 원소를 피벗으로 선택

방법 2
배열의 맨 앞 원소, 가운데 원소, 맨 끝 원소를 정렬한 뒤, 가운데 원소와 맨 끝에서 두 번째 원소를 교환한다. 맨 끝에서 두 번째 값을 피벗으로 선택한 뒤 나눌 대상을 [left + 1] ~ [right - 2]로 좁힌다.