JAVA 선택정렬이란(Selection Sort)

선택정렬이란

- 제자리 정렬 알고리즘의 하나

- 정렬되지 않은 자료중 

과정

1. 주어진 리스트중 가장 작은 값을 찾는다

2. 그 값을 맨앞에 위치한 값과 뒤 바꾼다

3. 맨 처음 위치를 뺀 나머지리스트를 같은 방법으로 순회하여 교체한다.

시간 복잡도 

- Θ(n²) 

코드

1) SelectionSort Class

public class SelectionSort {
 
    public void selectionSort(int[] unsortedList) {
        for(int i = 0; i < unsortedList.length - 1; i++) {
            int min = i;
            for(int j = i+1; j < unsortedList.length; j++) {
                if(unsortedList[min] > unsortedList[j])
                    min = j;
            }
            SortUtil.swap(unsortedList, i, min);
        }
        
        SortUtil.printList(unsortedList);
    }
    
 
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] list = new int[]{3,1,4,5,2};
        
        SelectionSort selection = new SelectionSort();
        selection.selectionSort(list);
    }
 
}

2) SortUtil Class

public class SortUtil {
    
    public static void printList(int[] list) {
        for(int num : list)            
            System.out.println(num + " ");
    }
    
    public static void swap(int[] list, int num1, int num2) {
        int temp = list[num1];
        list[num1] = list[num2];
        list[num2] = temp;
    }
    
}
 

코드해석

1. i에 대한 for문은 1씩 증가할 때 마다 리스트에서 정렬되지 않은 첫번째 원소를 선택하고 int min 변수에 원소의 위치(i)를 저장한다

2. j에 대한 for문은 1씩 증가할 때 마다 리스트에서 min 위치에 있는 값과 j의 위치값을 비교하여

   j위치 값이 더 작은 경우 min 변수에 j를 저장한다.

3. j에 대한 for문이 1사이클을 종료하면 i위치의 원소와 min위치의 원소를 뒤바꾼다