선택정렬 Selection Sort

안녕하세요, 오늘은 선택 정렬(Selection Sort)에 대해 알아보겠습니다.

선택 정렬은 가장 기본적인 정렬 알고리즘 중 하나입니다. 정렬되지 않은 배열에서 작은 값부터 차례대로 선택해 앞쪽으로 가져오는 방식으로 정렬을 수행합니다. 구현 방법이 매우 간단하고 이해하기 쉬운 것이 장점입니다.

728x90

선택 정렬의 동작 원리

1. 배열에서 가장 작은 값을 선택합니다.
2. 선택한 값을 맨 앞으로 옮깁니다. (첫 번째 자리)
3. 남은 배열에서 두 번째로 작은 값을 선택합니다.
4. 선택한 값을 두 번째 자리로 옮깁니다.
5. 이런 식으로 배열의 끝까지 반복합니다.

이렇게 하면 매 단계마다 작은 값부터 순서대로 앞으로 이동하게 되어 정렬이 완성됩니다. 간단한 예시로 살펴보겠습니다.

[5, 3, 8, 4, 9] 초기 배열

1. [3, 5, 8, 4, 9] 3이 첫 번째로 이동
2. [3, 4, 8, 5, 9] 4가 두 번째로 이동 
3. [3, 4, 5, 8, 9] 5가 세 번째로 이동
4. [3, 4, 5, 8, 9] 8이 네 번째에 있어서 교체 없음
5. [3, 4, 5, 8, 9] 정렬 완료

반응형

선택 정렬의 시간 복잡도

선택 정렬의 시간 복잡도는 O(n^2)입니다. 왜냐하면 전체 배열 크기 n에 대해 n-1번의 탐색이 이루어지기 때문입니다. 즉, 배열의 크기가 커질수록 수행 시간이 급격히 증가하게 됩니다. 대용량 데이터에는 적합하지 않은 알고리즘이라고 할 수 있습니다.

선택 정렬의 장단점

장점

• 구현이 매우 간단합니다.
• 정렬 과정에서 데이터의 이동이 적어 메모리에 유리할 수 있습니다.
• 작은 데이터 셋에 대해서는 빠른 편입니다.

단점

• 시간 복잡도가 O(n^2)로 데이터 크기가 클수록 비효율적입니다.
• 다른 정렬 알고리즘에 비해 대부분의 경우에 성능이 좋지 않습니다.

선택 정렬의 활용

선택 정렬은 데이터 양이 적고, 데이터 이동을 최소화해야 하는 경우에 유용합니다. 하지만 대부분의 경우에는 다른 효율적인 정렬 알고리즘(퀵정렬, 병합정렬 등)을 사용하는 것이 좋습니다.

정렬 알고리즘의 기본 개념을 익히고자 한다면 선택 정렬부터 시작하여 이해하는 것이 도움이 될 수 있습니다. 하지만 실제 프로그래밍에서는 좀 더 효율성이 높은 정렬 알고리즘을 주로 활용하게 될 것입니다.

 

<Python 예제 코드>

def selection_sort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        
        # Find the minimum element in remaining unsorted array
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example usage
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array is:", arr)

 

<C++ 예제 코드>

#include <iostream>
using namespace std;

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // Find the minimum element in unsorted array
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // Swap the found minimum element with the first element
        swap(arr[min_idx], arr[i]);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selection_sort(arr, n);
    
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

 

<삽입 정렬 Insertion Sort>

https://tonnykang.tistory.com/180

삽입 정렬(Insertion Sort)