Sort(정렬)에 대해서 - Selection Sort

선택 정렬 

주어진 자료중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식입니다. 저장되어 있는 자료를 전체 정렬한 뒤에 k 번째의 원소를 가져오는 것과는 차이가 있는 것 같습니다.

1. 주어진 리스트 중에서 최소값을 찾습니다.
2. 그 값을 리스트의 맨 앞에 위치한 값과 교환합니다.
3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 작업을 반복합니다.

{64, 25, 10, 22, 11}을 선택 정렬하는 과정

1. 리스트에서 최소값을 찾습니다. 현재 시작위치는 64이고 최소값은 10입니다.

64

25

10

22

11

2. 리스트의 맨 앞에 위치한 값과 교환합니다. 10은 정렬이 완료되었습니다.

10

25

64

22

11

3. 아직 정렬되지 않은 리스트에서 최소값을 찾습니다. 현재 위치는 25이고 10을 제외한 최소값은 11입니다. 

10

25

64

22

11

4. 아직 정렬되지 않은 리스트의 맨 앞에 위치한 값과 교환합니다. 10과 11은 정렬이 완료되었습니다.

10

11

64

22

25

5. 위의 작업을 반복합니다..

Selection Sort 구현하기

 
public class 선택정렬 {
    public static void main(String[] args) {
        int[] arr = {64, 25, 10, 22, 11};
        int[] sortedArr = selectionSort(arr);
        
        for(int i=0; i<sortedArr.length; i++) {
            System.out.printf(sortedArr[i]+" ");
        }
    }
    
    private static int[] selectionSort(int[] arr) {
        for(int i=0; i<arr.length-1; i++) {
            int min = i;
            for(int j=i+1; j<arr.length; j++) {
                if(arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        return arr;
    }
}