과제 3번은 강의시간에 배운 findIdxOfMin()함수와 printArr()함수를 이용하여 정수형 배열 {9,1,6,8,4,3,2,0}을 선택정렬 방식으로 오름차순으로 정렬하는 함수 selectionSorting()을 작성하는 것이었습니다.

findIdxOfMin()함수는 다음과 같았고,

int findIdxOfMin(int* ptr, int len){
	int min=0;
	for(int i=1;i<len;i++){
		if(ptr[min]>ptr[i]) min=i;
	}
	return min;
}

printArr()함수는 다음과 같았습니다.

void printArr(int* ptr,int len){
	for(int i=0;i<len;i++){
		printf("arr[%d]:%d\n",i,ptr[i]);
	}
}

지금까지 두 수를 바꾸기 위해서 swap()함수를 이용했는데요, 이번 과제에서는 이 대신에 #define이라는 전처리문을 이용해봤습니다.

#define은 단어의 뜻 그대로 무언가를 정의하는 전처리문인데요, #define A B는 A를 B로 정의한다는 의미를 갖습니다.

swap을 #define을 이용해서 구현한다면 #define SWAP(a,b) {int t;t=a;a=b;b=t;}인데요,

#include <stdio.h>

#define SWAP(a,b) {int t;t=a;a=b;b=t;}

// 생략

와 같이 보통 #include 밑에 작성하여 사용합니다.

다음으로 선택정렬의 알고리즘은 아래와 같습니다. (출처:위키피디아)

1. 주어진 리스트 중에 최솟값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

배열 {9,1,6,8,4,3,2,0}이 있을 때 선택정렬을 한 번 적용하면 {0,1,6,8,4,3,2,9}가 되고

여기서 한 번 더 적용하면 {0,1,6,8,4,3,2,9}, 한 번 더 적용하면 {0,1,2,8,4,3,6,9}가 되는데요,

차례로 설명하자면 {9,1,6,8,4,3,2,0}에서 맨 앞의 값은 9이고 리스트 중 가장 작은 값은 0입니다. 따라서 9와 0을 교체합니다.

{0,1,6,8,4,3,2,9}이 됐고 0은 정렬이 됐으니 그 다음의 맨 앞의 값은 1입니다. (0을 제외한) 리스트 중 가장 작은 값도 1입니다.

알고리즘 상에서 둘을 교체하긴 하지만 변하는건 없고 배열은 그대로 {0,1,6,8,4,3,2,9}입니다.

0과 1 다음의 맨 앞의 값은 6이고 (0과 1을 제외한) 리스트 중 가장 작은 값은 2입니다. 따라서 6과 2를 교체합니다.

이러한 과정을 반복하는 것이 선택정렬 알고리즘이고 결과적으로는 {0,1,2,3,4,6,8,9}의 배열이 완성됩니다.

이를 위해 함수 selectionSorting()를 작성해보면,

selectionSorting()은 특별한 반환이 필요하지 않으므로 타입을 void로 정하고 매개변수는 int* ptr과 int len으로 설정해줍니다.

int* ptr은 배열을 받기 위함이고 int len은 이 배열의 길이를 받기 위함입니다.

void selectionSorting(int* ptr, int len){

}

findIdxOfMin()에서 return(반환)된 값을 저장하기 위한 정수형 변수 int min을 선언해줍니다.

void selectionSorting(int* ptr, int len){
	int min;
}

배열의 모든 원소를 정렬해야하기에 반복문을 이용해야하는데요, 반복문은 루프변수의 값이 0에서 len까지 진행되는것이 아니라 0에서 len-1까지 진행됩니다.

이유는 알고리즘을 살펴보면 알 수 있는데요, len-1번째의 선택정렬이 적용된다면 len번째의 정렬은 필요가 없어지기 때문입니다.

따라서 루프변수를 선언하고 반복문을 적용한다면,

void selectionSorting(int* ptr, int len){
	int min;
	int i;
	for(i=0;i<len-1;i++){
	
	}
}

입니다.

다음으로는 반복문 내에서 min의 값을 정하고 SWAP을 이용하는것을 작성해야하는데, min의 값을 정하는것이 이번 과제의 핵심이고 가장 어려운 부분입니다.

우선 답은 min=i+findIdxOfMin(&ptr[i],len-i);입니다.

이를 보고 크게 세 가지의 의문점이 들 수 있습니다.

1. &ptr[i]
2. len-i
3. min=i+findIdxOfMin();

첫쨰로 &ptr[i]는 ptr의 i번째 요소의 주소를 넘겨주기 위함입니다.

i가 0일때는 0번째 요소의 주소를 넘기는 식으로 선택정렬을 배열의 모든 원소에 대해 적용하기 위해서 사용합니다.

둘째로 len-i는 선택정렬이 진행될때마다 선택정렬을 적용할 범위가 줄어들어서인데,

예시로

printArr(&arr[0],len); // arr[0]~arr[7] 출력
printArr(&arr[1],len-1); // arr[1]~arr[7] 출력
printArr(&arr[2],len-2); // arr[2]~arr[7] 출력

마지막으로 min=i+findIdxOfMin();을 설명하자면 알고리즘에서 정렬된 값을 제외하고 나머지 값들을 정렬할 때 배열의 인덱스를 정하기 위함입니다.

예시로

{9,1,6,8,4,3,2,0}인 상황에서

i==0이라면,
min=0+findIdxOfMin(&ptr[0],len);
(findIdxOfMin에서) return 7;
min=0+7;
SWAP(ptr[7],ptr[0]);

{0,1,6,8,4,3,2,9}인 상황에서

i==1이라면,
min=1+findIdxOfMin(&ptr[1],len-1);
(findIdxOfMin에서) return 0;
min=1+0;
SWAP(ptr[1],ptr[1]);

{0,1,6,8,4,3,2,9}인 상황에서

i==2이라면,
min=2+findIdxOfMin(&ptr[2],len-2);
(findIdxOfMin에서) return 4;
min=2+4;
SWAP(ptr[6],ptr[2]);

{0,1,2,8,4,3,6,9}이 됩니다.

따라서 반복문 내부를 완성시키면,

void selectionSorting(int* ptr,int len){
	int min;
	for(int i=0;i<len-1;i++){
        min=i+findIdxOfMin(&ptr[i],len-i); 
        SWAP(ptr[min],ptr[i]);
    }
}

으로 selectionSorting()이 완성됩니다.