[알고리즘] 선택 정렬

 알고리즘, 자료구조 - 선택 정렬 

 

 

선택 정렬이란?

 

리스트 안의 원소들 중 최솟값을 찾아 리스트의 앞쪽으로 보내고, 그 뒤에 남은 원소들에 대해서 반복적으로 최솟값을 찾아 정렬하는 알고리즘이다. 간단한 알고리즘이지만 성능면에서는 느리기 때문에 좋지 않은 방식이다.

 

- 선택 정렬 알고리즘의 구체적인 개념

1. 첫 번째 원소를 선택, 그 뒤의 원소들과 차례대로 비교해 최솟값을 찾는다.

2. 찾은 최솟값을 첫 번째로 옮긴다.

3. 두 번째 원소를 선택, 3번째 원소부터 끝까지 비교해 최솟값을 찾는다.

4. 위의 과정들을 계속 반복한다.

 

위의 알고리즘 방식을 보면 코드상에서 2개의 반복문이 필요하고 이는 시간 복잡도 면에서 O(n^2)의 시간이 걸린다.

 

- 시간 복잡도

0번 요소: (n-1) 번 비교

1번 요소: (n-2) 번 비교

 ...

n-2번 요소: 1번 비교

n-1번 요소: 0번 비교

 

전체 비교 횟수는 0+1+2+3+...+n-2+n-1 = (n-1)(n-1+1) / 2 가 된다. n의 수가 커지면 결국 n^2이 큰 영향을 가지고 나머지는 무시할 수 있다. 따라서 시간 복잡도는 O(n^2)가 된다. 

 

<출처: 위키피디아>

 

예제

def select_sort(li):
    n = len(li)

    for i in range(0, n-1): #0번째~n-2번(뒤에서 2번째)
        min_idk = i
        for j in range(i+1, n): #비교하려는 값 뒤부터 끝까지 비교
            if(li[j] < li[min_idk]): # 비교하려는 값보다 뒤에 값이 작다면
                min_idk = j 		 
        li[i], li[min_idk] = li[min_idk], li[i] # 최솟값 위치 변경 

    return li


print(select_sort([2, 4, 5, 1, 3])) # [1, 2, 3, 4, 5]