CS(Computer Science)/알고리즘

JAVA 선택정렬이란(Selection Sort)

galid1 2018. 10. 28. 17:50
728x90

선택정렬이란

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

- 정렬되지 않은 자료중 



과정

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

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

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


시간 복잡도 

Θ(n2


코드


1) SelectionSort Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
    }
 
}
cs


2) SortUtil Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
    }
    
}
 
cs


코드해석

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

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

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

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