선택 정렬(Selection Sort)이란 무엇인가?

선택 정렬은 데이터를 정렬하기 위한 간단하고 직관적인 알고리즘이며,

입력 배열을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누어 작동합니다. 

 

작동 방식을 알아보겠습니다.

1. 최솟값(또는 최댓값) 찾기
   • 정렬되지 않은 부분에서 가장 작은(혹은 가장 큰) 요소를 찾습니다.
2. 교체
   • 찾은 최솟값(혹은 최댓값)을 정렬되지 않은 부분의 첫 번째 요소와 교체합니다.
3. 경계 이동
   • 정렬된 부분의 경계를 오른쪽으로 한 위치 이동합니다.
4. 반복
   • 배열이 완전히 정렬될 때까지 1~3단계를 반복합니다.

 

예를 들어, 배열 [7, 5, 6, 4, 9, 2]를 오름차순으로 정렬하는 경우:

• 첫 번째 반복: 최솟값 2를 찾고, 첫 번째 요소 7과 교체합니다. → [2, 5, 6, 4, 9, 7]
• 두 번째 반복: 최소값 4를 찾고, 두 번째 요소 5와 교체합니다. → [2, 4, 6, 5, 9, 7]
• 세 번째 반복: 최소값 5를 찾고, 세 번째 요소 6과 교체합니다. → [2, 4, 5, 6, 9, 7]
• 네 번째 반복: 최소값 6을 찾고, 네 번째 요소 6과 교체합니다(변화 없음). → [2, 4, 5, 6, 9, 7]
• 다섯 번째 반복: 최소값 7을 찾고, 다섯 번째 요소 9와 교체합니다. → [2, 4, 5, 6, 7, 9]
• 여섯 번째 반복: 마지막 요소만 남았으므로 종료합니다. 최종 결과는 [2, 4, 5, 6, 7, 9]입니다.

이 예시에서 외부 루프는 5번 반복됩니다(len(arr)-1번, 여기서 len(arr)=6).

마지막 요소는 자동으로 정렬된 위치에 놓이게 되므로 추가적인 비교나 교환이 필요하지 않습니다.

 

선택 정렬의 장점은 뭐가 있을까요? 선택 정렬의 장점은 알고리즘의 단순성 및 교환 횟수의 효율입니다.

다시 말해, 선택 정렬의 알고리즘은 매우 간단하여 이해하고 구현하기 쉽습니다.

 

다만 단점으로는, 시간 복잡도가 버블 정렬과 같은 O(n^2)입니다. 이는 두 개의 중첩된 반복문이 있기 때문입니다. 첫 번째 반복문은 배열의 각 요소에 대해 실행되고, 두 번째 반복문은 남은 요소들에 대해 실행되므로, 데이터 수가 증가할수록 처리 시간이 급격히 늘어납니다. 

 

아래는 선택 정렬을 파이썬으로 구현한 코드입니다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

 

코드를 한 번 분석해 보겠습니다.

 

1. 함수 정의 및 입력

   def selection_sort(arr):

    
   • ‘ selection_sort ’라는 이름의 함수를 정의합니다. 이 함수는 하나의 매개변수 ‘ arr ’를 받으며, 이는 정렬할 배열입니다. 
2. 배열 길이 계산

       n = len(arr)

    
   • ‘ len(arr) ’ 함수를 사용하여 배열의 길이를 구하고, 이를 변수 ‘ n ’에 저장합니다. 이 값은 반복문에서 사용됩니다. 
3. 외부 반복문

       for i in range(n-1):

    
   • ‘ i ’는 현재 정렬할 요소의 인덱스를 나타냅니다. 이 반복문은 배열의 모든 요소를 순회하며, 각 단계에서 현재 위치 ‘ i ’를 기준으로 최솟값을 찾습니다. 
4. 최솟값 인덱스 초기화

           min_idx = i

    
   • ‘ min_idx  ’ 변수를 현재 인덱스 ‘ i ’로 초기화합니다. 이는 현재 위치에서 시작하여 가장 작은 값을 찾기 위한 기준점입니다. 
5. 내부 반복문

           for j in range(i+1, n):

    
   • ‘ j ’는 현재 위치 ‘ i ’ 이후의 요소들을 순회합니다. 이 반복문은 ‘ i + 1 ’부터 시작하여 배열 끝까지 진행됩니다. 
6. 최솟값 비교 및 갱신

               if arr[j] < arr[min_idx]:
                   min_idx = j

    
   • 현재 요소 ‘ arr[j] ’가 ‘ arr[min_idx] ’보다 작으면, ‘ min_idx  ’을 ‘ j ’로 업데이트합니다. 이렇게 함으로써, 정렬되지 않은 부분에서 가장 작은 값의 인덱스를 찾습니다. 
7. 교환 수행

           arr[i], arr[min_idx] = arr[min_idx], arr[i]

    
   • 내부 반복문이 끝난 후, 현재 위치 ‘ i ‘와 찾은 최솟값의 인덱스 ‘ min_idx  ’에 있는 값을 교환합니다. 이로 인해 현재 위치에는 가장 작은 값이 오게 됩니다.
     

선택 정렬(Selection Sort)의 특징 중 하나는 min_idx = i와 같은 방식으로 최솟값의 인덱스를 설정하는 것입니다. 이 코드는 선택 정렬 알고리즘의 핵심적인 부분으로, 정렬 과정에서 가장 작은 값을 찾기 위해 현재 위치의 인덱스를 초기화하는 역할을 합니다. 

 

마지막으로, 선택 정렬의 주요 특징들에 대해 정리해 보겠습니다.

1. 제자리 정렬(in-place sorting)
   • 선택 정렬은 제자리 정렬 알고리즘입니다. 이는 추가적인 배열이나 리스트를 생성하지 않고, 주어진 배열 내에서 직접 요소를 교환하여 정렬을 수행한다는 의미입니다. 이로 인해 메로리 사용이 효율적이며, 공간 복잡도는 O(1)입니다.
2. 최솟값 인덱스 설정
   • ‘ index_min = i ‘처럼 현재 위치 ‘ i ‘의 값을 최솟값으로 가정하고 시작합니다. 이후 내부 반복문을 통해 더 작은 값이 발견되면 ‘ index_min ‘을 갱신합니다. 이 방식은 각 요소를 순회하면서 가장 작은 값을 찾기 위한 기준점을 설정합니다. 
3. 시간 복잡도
   • 선택 정렬의 시간 복잡도는 O(n^2)입니다. 이는 두 개의 중첩된 반복문이 있기 때문입니다. 
   • 선택 정렬의 외부 루프는 실제로 n-1번 실행됩니다. 이는 마지막 요소는 자동적으로 정렬된 위치에 놓이게 되므로 추가적인 비교나 교환이 필요하지 않기 때문입니다. 따라서 전체 비교 횟수는 n(n-1)/2입니다.
     • 첫 번째 반복에서 n-1번 비교
     • 두 번째 반복에서 n-2번 비교
     • 세 번째 반복에서 n-3번 비교
       ........
     • n-1번째 반복에서 1번 비교
       이 비교 횟수를 모두 더하면 (n-1) + (n-2) + (n-3) + ... + 2 + 1이 되며 이는 등차수열의 합 공식에 따라 n(n-1)/2와 같습니다.
4. 불안정한 정렬(Unstable sort)
   • 선택 정렬은 불안정한 알고리즘입니다. 즉, 동일한 값을 가진 요소들의 상대적인 순서가 보장되지 않습니다. 이는 교환 과정에서 동일한 값이 서로 교환될 수 있기 때문입니다.  

 

 

 

#이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.