🥕 Selection Sort(선택 정렬)

선택 정렬은 배열에서 가장 작은 값을 선택하고 그 값을 배열의 맨 앞으로 이동시키는 과정을 반복하여 정렬을 수행하는 방법이다.

num_list = [0, 7, 5, 2, 8, 6, 1, 10, 3]

for idx in range(len(num_list)-1):
    min_idx = idx
    for j in range(idx+1, len(num_list)):
        if num_list[j] < num_list[min_idx]:
            min_idx = j
    if idx != min_idx:
        num_list[idx], num_list[min_idx] = num_list[min_idx], num_list[idx]

print(num_list)

선택 정렬은 가장 작은 값을 선택해 배열의 앞쪽부터 정렬해가는 방식을 수행한다. 파이썬으로 구현한다면 위와 같이 구현할 수 있으며, 배열의 첫번째 요소부터 시작해 가장 작은 값을 찾아서 배열의 맨 앞으로 보낸식의 코드이다. for문을 이용하여 배열의 인덱스를 하나씩 순회하며 현재 인덱스부터 배열의 끝까지 중 가장 작은 값을 찾아서 현재 위치로 이동시키는 과정을 반복한다.

버블정렬과 선택 정렬과의 차이는 버블 정렬은 첫번째 요소와 두번째 요소를 비교하여 큰값을 뒤로 보내는 형식으로 구현되어 있는 반면에 선택 정렬은 배열에서 가장 작은 최솟값을 찾아 첫번째 요소와 교환하는 식으로 구현되어 있다.

장점

• 구현이 간단하고 이해하기 쉽다
• 제자리 정렬로 추가 메모리가 필요하지 않음
• 데이터 이동 횟수가 미리 결정되어 있어 안정성이 높음

단점

• 평균적인 시간복잡도가 $O(n^2)$이므로 데이터가 많을수록 느려짐
• 입력 데이터의 초기 순서에 따라 성능이 크게 좌우됨
• 비교적 큰 데이터 셋에 대해 효율적이지 않음