[이코테_코딩테스트] 정렬 알고리즘 - 선택 정렬 (Selection Sort)

date

Jul 25, 2023

slug

coding-test-selection-sort

author

status

Public

tags

Python

코딩테스트

summary

선택 정렬을 알아보자

type

Post

thumbnail

category

💻코딩테스트

updatedAt

Jul 26, 2023 07:19 AM

정렬 알고리즘

• 정렬?
• 데이터를 특정한 기준에 따라 순서대로 나열하는 것

• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

선택 정렬 (Selection Sort)

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

• 매번 가장 작은 원소 찾기 위해 탐색 범위만큼 데이터를 하나씩 확인해야 함 → 매번 선형 탐색 하는 것과 동일
• 이중 반복문을 통해 선택 정렬 구현 가능

선택 정렬 동작 예시

[Step 0] 처리되지 않은 데이터 중 가장 작은 ‘0’을 선택해 가장 앞의 ‘7’과 바꾼다.

[Step 1] 처리되지 않은 데이터 중 가장 작은 ‘1’을 선택해 가장 앞의 ‘5’와 바꾼다.

[Step 2] 처리되지 않은 데이터 중 가장 작은 ‘2’를 선택해 가장 앞의 ‘9’와 바꾼다.

[Step 3] 처리되지 않은 데이터 중 가장 작은 ‘3’을 선택해 가장 앞의 ‘7’과 바꾼다.

[Step N] 위 과정을 반복하면 다음과 같이 정렬이 완료된다.

• 마지막 위치(’9’)는 자신의 위치와 동일하기 때문에 마지막 위치는 처리하지 않아도 된다.

선택 정렬 소스코드 (Python)

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

for i in range(len(array)):
    min_index = i
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array)

선택 정렬의 시간 복잡도

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다.

• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.

• 이는 로 표현할 수 있는데, 빅오 표기법에 따라 이라고 작성한다.

이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 4. 정렬 알고리즘” 영상을 보고 작성하였습니다.