[Algorithm] Selection Sort (선택정렬)

 

 

https://www.inflearn.com/course/algorithm-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%A4%EC%8A%B5#curriculum

[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의

 

 

위 사이트의 두번째 강의인 정렬의 개요와 선택 정렬에 대한 강의일지를 쓴다. (복습 겸)

 

 

선택정렬의 시간 복잡도는 O(N*N) 혹은 O(N^2) 라고 한다.

회수는 등차수열의 합 n * ( n + 1 ) / 2 이나 컴퓨터에스는 가장 큰 차수인 N^2 만 보기 때문이라고 한다.

 

 

 

 

* 시간복잡도는 시간과 관련된 효율성으로 정확한 시간이라 아니라 처리 시간의 증가율을 나타내는 척도이다.

출처: https://kodakit.tistory.com/entry/%EB%B9%85%EC%98%A4%ED%91%9C%EA%B8%B0%EB%B2%95-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84

 

 

 

 

 

 

일단 C++로 코드를 쓴다면

 

#include <stdio.h>

int main(void) {
	int i, j, min, index, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for (i = 0; i < 10; i++) {
		min = 9999;
		for (j = i; j < 10; j++) {
			if (min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	for (i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
	return 0;
}

 

배열에서 남아있는 수 중에서 가장 작은 수만 앞으로 보내는 것이다.

 

 

 

위 코드를 자바스크립트로 바꾼다면 (사실 별 거 없다)

 

function main() {
    let i, j , min, index, temp;
    let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
    for (i = 0; i < 10; i++) {
    	// min은 array에 들어있는 숫자보다 아주 큰 수로 정해줘야 한다.
        min = 9999;
        for (j = i; j < 10; j++) {
        	if (min > array[j]) {
            	min = array[j];
                index = j;
            }
        }
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }
    console.log(array.join(", "));
}

main();

 

이렇게 된다.

 

 

 

 

강의 들을 때는 생각 안 해봤는데 만약에 1이 맨 앞에 없어도 되는 것인지 궁금했다.

뒤에 있는 2도 원래 자리를 찾아갔는데 1이라고 자리를 바꾼다고 해서 다를 거 같진 않았다.

 

let array = [10, 2, 5, 8, 7, 6, 4, 3, 1, 9];

 

array 안의 수 위치만 바꿔줬다.

 

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

 

 

역시나 정렬이 잘 된다.

 

 

java로는 다음과 같이 작성하면 된다.

 

 

public class Sort
{
    public static void selectionSort(int[] args) {
        int index = 0;
        int i, j, min, temp;
        int[] array = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        for (i = 0; i < 10; i ++) {
            min = 9999;
            for (j = i; j < 10; j++) {
            	if (min > array[j]) {
                    min = array[j];
                    index = j;
                }
            }
            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
        for (i = 0; i < 10; i++) {
        	System.out.printf("%d ", array[i]);
        }
    }
}

 

 

C++ 로 작성된 코드에서는 에러가 없었는데

Java 의 경우

int index = 0;

 

을 선언하지 않으면

array[i] = array[index]

에서 에러가 난다. 그래서 추가해주었다.

 

(아마도 if 문을 걸리지 않을 경우 index 에 아무 값도 들어있지 않기 때문에 에러가 난 거 같다.)

 

 

위 식에서 왜 min = 9999 해야 하는지 이해가 안 가서 다른 소스도 찾아봤다.

 

출처: https://devuna.tistory.com/28

출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=os2dr&logNo=221717426079

출처: https://st-lab.tistory.com/168

 

void selectionSort(int [] arr) {
    // min값을 가리키는 index와 임시변수
    int minIndex, temp;
    // 배열 크기만큼 순회
    for (int i = 0; i < arr.length - 1; i++) {
        // minIndex 임의선택
        minIndex = i;
        // i + 1 번째 원소부터 index까지 값 비교 (최솟값을 갖고 있는 index 찾기)
        for (int j = i + 1; j < arr.length; j++) {
            // 현 min 값보다 작다면 minIndex 갱신
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        // 순회 끝난 뒤에 교환 (가장 작은 값을 앞으로 보냄, i번째 값과 최솟값 서로 교환)
        temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

 

 

위 블로그에서는 이게 공간복잡도가 O(N) 이라고 한다. 이게 메모리와 추가적인 공간을 필요로 하지 않는 제자리 정렬이기 때문에 공간복잡도가 O(N)으로 나온 것이 아닌지 추측해본다.