[알고리즘] 선택 정렬(selection sort)

yujamint·2022년 7월 13일

Java ps 알고리즘

PS

목록 보기

3/9

선택 정렬

선택 정렬은 제자리 정렬(in-place sorting) 알고리즘의 하나이다.

제자리 정렬 : 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 즉, 자료를 넣을 자리를 먼저 선택하고 그 자리에 오는 값을 찾는다.

정렬 과정

오름차순을 기준으로 정렬한다
1. 주어진 배열에서 최소값을 찾는다.
2. 찾은 최소값을 가장 앞 인덱스에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위 과정을 반복한다. (마지막에 남은 원소는 최대값이고, 자동으로 가장 끝에 위치하게 된다.)
- 1회전에서 첫 번째 인덱스에 최소값을 넣는다.
- 2회전에서 두 번째로 작은 값을 두 번째 인덱스에 넣는다.
- n회전에서 n번째로 작은 값이 n번째 인덱스에 위치하게 된다.

선택 정렬 Java 코드

public int[] SelectionSort(int n, int[] arr){
// n = 6 , arr = {13, 5, 11, 7, 23, 15}
	int index = 0;
	for(int i=0; i<n-1; i++) {
        int min = Integer.MAX_VALUE;
    	for(int j=i; j<n; j++) {
        	if(arr[j] < min) {
            	min = arr[j];
                index = j;
                }
         }
         arr[index] = arr[i];
         arr[i] = min;
    }
    return arr; 
}

입력 : 13 5 11 7 23 15
출력 : 5 7 11 13 15 23

1회전 :
전체 배열에서의 최소값인 5를 찾아서 가장 앞에 위치한 자료인 13과 교체한다.
결과 - 5 13 11 7 23 15
2회전 :
1회전에서 정렬한 0번 인덱스를 제외한 리스트에서의 최소값인 7을 찾아서 가장 앞에 위치한 자료인 13과 교체한다.
결과 - 5 7 11 13 23 15
3회전 :
앞에서 정렬한 1번 인덱스까지를 제외한 리스트에서의 최소값인 11을 찾아서 가장 앞에 위치한 자료인 자료와 교체한다.(11은 이미 2번 인덱스에 위치하므로 교체 일어나지 않는다.)
결과 - 5 7 11 13 23 15
4회전 :
2번 인덱스까지를 제외한 리스트에서의 최소값인 13을 찾아서 가장 앞에 위치한 자료와 교체한다.(13은 이미 3번 인덱스에 위치하므로 교체 일어나지 않는다.)
결과 - 5 7 11 13 23 15
5회전 :
3번 인덱스까지를 제외한 리스트에서의 최소값인 15를 찾아서 가장 앞에 위치한 자료와 교체한다.
결과 - 5 7 11 13 15 23
한 가지 자료가 남을 때까지 실행하였으므로 정렬은 종료되고, 오름차순으로 정렬된 것을 확인할 수 있다.

시간복잡도

첫 번째 회전에서의 비교횟수 : 1 ~ n => n
두 번째 회전에서의 비교횟수 : 2 ~ n => n-1
...
(n-1) 번째 회전에서의 비교횟수 : (n-1) ~ n => 1

n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2
= N * N
= O(N * N)

n개의 자료가 들어있는 배열을 정렬하는 데에 걸리는 시간은 O(n^2)이다. 최선,평균,최악의 경우 모두 같은 비교횟수를 가진다.