선택 정렬(Selection Sort)

dion·2020년 3월 11일
1

알고리즘

목록 보기
5/7

참고

선택 정렬의 아이디어는 아주 간단합니다. 숫자를 큰 순서대로 마지막부터 바꾸거나, 혹은 작은 순서대로 처음부터 바꾸는 것입니다. 즉 모든 항목을 서로 비교합니다. 모든 항목을 비교하니 (모든 항목 x 모든 항목)으로 O(n2)이 걸리게 됩니다.

물론 어느정도 튜닝(이미 정렬된 항목은 확인하지 않도록)을 해준다면, 속도가 조금은 빨라질 수 있습니다. 하지만, 빅 오 표기법에서 상수항은 무시합니다. 따라서 이 속도가 조금 빨라지는 것은 시간복잡도를 계산하는 것에 영향을 주지 않습니다.

공간복잡도는 이미 존재하는 배열 내부에서 정렬을 하는 것이므로 O(1)입니다.

선택 정렬을 왜 배울까요?

보시다시피 O(n2) 은 굉장히 시간의 소요가 많다는 것을 알 수 있습니다. 그런데 왜 우리는 선택 정렬을 배울까요?

우리는 남이 작성한 정렬 알고리즘을 이용할 수도 있지만, 문제에 대한 다양한 접근 방법이 있을 수 있다는 것을 공부하고자 선택정렬을 배운다고 생각합니다.

정렬을 하는데에는 훌륭한 알고리즘도 많습니다. 하지만 이들 알고리즘과 선택 정렬이 추구하는 바는 같습니다. 주어진 항목들을 정렬하는 것이죠. 단지 그 방법이 다를 뿐입니다.

정렬은 왜 할까요?

더 본질적인 질문입니다. 왜 우리는 정렬을 해야할까요? 이전에 쓴 글인 이진 탐색에 대해서 읽어보셨다면, 금방 답을 찾으셨으리라 생각합니다. 우리도 그렇고, 컴퓨터도 그렇고, 이미 정렬된 데이터에 대해서 작업을 하는 것이 더 효율적입니다.

정렬되지 않은 데이터는 선형 탐색만 사용할 수 있습니다. 선형 탐색의 경우 O(n)의 시간이 소요됩니다. 하지만 이진 탐색을 사용한다면 O(logn)의 시간이 소요됩니다. 이미 정렬되어 있다면, 탐색을 더 효율적으로 할 수 있습니다. 이진 탐색은 매우 간단하지만 효과적인 탐색이기 때문에 알고리즘을 풀이할 때에도 개선의 여지가 없는 경우 정렬을 하는 방식이 더 효과적이기도 합니다.

구현

감사합니다.

profile
더 나은 나를 위해 노력하는 개발자입니다. @Code-Squad

0개의 댓글