선택정렬

이번에는 버블 정렬보다 쉽고 간단한 알고리즘인 선택 정렬에 대하여 얘기를 하고자 합니다. 선택 정렬은 정렬 순서에 맞게 

하나씩 선택해서 옮기는, 옮기면서 정렬이 되게하는 알고리즘인데요.

위 이미지에서 보이는 대로 정렬을 진행하면 별도의 메모리 공간이 필요하게 됩니다.. 하지만! 데이터를 하나 옮길 때마다 공간이 하나씩 비게 된다는 사실을 기반으로 아래와 같이 알고리즘을 개선시키면 별도의 메모리 공간을 마련할 필요가 없어집니다!

위의 이미지를 보시면 '교환'이라는 표현을 사용하고 있는데, 적절한 표현 방식은 아닙니다. 그래서 다음과 같이 이해할 필요가 있습니다.

"정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다."

결론적으로 교환은 맞지만 '빈 자리를 활용하는 과정에서 비롯된 교환'이라는 사실을 이해하시길 바랍니다. 

그렇지 않으면 위에서 보여드린 두 이미지의 알고리즘이 서로 다른 알고리즘처럼 느껴질 수 있답니다.

그러면 개선된 코드를 보여드리겠습니다. 

#include

void SelectionSort(int arr[], int Len) {
	int DataSave = 0;
	for (int i = 0; i < Len; i++) {
		DataSave = i;
		for (int j = 1; j < Len; j++) {
			if (arr[j] < arr[DataSave]) {
				DataSave = j;
			}
		}
		int Temp = arr[DataSave];
		arr[DataSave] = arr[i];
		arr[i] = Temp;
	}
}

int main() {
    int arr[4] = {3,4,2,1};  

    SelectionSort(arr,sizeof(arr)/sizeof(int));

    for(int i=0;i<4;i++){
        printf("%d ",arr[i]);
    }
    puts("");

    return 0;
}