[정렬 알고리즘] 선택정렬(Selection Sort), 삽입정렬(Insertion Sort)

정렬 알고리즘에는 7가지가 있다.

선택정렬,

삽입정렬,

버블정렬,

병합정렬,

힙정렬,

퀵정렬,

기수정렬

 

 

그 중 선택정렬과 삽입정렬에 대해 알아보자.

 

 

1. 선택정렬(Selection Sort)

: 주어진 리스트에서 값을 선택해서 나머지 값들과 비교하여 순서대로 값을 정렬하는 알고리즘이다.

 

방법

1. 주어진 리스트 중에 처음 값을 최소값이라고 지정한다.
2. 그 이후 값과 비교하며 최소값을 찾는다. 최소값을 맨 앞에 위치한 값(i번째 값)과 교체한다.
3. 처음 for문에서 값 하나를 증가시킨다. 나머지 리스트를 같은 방법으로 교체한다.

private static void selectionSort() {

    for (int i = 0; i < n-1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {

            if (array[j] < array[min]) {
                min = j;
            }

        }
        changeCurrentValueWithMinValue(min, i);
    }
}

private static void changeCurrentValueWithMinValue(int minIdx, int currentIdx) {

    int tmpVal = array[minIdx];
    array[minIdx] = array[currentIdx];
    array[currentIdx] = tmpVal;

}

시간복잡도는 O(n^2)이다.

best, worst, average 모두 동일하다.

 

 

 

2. 삽입정렬(Insertion Sort)

: 맨 처음 값을 가장 큰 값이라고 지정하고 그 전의 값들과 비교하며 삽입하는 알고리즘이다.

 

방법:

1. 주어진 리스트 중에 처음 값을 최대값이라고 지정한다.

2. 그 이전 값(array[j])과 비교하며 최대값을 찾는다. 그 이전 값이 최대값 보다 크다면 다음값(array[j+1])에 그 이전 값(array[j])을 넣는다.

3. 2번째 for문이 끝날 때까지 순서2를 반복한다.

4. 최대값을 j다음 번째에 넣는다.

 

private static void insertionSort() {

    int j = 0;
    for(int i = 1; i < n; i++) {
        int max = array[i];
        for(j = i-1; j >= 0; j--) {

            if(max < array[j]) {
                array[j+1] = array[j];
            }
            else {
                break;
            }
        }
        array[j+1] = max;
    }

}

시간복잡도는 best(이미 정렬되어 있다면) O(n)

average, worst는 O(n^2)이다.