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

선택 정렬(Selection Sort)

• 정렬되지 않은 리스트에서 매번 가장 큰(또는 작은) 요소를 선택하여 끝자리와 교환하는 방식을 반복하는 알고리즘
• 시간 복잡도는 O(n^2)로, 작은 데이터셋에 적합하지만 큰 데이터셋에서는 비효율적이다.

 

동작 원리

1. 초기 리스트가 주어졌을 때, 리스트의 처음부터 끝까지 순회하며 최댓값(또는 최소값)을 찾는다.
2. 최댓값(또는 최솟값)을 리스트의 마지막 요소와 교환한다.
3. 남은 리스트에서 위 과정을 반복하여 정렬을 완료한다.

 

단계별 구현

1. 리스트의 마지막 요소부터 첫 번째 요소까지 역순으로 반복
2. 각 반복에서 리스트의 첫 번째 요소부터 현재 반복 요소까지 순회하여 최댓값을 찾기
3. 최댓값을 현재 반복 요소와 교환
4. 리스트가 정렬될 때까지 위 과정을 반복

 

Python 파이썬 코드:

def selectionSort(lst: list) -> list:
    
    length = len(lst) # 길이 구하기

    for last in range(length-1, 0, -1):

        max_idx = 0 # 최댓값 위치, 초기화

        # 남은 리스트에서 최댓값 위치 찾기
        for idx in range(1, last+1):
            if(lst[idx] > lst[max_idx]):
                max_idx = idx

        # 최댓값을 남은 리스트의 마지막 위치로 이동
        lst[max_idx], lst[last] = lst[last], lst[max_idx]

    return lst

def selectionSort(lst: list) -> list:

   

    length = len(lst) # 길이 구하기

    for last in range(length-1, 0, -1):

        max_idx = 0 # 최댓값 위치, 초기화

        # 남은 리스트에서 최댓값 위치 찾기

        for idx in range(1, last+1):

            if(lst[idx] > lst[max_idx]):

                max_idx = idx

        # 최댓값을 남은 리스트의 마지막 위치로 이동

        lst[max_idx], lst[last] = lst[last], lst[max_idx]

    return lst

 

장단점

장점:

• 구현이 직관적이다?.
• 데이터 이동 횟수가 적어 메모리 이동 비용이 낮다.

 

단점:

• 시간 복잡도가 O(n^2)로, 데이터가 커질수록 비효율적이다.
• 안정적인 정렬이 아니다. -> 동일한 값을 가지는 요소들의 상대적인 순서가 변경될 수 있다.