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

여러가지 정렬 알고리즘 중 하나인

선택정렬 알고리즘!

 

간단히 설명하면

 

맨 앞에서부터 하나의 원소를 고정한 후,

그 뒤에 원소들과 비교해서

고정된 원소보다 작으면서 가장 작은 원소와 위치를 바꿔준다.

 

예를 들어

 

5 4 3 2 1

배열을 sort할 경우

 

고정원소는 5이고, 

4 3 2 1 중 가장 작은 원소는 1이므로

1 4 3 2 5 가 된다.

 

다음으로

고정원소는 4이고,

3 2 5중 가장 작은 원소는 2이므로

1 2 3 4 5 가 된다.

 

이런 방식으로 문자열 길이만큼 돌면 된다.

 

 

선택정렬은 

이중 for문 / 재귀 

두 가지 방식으로 구현할 수 있다.

 

 

1. 이중 for문

def selectionSort(lst):
    for i in range(len(lst)):
        target = i
        for j in range(i+1, len(lst)):
            if lst[target] > lst[j]:
                target = j
        lst[i], lst[target] = lst[target], lst[i]

    return lst

 

 

2. 재귀

def recurSelectionSort(target, lst):
    if target == len(lst)-1:
        return
    min_idx = target
    for i in range(target+1, len(lst)):
        if lst[min_idx] > lst[i]:
            min_idx = i
    lst[min_idx], lst[target] = lst[target], lst[min_idx]
    return lst

 

둘 다 O(n^2)만큼 돌지만

함수호출을 할 경우

시간이 더 걸리기 때문에

이중for문으로 사용하는게 나을 것 같다!