[알고리즘] 정렬 : 선택정렬

선택 정렬은 오름차순 기준일 때 범위 내에서 최솟값을 찾아 앞자리의 숫자와 자리를 변경해 나간다. 최솟값 또는 최댓값을 선택한다는 의미로 선택 정렬이라는 이름이 붙었다.

---

개념

• 오름차순 기준으로 설명한다.
• N개의 원소가 있을 때 0~N-1까지 탐색을 진행하여 최솟값을 찾는다.
• 찾은 최솟값과 0번째 인덱스에 있는 숫자와 스왑을 한다.
• 위의 과정을 통해 첫 번째 자리는 정렬이 된 것이다.
• 이후 1~N-1까지 탐색을 진행하여 최솟값을 찾고 1번째 인덱스에 있는 숫자와 스왑을 한다.
• 위의 과정을 반복하여 정렬을 한다.

구현

• 10개의 숫자가 랜덤하게 나열되어 있다.
• 첫 번째 for문의 i인덱스는 최솟값을 찾아서 해당 인덱스와 i 인덱스와 자리를 변경할 때 사용된다.
• 두 번째 for문은 i인덱스부터 탐색을 진행한다. i 이전의 원소들은 이미 정렬되어 있다.
• 두 번째 for문을 통해 최솟값을 찾고 해당 인덱스를 min_idx에 저장한다.
• 이제 min_idx(최솟값이 있는 인덱스)와 i(정렬해야 할 인덱스)와 변경한다.

N = 10
numbers = [3, 1, 10, 6, 4, 7, 8, 2, 5, 9]

for i in range(N-1):
    min_idx = i
    for j in range(i, N):
        # 최솟값을 찾는다.
        if numbers[min_idx] > numbers[j]:
            min_idx = j
    # 찾은 최솟값의 인덱스와 i의 자리를 변경한다.
    numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]

print(*numbers)

 

특징

- 역순 정렬할 때 효과적이다. (내림차순 되어있는 것을 오름차순으로 정렬할 때)

 

장점

- 정렬해야 하는 데이터의 양이 적을 때 좋은 성능을 나타낸다.

- 교환횟수가 적다.

 

단점

- 정렬해야 하는 데이터의 양이 많을 때는 성능이 급격하게 떨어진다.

 

시간 복잡도

두 번의 for문을 사용하여 탐색이 진행되기 때문에 최선, 최악, 평균의 경우 모두 O(N^2)의 시간 복잡도를 갖는다.