정렬 part1. 선택 정렬

https://pixabay.com/photos/pattern-background-patterns-tiles-1245991/

 프로그램뿐 아니라 일상에서도 정렬을 하는 일은 굉장히 많습니다. 일례로 도서관에서 책을 장르, 제목 등으로 정렬하는 것도 그 예이지요. 이렇게 정렬을 하는 이유는 단편적으로는 심리적 안정감[# 자기만의 기준으로 물건을 배치하는 것 또한 일종의 정렬이라 볼 수 있겠지요], 보기 좋아서일 수 있습니다. 그러나 제일 중요한 것은 많은 대상 중에 필요한 부분을 더 빠른 속도로 찾기 위함이겠죠.

 

 이번 시간에는 정렬 알고리즘 중에서 간단한 축에 속하는 선택 정렬에 대해 다루어봅니다.

---

 

선택 정렬

 정렬은 정렬인데 선택 정렬은 무엇인가 싶습니다.

네이버 사전

 여럿 가운데서 필요한 것을 골라 뽑음이라고 되어있네요.

정의

 정렬되지 않은 여러 대상 중에서 정렬 기준에 부합하는 대상을 찾아 새롭게 배치하는 구조입니다. 처음 시도에서 정렬 기준에 가장 부합하는 대상을 찾아 첫 번째 자리에 둡니다. 그리고 정렬된 첫 번째 항목을 제외한 나머지 중 기준에 부합하는 대상을 찾아 두 번째 자리에 둡니다. 이렇게 정렬된 항목을 제외한 대상(K-1개) 중 기준에 맞는 대상을 찾아 K번째 자리에 두는 것을 선택 정렬이라고 합니다.

PseudoCode(의사 코드)

function AsendingSelectionSorting(input: array){
    i = 0, k = 0
    selectionIndex = 0
    
    while(i < input.length - 1){
        k = i + 1
        selectionIndex = i
        
        while(k < input.length){
            if(input[selectionIndex] > input[k]) then
                selectionIndex = k
            k = k + 1
        }
        
        temp = input[selectionIndex]
        input[selectionIndex] = input[i]
        input[i] = temp
        
        i = i + 1
    }
}

 의사 코드 표현을 하는 것은 굉장히 오랜만인지라 잘 이해하도록 작성했는지 의문이군요.

복잡도

시간 복잡도

 선택 정렬의 시간 복잡도는 O(n²)입니다. 제일 바깥의 반복문은 n-1번 반복하며, i번[# 실제 작동은 n-1번 반복부터 시작해서 1번 반복까지 동작하지만, 편의상 이 과정을 역으로 1번 반복부터 n-1번 반복까지로 수정했습니다.] 반복하게 됩니다. 즉 아래 이미지와 같은 식이 구성됩니다.

다른 작업은 무시하고 반복 횟수만 계산

 여기에서 시간 복잡도 Big-O 표기법은 가장 높은 차수의 계수만 다루므로 ½와 -n은 제외하고 n²만 살아남게 됩니다.

공간 복잡도

 이 알고리즘은 들어오는 입력만큼의 공간만 필요하므로 공간 복잡도는 O(n)입니다. 여기서 i, k, selectionIndex와 같은 변수도 존재하지만 이 변수들은 입력이 얼마나 들어오던 무조건 3으로 고정입니다. 표기 규칙으로 인해 이 상수 3은 무시됩니다.

---

실제 코드

 정의만 알아서는 무의미합니다. 실제 코드로는 어떻게 작성되는지 알아보아야겠죠. 이번에는 오름차순 정렬을 합니다.

#include<stdio.h>

int main(void){
    int array[10];
    
    for(int i = 0; i < 10; ++i){
        scanf("%d", array + i);
    }
    
    /* selection sorting Start */
    
    for(int i = 0; i < 9/*input.length-1*/; ++i){
        int selectionIndex = i;
        for(int k = i + 1; k < 10; ++k){
            if(array[selectionIndex] > array[k]) selectionIndex = k;
        }
        
        int temp = array[selectionIndex];
        array[selectionIndex] = array[i];
        array[i] = temp;
        
    }
    
    /* end of selection sorting */
    
    for(int i = 0; i < 10; ++i){
        printf("%d ", array[i]);
    }
    
    return 0;
}

 이 코드는 사용자로부터 숫자 10개를 받아 오름차순 정렬을 진행합니다.

---

생각 해보기

이중 선택 정렬(Double Selection Sort)

 기본적인 선택 정렬의 경우 최댓값, 혹은 최솟값을 기준으로 작성합니다. 정렬 순서도 여러 곳에서 동시에 동작하지 않고 앞(혹은 뒤)에서부터 순차적으로 나아갑니다. 그렇다면 앞과 뒤 모두에서 정렬을 시행할 수도 있을 것입니다. 이 경우 총 반복 횟수는 기존의 선택 정렬 방법의 1/2배입니다.

# 이중 선택정렬 코드

 코드 설명은 따로 하지 않습니다.

void DblSelectionSort(int* arr, size_t size) {
	size_t min, max;
	size_t start, end;
	start = 0;
	end = size - 1;

	while(start < end) {
		min = start;
		max = end;
		for (int i = start; i <= end; ++i) {
			if (arr[min] > arr[i]) min = i;
			if (arr[max] < arr[i]) max = i;
		}
        
        if(max == start) max = min;
        
		int temp;
		temp = arr[start];
		arr[start] = arr[min];
		arr[min] = temp;

		temp = arr[end];
		arr[end] = arr[max];
		arr[max] = temp;
		++start;
		--end;
	}
}

 

# index