Selection Sort, 가장 기본적인 선택 정렬

dropKick·2020년 5월 25일

자바 정렬 알고리즘

자료구조와 알고리즘

목록 보기

18/22

목표

Selection Sort 알고리즘 이해
Selection Sort 알고리즘 구현
Selection Sort 알고리즘 특징과 시간복잡도 이해

Selection Sort 알고리즘

가장 기본적인 알고리즘 중 하나
제자리 정렬 기법을 사용

제자리 정렬은 원소들의 개에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘들을 의미하며, 제자리 알고리즘의 범위에 포함된다.
예를 들어 삽입 정렬은 이미 주어진 원소들을 옮긴 뒤 적절한 위치에 원소를 삽입하는 연산을 반복하는데, 이 과정에서 원소들을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 원소가 저장되는 공간과 루프 변수 정도에 불과하다.
퀵 정렬은 제자리 알고리즘의 정의에 따라서 제자리 정렬로 분류할 수도 있고 아닐 수도 있다. 퀵 정렬은 재귀적으로 정의되기 때문에 스택을 사용하게 되는데, 이 스택의 깊이는 n개의 원소에 대해 비례하므로 전체 공간 복잡도는 상수가 아니다. 하지만 실용적인 의미에서 퀵 정렬은 상대적으로 작은 메모리만을 더 사용하기 때문에 흔히 제자리 정렬로 기술된다.

Selection Sort 알고리즘 구현

public class selectionSort {
    public static void swap(Integer[] arr, int prev, int next) {
        int temp = arr[prev];
        arr[prev] = arr[next];
        arr[next] = temp;
    }

    public static void simplySort(Integer[] arr, int len) {
        for (int i = 0; i < len - 1; i++) {
            int min = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
                swap(arr, i, min);
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr =new Integer[]{6,5,4,3,2,1};
        simplySort(arr, arr.length);
        for (Integer integer : arr) {
            System.out.println(integer);
        }
    }
}