[알고리즘] 역순 정렬에 효율적인 정렬 알고리즘은?

정렬을 위한 알고리즘은 다양하다. 따라서 각각의 상황에 맞는 정렬 알고리즘을 적절히 사용해야 한다. 이번에는 내림차순으로 정렬된 수들을 다시 오름차순으로 정렬하기 위해서는 어떠한 기법이 효율적이며 왜 그런 것인지 알아보려고 한다. 잘못된 내용은 댓글에 적어주시면 감사하겠습니다.

---

아래처럼 10부터 내림차순으로 정렬되어 있는 것을 오름차순으로 정렬하려고 한다. 어떻게 하는 것이 가장 효율적인 방법일지 생각해보자.

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

 

빈번한 교환은 비효율적

정렬을 할 때 두 수를 비교하여 두 수의 위치를 변경하는 횟수가 많을수록 비효율적인 알고리즘이 된다. 두 수를 교환하기 위해서는 임시 변수를 생성해야 하고 A를 임시 변수에 저장하고 A에 B를 저장 후에 B에 임시 변수를 저장하는 과정을 거치게 된다. (지금까지 이러한 빈번한 교환이 비효율적인 이유를 이렇게까지 밖에 설명을 못하겠다.) 

 

따라서 정렬을 할 때 비교도 비교지만 최대한 교환이 적게 일어나야 효율적인 알고리즘이 된다. 그렇다면 위에서 내림차순으로 정렬된 것을 오름차순으로 역순 정렬해야 할 때는 어떠한 알고리즘을 사용하는 것이 효율적일까?

 

자신의 위치를 찾아가는 삽입 정렬

오름차순을 기준으로 삽입 정렬은 특정 위치를 기준으로 왼쪽보다 작을 때는 왼쪽과 자리를 변경한다. 변경 후에는 또 다시 왼쪽과 비교하여 작을 때는 자리를 변경한다. 이때 왼쪽에 더 작은 수가 나올 때 또는 첫 번째 자리일 때는 자신의 자리를 맞게 찾아간 것이다.

 

이처럼 삽입 정렬은 왼쪽의 데이터와 비교하여 자리를 스왑하고 자기 자리를 찾아가는 것이다. 이를 역순 정렬에 대입해보자. 먼저 8부터 시작해보면 아래와 같은 과정이 일어난다.

[9, 10, 8, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 10, 7, 6, 5, 4, 3, 2, 1]
[8, 9, 10, 7, 6, 5, 4, 3, 2, 1]

8은 계속해서 왼쪽의 수보다 작기 때문에 교환이 일어난다. 그렇게되면 1은 최대 9번의 비교가 일어나고 자리를 스왑할 것이다. 따라서 삽입 정렬은 역순 정렬에 적합하지 않다.

 

pivot의 설정이 중요한 퀵 정렬

퀵 정렬은 pivot을 기준으로 pivot보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 이동시킨다. 이렇게 계속해서 pivot을 기준으로 왼쪽 또는 오른쪽으로 이동시켜서 정렬을 완성한다. 이때 pivot을 첫 번째 수로 설정하면 어떻게 될까?

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[9, 8, 7, 6, 5, 4, 3, 2, 1], [10]
[8, 7, 6, 5, 4, 3, 2, 1], [9], [10]
[7, 6, 5, 4, 3, 2, 1], [8], [9], [10]

계속해서 한 개의 수만 정렬된 위치로 이동하게 된다. 삽입 정렬보다는 효율적이지만 조금 더 효율적인 알고리즘을 생각해보자.

 

앞에서부터 차근차근 정렬하는 선택 정렬

선택 정렬은 앞에 저장되어야 하는 수(범위 내에 가장 작은 수)를 선택하여 앞자리와 교환하며 정렬하는 기법이다. 아래처럼 첫 번째 수부터 마지막 수까지 비교하여 가장 작은 수를 첫 번째 자리와 바꾼다. 이어서 두 번째 수부터 마지막 수까지 비교하여 가장 작은 수를 두 번째 자리와 바꾼다.

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 9, 8, 7, 6, 5, 4, 3, 2, 10]
[1, 2, 8, 7, 6, 5, 4, 3, 9, 10]
[1, 2, 3, 7, 6, 5, 4, 8, 9, 10]

위의 과정을 반복하다보면 정렬이 될 것이며 반복은 최대 원소의 개수의 반만큼 (N/2) 일어나게 된다. 한 번의 교환으로 두 개의 수를 알맞은 위치로 저장하게 되었다.

---

이처럼 역순 정렬을 할 때는 교환의 횟수가 적은 선택 정렬을 사용하는 것이 효율적이다. 각각의 정렬에 대한 특징을 정확히 알고있어야 알맞게 사용할 수 있는 것 같다.