[Algorithm] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

출처

선택 정렬(Selection Sort)은 배열에서 가장 작은(또는 가장 큰) 원소를 선택하고 이를 배열의 앞쪽으로 이동시키는 방식으로 동작합니다.
비교 연산을 기반으로 동작하며 원소 간의 비교를 통해 작은(또는 큰) 값을 찾고 배열에서 다른 위치로 이동시키는 방식으로 동작합니다.

예제

먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다.

위 배열을 오름차순으로 정렬하기 위한 선택 정렬 알고리즘은 다음과 같이 동작합니다.

먼저 첫 번째 위치의 값과 해당 배열에서의 가장 작은 값이 무엇인지 확인합니다.
영 번째 인덱스의 값인 15보다 세 번째 인덱스의 값 10이 더 작은 값 입니다.

가장 작은 값인 10을 영 번째 인덱스에 넣고 15는 세 번쨰 인덱스로 위치를 교환합니다.

한 번의 탐색으로 해당 배열은 위와 같이 정렬됩니다.

그 후 이미 정렬된 영 번째 인덱스를 제외하고 가장 작은 값인 15를 첫 번쨰 인덱스에 배치해야 한다는 것을 발견합니다.

두 번의 탐색으로 두 개의 작은 값이 정렬되었습니다.

위와 같이 동일한 방식으로 나머지 정렬되지 않은 배열의 요소에도 똑같은 작업을 진행합니다.

다음은 전체 정렬 과정을 시각적으로 나타낸 것 입니다.

출처

시간 복잡도

선택 정렬은 두 개의 중첩된 반복문을 사용하여 배열을 정렬합니다.
외부 반복문은 배열의 모든 요소를 반복하며 내부 반복문은 외부 반복문의 현재 요소를 기준으로 나머지 요소들과 비교합니다.
선택 정렬은 입력된 배열의 크기와 무고나하게 항상 동일한 수의 비교와 교환을 수행하기 때문에 최선, 평균, 최악의 경우 모두 동일한 시간 복잡도 O(n^2)을 가집니다.

코드

package io.github.ones1kk.study.sorting;

public class SelectionSort {

    public static void selectionSort(int[] arr, int size) {
        for (int i = 0; i < size - 1; i++) {
            int min_index = i;

            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[min_index]) {
                    min_index = j;
                }
            }

            swap(arr, min_index, i);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

좀 더 자세한 코드는 이 곳에서 확인 가능합니다.

 

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.