[문법] 선택 정렬(selection sort) 개념 및 구현(Python)

선택 정렬이란?

제자리 정렬(in-place sorting) 알고리즘의 하나
- 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

• 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

 

특징

• 장점
  - 자료 이동 횟수가 미리 결정된다.
• 단점
  - 안정성을 만족하지 않는다.
  - 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

시간복잡도

• 비교 횟수
  - 두 개의 for 루프의 실행 횟수
  - 외부 루프: (n-1)번
  - 내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
• 교환 횟수
  - 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
  - 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번
• T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

 

구현 (Python)

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst