[알고리즘] 선택 정렬 (Selection Sort)

이번에 공부할 내용은 선택 정렬(Selection Sort)이다.

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

선택 정렬(Selection Sort)은 수열에서 최솟값을 찾아서 가장 왼쪽의 숫자와 교체하는 작업을 반복하여 정렬한다.

수열에서 최소값을 찾을 때는 선형 탐색을 사용한다.

[알고리즘] 선형 탐색 (Linear Search)

 

선택 정렬

1부터 9까지의 수열을 선택정렬로 정렬해 보겠다.

 

선택 정렬

수열을 선형 탐색하여 최솟값인 1을 찾는다.

 

선택 정렬

최솟값인 1을 가장 왼쪽에 있던 2와 교체하여 1의 정렬을 마친다. 이렇게 1라운드가 종료 된다.

참고로 최솟값이 이미 가장 왼쪽에 있다면 아무런 작업을 하지 않는다.

 

선택 정렬

다음 최솟값인 2를 선형 탐색으로 찾는다.

 

선택 정렬

2를 왼쪽에서 두번째에 있던 7과 교체하여 1과 2의 정렬을 마친다. 2라운드가 종료되었다.

 

선택 정렬

모든 숫자가 정렬을 마칠 때 까지 같은 작업을 반복해 준다.

 

선택 정렬

총 5라운드만에 정렬이 완료되었다.

 

 

---

⏱️ 시간복잡도

선택 정렬은 선형 탐색을 위해 1라운드에서 n-1회, 2라운드에서 n-2회, ..., n-1회에서 1회 비교한다.

따라서 비교횟수는 버블 정렬과 같은 n²/2 다.

 

또한, 숫자 교체는 각 라운드에서 최대 1회(0회 혹은 1회)고 입력 데이터가 이미 작은 순으로 나열되어 있다면 교체는 한버도 발생하지 않는다.

선택 정렬의 시간 복잡도는 버블 정렬과 마찬가지로 O(n²)이다.

 

📌 추가 내용

버블정렬 vs 선택정렬

버블 정렬과 선택 정렬은 동일한 시간 복잡도를 가지고 있지만 성능면에서는 선택 정렬이 뛰어나다.

버블정렬은 자리 이동을 할때마다 계산해줘야 하기 때문이다.

 

버블 정렬은 잘 사용되지 않는 알고리즘이다.

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠

[자료구조] 선택정렬과 버블정렬 정의 및 차이 : 카멜레온 개발자 이야기 https://jcurveworld.tistory.com/25

[알고리즘] 버블 정렬(bubble sort)이란 : Heee's Development Blog https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html