알고리즘 | 선택 정렬

✔ 학습목표

선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다.

 

선택 정렬

선태 정렬(selection sort)은 버블 정렬과 마찬가지로 정렬을 위한 알고리즘 중 하나이다. 선택 정렬에서는 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환한다. 넣을 위치는 이미 정해져있고, 어떤 수를 넣을지 선택한다는 게 특징이다.

 

선택 정렬은 아래와 같은 의사 코드로 나타낼 수 있다.

 

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

 

이해를 위해 간단한 GIF를 보자.

 

 

선택 정렬은 버블 정렬과 달리 교환 횟수가 적은 반면 각 자료를 비교하는 횟수는 많다. 이는 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적이다. 또 버블 정렬과 마찬가지로 같은 배열 내에서 교환이 일어나기 때문에 다른 메모리 공간을 필요로 하지 않는다. 이런 정렬을 제자리 정렬(in-place sorting)이라 한다.

 

효율성

선택 정렬도 코드로 구현하면 중첩 루프를 돈다. 데이터의 개수가 n 개라고 했을 때, 1에서 (n-1)까지, 2에서 (n-1)까지 하나하나 비교하고 교환하면 (n-1) + (n-2) +.... + 2 + 1 = n(n-1)/2이라는 값이 나온다.

 

표기법으로 나타내면 시간복잡도의 상한은 O(n^2)이다. 배열 전체를 비교하지 않고서는 가장 작은(혹은 큰) 수라고 확신할 수 없기에 하한도 역시 Ω(n^2)이다. 주어진 배열 안에서 교환을 통해 정렬하기 때문에 공간 복잡도는 O(n)이다.

 

 

 

 

참고 자료

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview

정렬 알고리즘 6개 정리

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)