[Sorting] 1. Selection Sort

What is selection sort?

총 N개의 value 중에서 j가 0 부터 N - 2 까지

1. minimum을 찾고

2. j와 min을 swap 해주고 j++ 후 '1.'부터 반복.

매우 간단한 소팅으로 눈으로 보는 편이 빠르다. {3, 5, 6, 1, 2} 라는 array를 정렬하게 되면,

3	5	6	1	2
1	5	6	3	2
1	2	6	3	5
1	2	3	6	5
1	2	3	5	6

앞에서부터 순서대로 정렬(빨간색은 정렬 완료를 의미)되는 것을 확인할 수 있습니다.

void select_sort(int *a, int N)
{
	int min, min_idx;
	int x, y;

	for (y = 0; y < N - 1; y++)
	{
		min_idx = y;
		min = a[y];

		for (x = y + 1; x < N; x++)
		{
			if (min > a[x])
			{
				min = a[x];
				min_idx = x;
			}
		}

		a[min_idx] = a[y];
		a[y] = min;
	}
}

여기서 끝나면 재미가 없기 때문에 generalized version을 만들 것입니다.

gen version이란 value의 type에 구애받지 않고 어떤 변수형이든 소팅할 수 있도록 void pointer로 선언하는 것인데,

표로 설명하겠습니다.

1. value init. (int key)	void *min = malloc(width)
2. array element (a[y])	(type)((char)base + y*width)
3. comparison (min > a[x])	fcmp(min, (char)base + xwidth) > 0
4. assign value (a[y] = min)	memcpy((char)base + ywidth, min, width)

오른쪽 코드들은 왼쪽의 의미를 코드로 나타낸 것인데 하나씩 설명해보자면,

첫 번째, 값은 선언할 때 int형으로 선언했던 것을 void pointer로 선언하고 메모리를 할당해준 것입니다.

* void pointer와 memory alloc에 대해서는 나중 게시글에 업로드

두 번째, 배열 요소를 나타낼 때 포인터의 형태로 나타낸 것인데 간단히 설명하자면 void pointer이기 때문에 사용할 때는 앞에 type casting을 해주는 것입니다.

여기서 모든 변수형에 대한 소팅이라면서 왜 (char*)을 이용했나?라는 의문이 생길 수 있는데, 이는 각 변수들의 size를 알면 간단하게 파악할 수 있습니다.

char	1 byte
int	4 bytes
float	4 bytes
double	8 bytes

간단하게 4가지 변수형만 가져와서 보자면, 메모리 크기를 1byte기준으로 4배나 8배를 하면 다른 변수형의 크기를 맞추기 쉽기 때문에 char*을 이용하는 것입니다.

세 번째, 기존에 없는 함수 fcmp가 나왔는데 이는 compare function으로 사용자가 직접 정의하는 함수로서 정렬을 할 data의 변수에 따라 customize를 해주면 됩니다. 예를 들어 int형의 data를 다룰 것이라면

int intcmp(const void *a, const void *b)
{
	return (*(int *)a - *(int *)b);
}

을 이용해서 비교해줍니다.

네 번째, value를 pointer의 형태로 주었기 때문에 값을 이동시킬 때는 단순히 '=' 연산자로 가능한 것이 아니라 memory의 copy를 통해서 실현할 수 있기 때문에 memcpy()함수를 사용했습니다.

위의 4가지 규칙을 이용해서 selection sort를 generalize 시켜보면,

void gen_select_sort(void *base, size_t nelem, size_t width, int(*fcmp)(const void *, const void *))
{
    void *min;
    int min_idx;
    int x, y;

    min = malloc(width);

    for (y = 0; y < nelem - 1; y++)
    {
        min_idx = y;
        memcpy(min, (char *)base + y*width, width);

        for (x = y + 1; x < nelem; x++)
        {
            if (fcmp(min, (char *)base + x*width) > 0)
            {
                memcpy(min, (char *)base + x*width, width);
                min_idx = x;
            }
        }

        memcpy((char *)base + min_idx*width, (char *)base + y*width, width);
        memcpy((char *)base + y*width, min, width);
    }

    free(min);
}

쉽게 변환이 되었습니다. (memory를 할당해주었기 때문에 꼭 free(min)을 통해서 메모리 free를 시켜줘야 합니다.)

굳이 왜 generalized version을 사용해야 하는가?라는 의문이 생길 수 있는데, 속도면에서는 변수형을 지정해준 sort가 빠르겠지만 실제로 사용할 때 value의 type에 따라 int_selection, string_selection... 모두 만들어주는 것은 매우 비효율적이기 때문에 generalized를 통해 이를 간편하게 만들 수 있습니다.

질문은 댓글로