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

• 선택 정렬 (Selection Sort) 이란?
  • 자신의 뒤에 속하는 원소들과 순차적인 비교를 통해 자리를 교환하여 정렬하는 알고리즘
    • 비교 정렬에 속함
  • 선택 정렬 특징
    • 버블 정렬과 방식이 비슷하며 구현이 쉬움
    • 잦은 비교와 교환으로 성능이 나쁨
  • 선택 정렬 알고리즘 시간 복잡도
    • 최악, 최선, 평균 – O(N²)
    • 참고 – 각 정렬 알고리즘의 시간복잡도

• 예제 – 선택 정렬 (오름차순)

# Python Code

arr = [3,1,6,0,1,9,4]
N = len(arr)

for i in range(N-1):
    for j in range(i+1, N):
        if arr[i] > arr[j]:
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp

print(arr)
# [0, 1, 1, 3, 4, 6, 9]

• 과정 – 오름차순

첫 번째 배열부터 뒤에 속하는 배열과 순차적으로 값을 비교합니다.

1회전과 마찬가지로 (배열의 수 – 1) 회전까지 진행하면 아래와 같은 배열이 완성됩니다.

이상으로 선택 정렬에 대한 설명을 마칩니다! 😀