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

선택 정렬 🏅

선택 정렬은 가장 작은(또는 가장 큰) 값을 선택하여 맨 앞부터 차례대로 위치를 확정하는 정렬 알고리즘이다. 배열 내에서 가장 작은 값을 찾아서 첫 번째 자리로 이동, 그 다음으로 작은 값을 찾아 두 번째 자리로 이동하는 식으로 동작한다.

---

선택 정렬 원리

선택 정렬의 핵심 동작은 다음과 같다.

1. 현재 인덱스부터 배열의 끝까지 순회하여 가장 작은 값을 찾는다.
2. 그 값을 현재 인덱스의 값과 교환한다.
3. 다음 인덱스로 이동하여 같은 과정을 반복한다.

---

예시

초기 배열:

6	4	3	9	7

1번째 패스:

• (6, 4, 3, 9, 7) 중 가장 작은 값 3 → 첫 번째 자리와 교환
  | 3 | 4 | 6 | 9 | 7 |

2번째 패스:

• (4, 6, 9, 7) 중 가장 작은 값 4 → 두 번째 자리 유지
  | 3 | 4 | 6 | 9 | 7 |

3번째 패스:

• (6, 9, 7) 중 가장 작은 값 6 → 그대로
  | 3 | 4 | 6 | 9 | 7 |

4번째 패스:

• (9, 7) 중 가장 작은 값 7 → 교환
  | 3 | 4 | 6 | 7 | 9 |

→ 정렬 완료!

---

특징 및 시간 복잡도

• 비교는 항상 n(n-1)/2번 수행
• 교환 횟수는 O(n)으로 적음
• 시간 복잡도: O(n²)
• in-place 정렬이며 불안정 정렬
  (동일한 값의 순서가 보장되지 않음)

---

선택 정렬 장단점

장점

• 구현이 간단하다.
• 교환 횟수가 최대 n-1번으로 적다.

  ✅ 버블 정렬과의 차이점
  버블 정렬과 원리는 대체적으로 비슷하지만, 교환 방식에서 큰 차이가 있다.

  ---

  • 버블 정렬은 최솟값을 원소 하나하나 비교 & 교환을 반복하여 큰 값을 오른쪽 끝으로 보내는 방식.
    → 즉, 한 패스 안에서도 여러 번의 교환 (O(n)) 이 발생할 수 있다.
  • 하지만 선택 정렬은 한 패스에서 가장 작은 값(최솟값)을 먼저 찾고, 그 값을 한 번만 현재 위치와 교환한다.
    → 그래서 한 패스당 교환 횟수는 최대 1번 (O(1)) 으로 제한됩니다.

단점

• 항상 O(n²)의 비교가 필요.
• 데이터가 거의 정렬된 경우에도 비효율적.
• 실무에서는 거의 사용하지 않음 (학습용으로 적합)

---

선택 정렬 파이썬 코드

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 사용 예시
arr = [6, 4, 3, 9, 7]
sorted_arr = selection_sort(arr)
print(sorted_arr)  # 출력: [3, 4, 6, 7, 9]

---