Selection Algorithm & Selection Sort (셀렉션 알고리즘, 선택 정렬)

설명

• 저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소를 찾는 방법
  • 최소값, 최대값, 중간값 등을 찾는 알고리즘을 의미하기도 함
• 선택 과정
  • 셀렉션은 아래와 같은 과정으로 구성
    1. 정렬 알고리즘을 이용하여 자료 정렬
    2. 원하는 순서에 있는 원소 선택
• k번째로 작은 원소를 찾을 때,
  • 1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동, 배열의 k번째를 반환
• 시간 복잡도: O(kn) - k가 비교적 작을 때 유용
• 예시

def select(list, k):
    for i in range(0, k):
        minIndex = i
        for j in range(i+1, len(list)):
            if list[minIndex] > list[j]:
            	minIndex = j
        list[i], list[minIndex] = list[minIndex], list[i]
    return list[k-1]

 

선택 정렬 (Selection Sort)

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
  • 앞서 살펴본 셀렉션 알고리즘을 전체 자료에 적용
• 정렬 과정
  • 주어진 리스트 중에서 최소값을 탐색
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환
  • 맨 처음 위치를 제외한 나머지 리시트를 대상으로 위의 과정을 반복
• 시간 복잡도: O(n^2)

미정렬원소가 하나 남지만, 마지막 원소가 가장 큰 값을 갖게 되므로, 실행을 종료하고 선택 정렬이 완료

 

• 예시 (셀렉션 알고리즘과 거의 비슷함)

def selectionSort(_list):
    for i in range(len(_list)-1):
        min_index = i

        for j in range(i+1, len(_list)):
            if _list[min_index] > _list[j]:
                min_index = j

        _list[i], _list[min_index] = _list[min_index], _list[i]
    return _list