정렬 알고리즘 -선택 정렬 - selection sort

선택 정렬은 배열의 정렬되지 않은 부분에서 최소 요소를 반복적으로 찾아 배열의 정렬된 부분의 시작 부분으로 이동하여 배열 또는 목록을 정렬하는 간단한 정렬 알고리즘입니다.

선택 정렬 알고리즘의 단계는 다음과 같습니다:

1. 배열의 첫 번째 요소를 최소값으로 설정합니다.
2. 두 번째 요소부터 시작하여 각 요소를 최소값과 비교합니다.
3. 요소가 최소값보다 작으면 이를 새로운 최소값으로 설정합니다.
4. 배열의 끝에 도달할 때까지 이 과정을 계속합니다.
5. 최소값을 배열의 정렬되지 않은 부분의 첫 번째 요소와 바꿉니다.
6. 배열의 나머지 정렬되지 않은 부분에 대해 2~5단계를 반복합니다.
7. 이제 배열이 정렬되었습니다.

다음은 정수 배열에서 선택 정렬이 어떻게 작동하는지 보여주는 시각화입니다

원래 배열: 7 3 5 2 8 4 1 6

1을 통과시킵니다:
최소 요소는 1입니다. 첫 번째 요소로 바꿉니다.
1 3 5 2 8 4 7 6

2를 통과시킵니다:
최소 요소는 2입니다. 두 번째 요소와 교환합니다.
1 2 5 3 8 4 7 6

패스 3:
최소 요소는 3입니다. 세 번째 요소로 바꿉니다.
1 2 3 5 8 4 7 6

4를 통과합니다:
최소 원소가 4입니다. 네 번째 원소로 바꿉니다.
1 2 3 4 8 5 7 6

5를 통과합니다:
최소 원소가 5입니다. 다섯 번째 원소로 바꿉니다.
1 2 3 4 5 8 7 6

6을 통과합니다:
최소 원소가 6입니다. 여섯 번째 원소로 바꿉니다.
1 2 3 4 5 6 7 8

정렬된 배열은 1 2 3 4 5 6 7 8입니다.

선택 정렬은 시간 복잡도가 O(n^2)이므로 큰 배열에서는 비효율적입니다. 하지만 이해하고 구현하기 쉽다는 장점이 있습니다.

 

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the minimum element in the unsorted part of the array
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Swap the minimum element with the first element of the unsorted part of the array
        arr[i], arr[min_index] = arr[min_index], arr[i]
    
    return arr

 

 

이 함수를 사용하기 위해 간단하게 아래 처럼 사용 할 수 있습니다

 

arr = [7, 3, 5, 2, 8, 4, 1, 6]
sorted_arr = selection_sort(arr)
print(sorted_arr) # Output: [1, 2, 3, 4, 5, 6, 7, 8]