8-1) 정렬 - 종류, 선택 정렬

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

정렬 (sort)

컴퓨터 분야에서는 데이터를 정렬해야 하는 경우가 많이 발생하는데, 이를 효과적으로 해결하기 위한 알고리즘과 이 알고리즘을 비교하는 다양한 기준이 있다.

(*강의에서는 숫자를 정렬하는 경우만을 다룬다.)

 

---

out-of-place 정렬

모든 데이터를 자료 구조의 복사본에 옮긴 후(저장공간) 순서대로 배열하여 정렬하는 방법이다. 책을 정리할 때 모든 책을 다 꺼내어 바닥에 두고 다시 순서대로 꽂아 정리하는 방법에 비유할 수 있다.

 

in-place 정렬

out-of-place와 달리 자료 구조를 그대로 둔 채 그 안에서 요소의 위치만 shuffle하여 정렬하는 방법이다. 책꽂이에서 책을 하나 꺼내어 원하는 위치에 다시 꽂는 작업을 순서대로 해나가는 방법에 비유할 수 있다.

 

 

---

 

안정 정렬

중복된 숫자가 정렬 이전에 놓여있던 순서를 유지한 상태로 정렬되는 방법이다.

 

불안정 정렬

중복된 숫자의 순서를 보장할 수 없는 방법이다. out-of-place 정렬의 비유 상황에서 책을 다시 꽂을 때 원래의 순서에 맞게 정렬된다는 보장이 사라지는 것과 같다.

 

---

 

시간 복잡도

Worst case, Average case, Best case의 복잡도를 고려한다. Worst case는 정 반대로 정렬해야 하는 경우로 예를 들어 오름차순 정렬을 하기 이전에 내림차순으로 놓여있었던 경우이다. Average case는 완전한 임의의 리스트를 정렬하는 경우이며 Best case는 이미 정렬이 되어있는 경우일 것이다.

 

 

선택 정렬 (select sort)

정렬 알고리즘 중 하나인 선택 정렬은 인덱스 0부터 시작하여 차례대로 뒤의 숫자들과 하나하나 비교해 가장 작은 수가 나오면 앞으로 오도록 교체하는 방법이다. 리스트 내에서 그대로 둔 채 순서만 바꾸기 때문에 in-place 정렬이며 불안정 정렬이다. (정확하게는 데이터 교환 과정에서 임시 변수를 필요로 하지만 적은 양이기 때문에 in-place로 본다고 한다.)

선택 정렬의 시간 복잡도를 계산해보면, 1회전(round)에서 n-1번 대소비교하고 2회전에서 n-2, 3회전에서 n-3 순서로 비교해 나간다. 따라서 (n-1) + (n-2) + (n-3) .... 이므로 시간 복잡도는  O(n^2) 이다. 또한 이 경우, 이미 리스트가 잘 정렬되어 있다 하더라도 비교하기 전까지 모르기 때문에 0부터 끝까지 대소비교를 거쳐야 한다. 따라서 worst, best, average 모두 O(n^2)가 된다.

for문을 사용하여 비교적 간단하게 구현할 수 있다.