선택 정렬
Selection Sort
index를 저장한 뒤 index에 어떤 값을 넣을지 비교한 후 선택하는 정렬 알고리즘
값을 먼저 고른 뒤 값이 들어갈 자리를 찾는 삽입 정렬과 달리, 선택 정렬은 자리를 먼저 고르고 그 자리에 들어갈 값을 찾는 방법이다.
Process
1.
우선, 위치(index)를 선택해줍니다.
2.
i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작합니다.
3.
오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해줍니다.
4.
'2'번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택한 위치(index)에 들어가야하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해줍니다.
python
def selection_sort(x):
for size in range(len(x) - 1):
min_i = size
for i in range(size + 1, len(x)):
if x[min_i] > x[i]:
min_i = i
x[i], x[min_i] = x[min_i], x[i]
Python
복사
•
n개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아니라 비교하고 있는 값의 index를 저장해둔다. 그리고 최종적으로 한번만 바꿔준다.
•
시간복잡도 : O()
•
공간복잡도 : O()
장점
•
알고리즘이 단순
•
정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적
•
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 → 제자리 정렬(in-place sorting)
단점
•
최선, 평균, 최악의 시간복잡도가 O()으로 비효율적
•
불안정 정렬(Unstable Sort)