1. 선택 정렬

선택 정렬은 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

즉, 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 2번째 데이터와 바꾸는 과정을 반복한다.

2. 선택 정렬의 장단점

장점

• 선택정렬 또한 버블정렬과 마찬가지로 구현이 쉬운편에 속하는 정렬법이다.

• 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 효율적으로

  사용될 수 있다.

• 버블정렬과 비교했을 때, 똑같이 O(N^2)이라는 시간복잡도를 갖지만, 실제로 시간을 측정해보면

  버블정렬에 비해서는 조금 더 빠른 정렬 방식이다.

단점

• 선택정렬 또한 항상 O(N^2)이라는 시간복잡도를 갖기 때문에 시간이 오래걸리는 정렬 방식이다.

3. 선택 정렬 구현

구현

# 선택 정렬을 사용하여 오름차순 정렬
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
    min_idx = i  # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(arr)):
        if arr[min_idx] > arr[j]:
            min_idx = j
    temp = arr[min_idx]
    arr[min_idx] = arr[i]
    arr[i] = temp

print(arr)

>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간복잡도

시간 복잡도는 O(N^2)이다.

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 그리고 구현 방식에 따라서 사소한 오차는 있을 수 있으나, 전체 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2이다.
이는 (N² + N - 2) / 2로 표현할 수 있는데, 이는 빅오 표기법으로 간단히 O(N^2)이다.

최선 O(n^2)
최악 O(n^2)
평균 O(n^2)

참고문헌

https://yabmoons.tistory.com/250
https://overcome-the-limits.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%EB%A6%84-%EB%AC%B8%EC%A0%9C1I-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-with-nodejs
https://velog.io/@kimdukbae/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Sorting-Algorithm