선택 정렬

선택 정렬 (Selection Sort)

💡 선택 정렬(Selection Sort)은 배열 내에서 가장 작은(또는 가장 큰) 원소를 찾아 맨 앞의 원소와 교환하는 방식을 사용하는 정렬 알고리즘입니다.

작동 원리

http://algorithm.wiki/ko/app/

1. 배열에서 현재 위치를 제외한 나머지 원소 중에서 가장 작은 원소를 찾는다.
2. 찾아진 가장 작은 원소와 현재 위치의 원소를 교환한다.
3. 현재 위치를 한 칸 앞으로 이동하고, 배열의 끝까지 위의 과정을 반복한다.

시간 복잡도

• 최선의 경우: O(n2)
• 평균적인 경우: O(n2)
• 최악의 경우: O(n2)

공간 복잡도

• O(1) (in-place 정렬)

장단점

• 장점
  • 구현이 간단하며, 공간 복잡도가 작다. 데이터의 양이 작을 때는 효율적일 수 있다.
• 단점
  • 데이터의 양이 많아지면 시간 복잡도가 크기 때문에 비효율적이다. 안정성(stable)을 보장하지 않는다.
  • 5(a) 2 3 8 4 5(b) 6 > 2 3 4 5(b) 5(a) 6 8

구현

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