SelectionSort(선택정렬) - JAVA

SelectionSort의 개념을 간단하게 알아보고, java로 구현해보자.

선택 정렬이란?

• 제자리 정렬 알고리즘
• 가장 단순한 정렬 알고리즘이며, 메모리가 제한적인 경우 성능 이점

선택 정렬 과정

1) 주어진 리스트 중에 최소값을 찾는다.
2) 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

시뮬레이션

[7,4,2,8,3,5,1,6,10,9] 리스트를 SelectionSort로 정렬해보자.

• 최소값을 찾는다.

• 현재 인덱스에 위치한 7과 최소값 1을 SWAP하고, 인덱스를 하나 증가시킨 후 MinValue를 찾는다. 이 과정을 정렬이 완료될 때까지 반복한다.

• MinValue가 더 크기 때문에 SWAP하지 않는다.

시간복잡도(Time Complexity)

• O(N^2)

탐색 횟수가 항상 고정적이므로 시간복잡도는 항상 O(N^2)이다.

구현

public class selectionSort{
    static void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        
         // 최솟값을 탐색한다.
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
        if(i!=indexMin){
            temp = list[indexMin];
            list[indexMin] = list[i];
            list[i] = temp;
        }
    }
}
    
    public static void main(String[] args){
     	int[] list={7,4,2,8,3,5,1,6,10,9};
        selectionSort(list);
        for(int i=0;i<list.length;i++) {
            System.out.print(list[i]+",");
        }
    }
}

Reference

• 선택정렬 - 위키백과