선택 정렬의 아이디어는 아주 간단합니다. 숫자를 큰 순서대로 마지막부터 바꾸거나, 혹은 작은 순서대로 처음부터 바꾸는 것입니다. 즉 모든 항목을 서로 비교합니다. 모든 항목을 비교하니 (모든 항목 x 모든 항목)으로 O(n2)이 걸리게 됩니다.
물론 어느정도 튜닝(이미 정렬된 항목은 확인하지 않도록)을 해준다면, 속도가 조금은 빨라질 수 있습니다. 하지만, 빅 오 표기법에서 상수항은 무시합니다. 따라서 이 속도가 조금 빨라지는 것은 시간복잡도를 계산하는 것에 영향을 주지 않습니다.
공간복잡도는 이미 존재하는 배열 내부에서 정렬을 하는 것이므로 O(1)입니다.
선택 정렬을 왜 배울까요?
보시다시피 O(n2) 은 굉장히 시간의 소요가 많다는 것을 알 수 있습니다. 그런데 왜 우리는 선택 정렬을 배울까요?
우리는 남이 작성한 정렬 알고리즘을 이용할 수도 있지만, 문제에 대한 다양한 접근 방법이 있을 수 있다는 것을 공부하고자 선택정렬을 배운다고 생각합니다.
정렬을 하는데에는 훌륭한 알고리즘도 많습니다. 하지만 이들 알고리즘과 선택 정렬이 추구하는 바는 같습니다. 주어진 항목들을 정렬하는 것이죠. 단지 그 방법이 다를 뿐입니다.
정렬은 왜 할까요?
더 본질적인 질문입니다. 왜 우리는 정렬을 해야할까요? 이전에 쓴 글인 이진 탐색에 대해서 읽어보셨다면, 금방 답을 찾으셨으리라 생각합니다. 우리도 그렇고, 컴퓨터도 그렇고, 이미 정렬된 데이터에 대해서 작업을 하는 것이 더 효율적입니다.
정렬되지 않은 데이터는 선형 탐색만 사용할 수 있습니다. 선형 탐색의 경우 O(n)의 시간이 소요됩니다. 하지만 이진 탐색을 사용한다면 O(logn)의 시간이 소요됩니다. 이미 정렬되어 있다면, 탐색을 더 효율적으로 할 수 있습니다. 이진 탐색은 매우 간단하지만 효과적인 탐색이기 때문에 알고리즘을 풀이할 때에도 개선의 여지가 없는 경우 정렬을 하는 방식이 더 효과적이기도 합니다.
구현
class SelectionSort {
public void sort(int[] arr) {
int length = arr.length;
for (int i = 0; i < length - 1; i++) { // 두 개를 비교해서 정렬하므로 마지막 요소는 확인X
int minIndex = i;
for (int j = i + 1; j < length; j++) { // 이미 정렬되어 있는 항목을 확인하지 않기 위한 튜닝
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// swap하는 부분 (자바에서는 primitive type은 call by value여서 메소드화 하기 까다롭다.)
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}감사합니다.
