알고리즘 2 [선택정렬, selection sort]

2. 선택 정렬(selection sort)

 

이미지 출처: Marco Polo at wikipedia.org, originally uploaded at en.wikipedia.org with same filename (log), https://commons.wikimedia.org/w/index.php?curid=6503932

 

선택정렬이란?
가장 작은 데이터를 찾아 가장 앞으로 교환하는 방식

---

e.g.) 오름차순 선택 정렬

1. 첫번째 인덱스부터 마지막 인덱스 사이에서 가장 작은 값을 찾아 맨앞으로 보냄.
2. 두번째 인덱스부터 마지막 인덱스 사이에서 가장 작은 값을 찾아 두번째로 보냄.
... 반복

---

[ 장점 ] 
- 버블정렬과 마찬가지로 메모리 소비가 작음

[ 단점 ]
- 버블정렬과 마찬가지로 시간 소비가 비효율적임

---

시간 복잡도 : O(n^2)
공간 복잡도 : O(1)

비효율적이지만 직관적임(안정적이지 못함)

 

-> 선택정렬의 최적화
-> 최솟값과 최댓값을 같이 찾는 이중 선택정렬, 
-> 동일한 값이 있을 경우 함께 정렬하는 방법 등이 있다.

 

> 시간복잡도와 공간복잡도란?
깊이 들어가면 너무나도 복잡하기 때문에 대강 개념만 정리.
- 시간복잡도 : 문제를 해결하는데 걸리는 시간
- 공간복잡도 : 문제를 해결하는데 필요한 자원 공간
-> 둘 다 낮을 수록 좋은 것!