[Python] 선택 정렬 (Selection Sort)

가장 작은 것을 선택해서 제일 앞으로 보낸다.

다음 10개의 수를 오름 차순으로 정렬해보자

1 10 5 8 7 6 4 3 2 9

가장 작은 숫자 1은 가장 앞쪽에 있으니 정렬이 된 것

 

1 10 5 8 7 6 4 3 2 9 -> 1 2 5 8 7 6 4 3 10 9

1을 제외하고 나머지 중에서 가장 작은 숫자 2를 가장 앞에 있는 10과 바꾼다.

 

1 2 5 8 7 6 4 3 10 9 -> 1 2 3 8 7 6 4 5 10 9

그 다음 가장 작은 숫자 3을 가장 앞의 숫자 5와 바꾼다.

 

이런 식으로 정렬을 하는 것이 선택정렬

 

 

 

파이썬 코드

# 선택정렬 (Selection Sort)

# i와 j는 배열에 원소들을 반복적으로 탐색하기 위해 사용
# min 최소값 의미
# index 가장 작은 원소가 존재하는 위치
# temp 원소 교환을 위해 사용하는 임시변수

def selection_sort(arr):
    
    # for문 배열의 길이 만큼 반복 (0부터 리스트 길이 미만)
    for i in range(len(arr)):
        min = 9999
        
        # for문 최소값 찾기 (i부터 배열의 길이 미만)
        for j in range(i, len(arr)):
            # 두개의 값을 비교해서 min이 크면 min에 arr[j]값을 넣어준후 index를 j로 변경
            if min > arr[j]:
                min = arr[j]
                index = j
        
        # 두개의 값 바꾸기
        temp = arr[i]
        arr[i] = arr[index]
        arr[index] = temp
    
    return arr
                

test = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
print("선택 정렬된 데이터 : {}".format(selection_sort(test)))

 

 

 

시간 복잡도

처음에 1~10까지 확인

그 다음에는 2~10까지 확인

그 다음에는 3~10까지 확인 

 

10 + 9 + 8 + ... + 1

n * (n+1) / 2 

n의 제곱

O(n*n)

 

선택정렬은 다른 정렬과 비교했을 때 비효율적인 알고리즘이다.

데이터가 커질수록 매우 많은 연산을 처리해야하기 때문에 시간이 많이 걸린다.