알고리즘 | 선택 정렬 (Selection Sort)

진탱이·2021년 11월 28일
0

Algorithm

목록 보기
4/7

선택 정렬 (Selection Sort)

1. 개요

제자리 정렬 알고리즘 중 하나로, 입력 데이터 이외에 다른 추가 메모리를 요구하지 않는다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 주어진 리스트 중에서 최소값을 먼저 찾고, 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트들을 같은 방법으로 끝까지 교체한다.

2. 예시

3. 시간복잡도

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n^2)

4. 코드 (Python)

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
profile
개발자가 하고 싶은 대학생

0개의 댓글