[Algorithm] 선택 정렬(Selection sort)

 

선택 정렬 기본 개념

제자리 정렬(in-place sorting) 알고리즘의 하나로, 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

선택 정렬 구체적인 개념

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세번째 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회차에서는 두 번째 자료를 가지고 비교한다.

선택 정렬 알고리즘 예제

import java.util.Arrays;

public class SelectionSort {

    public static void main(String[] args) {
        
        int[] unsortedArray = {8, 5, 6, 2, 4};
        System.out.println("Array Before sorting: " + Arrays.toString(unsortedArray));
        System.out.println("Array After sorting : " + Arrays.toString(selectionSort(unsortedArray)));
    }

    private static int[] selectionSort(int[] arr) {
        
        int temp = 0;
        int arrLength = arr.length;
        
        for (int i=0; i<arrLength-1; i++) {
            int minIndex = i;
            for (int j=i+1; j<arrLength; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
            
            System.out.println((i+1) + "th element swapped : " + Arrays.toString(arr));
        }
        return arr;
    }
}

선택 정렬 알고리즘 특징

장점
자료 이동 횟수가 미리 결정된다.

단점
안정성을 만족하지 않는다. 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

단순하지만 비효율적인 방법
- 버블 정렬, 선택 정렬, 삽입정렬

복잡하지만 효율적인 방법
- 셸 정렬, 힙 정렬, 퀵 정렬, 병합 정렬

 

정렬 알고리즘 Post

[프로그래밍/Algorithm] - [Algorithm] 버블 정렬(Bubble sort)

[프로그래밍/Algorithm] - [Algorithm] 삽입 정렬(Insertion sort)

[프로그래밍/Algorithm] - [Algorithm] 선택 정렬(Selection sort)

[프로그래밍/Algorithm] - [Algorithm] 셸 정렬(Shell sort)