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

선택정렬(Selection Sort)란?

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
1. 주어진 데이터 중, 최소값을 찾는다.
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다.
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

 

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

1. 첫 번째 반복문 루프는 데이터의 마지막이 자동으로 정렬되기 때문에 데이터의 수 -1로 정해준다.
2. 최소값의 index를 저장할 수 있도록 변수를 선언해준다.
3. 두 번째 반복문은 정렬된 인덱스 다음번부터 시작하면 된다.
4. 차례대로 데이터 값을 비교하며 인덱스값을 알맞게 바꿔준다.

def selection_sort(data):
    for index in range(len(data) - 1):
        min_index = index
        for index2 in range(index+1, len(data)): # index+1은 min_index와 index2를 비교할 때
            if data[min_index] > data[index2]:   # +1을 하지않으면 자기자신을 비교하여 불필요한 부분을 제거
                min_index = index2
        data[index], data[min_index] = data[min_index], data[index]
    return data

 

선택 정렬(Selection Sort) 알고리즘 시간 복잡도

• 선택정렬 알고리즘에는 for문이 두 개 들어가니까 시간복잡도는 O(n^2)
• 실제로 상세하게 계산하면 𝑛∗(𝑛−1)/2이 된다.