선택 정렬 알고리즘 이해(Java 예제 포함)

선택 정렬: 단계별 안내

선택 정렬은 간단한 정렬 알고리즘입니다. 목록의 정렬되지 않은 부분에서 최소 요소를 반복적으로 찾아 처음에 배치합니다. 이 과정은 전체 목록이 정렬될 때까지 계속됩니다.

선택 정렬 작동 방식

이 배열을 오름차순으로 정렬하는 예를 들어 보겠습니다.

반복 1:

목표는 가장 작은 요소를 처음에 배치하는 것입니다. 첫 번째 요소가 최소값이라고 가정하여 시작합니다.

현재 최소값을 각 후속 요소와 비교하여 더 작은 요소가 발견되면 최소값을 업데이트합니다.

이는 실제 최소값이 확인될 때까지 계속됩니다.

마지막으로 최소 요소를 첫 번째 요소로 바꿉니다.

이제 첫 번째 요소가 정렬되었습니다. 후속 반복에서는 정렬되지 않은 부분만 고려됩니다.

후속 반복:

정렬되지 않은 나머지 요소마다 이 프로세스가 반복됩니다.

알고리즘은 n-1번 반복됩니다(여기서 n은 배열의 길이입니다). 다섯 번째 반복(요소 6개 배열의 경우) 후에는 마지막 요소가 암시적으로 정렬됩니다.

선택 정렬 구현(Java):

import java.util.Arrays;

public class SelectionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        // Iterate through the array size-1 times
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            // Find the minimum element in the unsorted part
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

출력:

정렬되지 않은 배열: [8, 2, 6, 4, 9, 1] 정렬된 배열: [1, 2, 4, 6, 8, 9]

복잡성 분석:

• 시간 복잡도: 모든 경우(최상, 평균, 최악)에서 O(n²)입니다. 중첩 루프는 입력 순서에 관계없이 항상 고정된 횟수만큼 실행됩니다.
• 공간 복잡도: O(1). 이는 지속적인 추가 공간이 필요한 내부 알고리즘입니다.

결론:

선택 정렬은 O(n²) 시간 복잡도로 인해 대규모 데이터 세트에는 비효율적입니다. 성능보다 단순성이 우선시되는 소규모 어레이나 상황에 가장 적합합니다.

위 내용은 선택 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!