선택 정렬 (Selection Sort)

선택 정렬(Selection Sort)

선택 정렬(Selection Sort)은 정렬 알고리즘 중 가장 기본적이면서도 직관적인 방법 중 하나입니다. 선택 정렬의 동작 원리는 배열에서 가장 작은 값을 찾아 첫 번째 위치로 이동시키고, 그 다음 작은 값을 찾아 두 번째 위치로 이동시키는 과정을 반복하는 것입니다. 이를 통해 전체 배열이 정렬됩니다.

 

선택 정렬의 동작 방식은 다음과 같습니다.

1. 배열에서 가장 작은 값을 찾습니다.
2. 찾은 작은 값을 배열의 첫 번째 원소와 교환합니다.
3. 두 번째 원소부터 배열의 마지막 원소까지 위의 과정을 반복합니다.
4. 위의 과정을 배열의 크기만큼 반복하면, 배열이 정렬된 상태가 됩니다.

아래는 선택 정렬의 동작 원리를 그림으로 나타낸 것입니다.

 

출처: https://en.wikipedia.org/wiki/Selection_sort#Example

 

선택 정렬의 시간 복잡도는 O(n^2)이며, 불안정 정렬에 속합니다. 이는 동일한 값을 가진 원소의 상대적인 위치가 정렬 후에도 유지되지 않을 수 있음을 의미합니다. 또한, 입력 배열이 이미 정렬된 경우에도 모든 원소를 비교하므로 비효율적입니다.

Java에서의 선택 정렬 사용

다음은 자바에서의 선택 정렬 구현 코드입니다:

void selectionSort(int arr[]) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

이 코드는 주어진 배열을 순회하면서 각 위치에 맞는 최솟값을 찾아 해당 위치와 교환하는 과정을 반복합니다. 이를 통해 전체 배열이 정렬됩니다.