예제와 함께 살펴보는 라이브러리 없이 정렬하기

모든 예제들은 백준 1181번을 c언어로 입출력 라이브러리의 printf scanf 만으로 코드들을 직접 작성해보면서 알아보겠습니다.

1181번 단어 정렬

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 256 MB 139099 58100 43410 40.354%

문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력 조건에 따라 정렬하여 단어들을 출력한다.

1. 버블정렬, 선택정렬, 삽입정렬

선택정렬은 인간적인 시선을 통한 방법으로 가장 작은 값을 맨 앞으로 보내는 것입니다. 가장 큰 값을 맨 뒤로 보내도 똑같습니다. 코드를 통해 살펴본 뒤 후술하겠지만 인간의 논리를 그대로 컴퓨터로 모방하는 것이 얼마나 비효율적인지 생각해볼 수 있습니다.

#include <stdio.h>

#define MAX_LENGTH 55
#define MAX_WORDS 20001

typedef struct
{
	char	str[55];
}	t_str;


int	ft_strlen(const char *word)
{
	int	i;

	i = 0;
	while (word[i])
		i++;
	return (i);
}

int	ft_strcmp(const char *s1, const char *s2, int n)
{
	int		i;

	i = 0;
	while (i < n && !(s1[i] == '\0' && s2[i] == '\0'))
	{
		if (s1[i] == s2[i])
			i++;
		else
			return ((unsigned char)s1[i] - (unsigned char)s2[i]);
	}
	return (0);
}

void	ft_strcpy(char *dest, const char *src)
{
	int	i;

	i = 0;
	while (src[i] != '\0')
	{
		dest[i] = src[i];
		i++;
	}
	dest[i] = '\0';
}

void	*ft_memset(void *ptr, int c, size_t n)
{
	size_t	i;

	i = 0;
	while (i < n)
		((unsigned char *)ptr)[i++] = (unsigned char) c;
	return (ptr);
}

int	compare(const char *s1,const char *s2)
{
	const int len1 = ft_strlen(s1);
	const int len2 = ft_strlen(s2);

	if (len1 != len2)
		return (len2 - len1);
	else
		return (-(ft_strcmp(s1, s2, 51)));
}

void	selection_sort(t_str *words, int start, int end)
{
	t_str	tmp;
	char	min[MAX_LENGTH];
	int		i;
	int		j;
	int		index;

	i = start;
	while (i < end)
	{
		j = i;
		ft_memset(min, 1, MAX_LENGTH - 1);
		min[MAX_LENGTH] = '\0';
		while (j < end)
		{
			if (compare(min, words[j].str) <= 0)
			{
				ft_strcpy(min, words[j].str);
				index = j;
			}
			j++;
		}
		tmp = words[index];
		words[index] = words[i];
		words[i] = tmp;
		i++;
	}
}

int	main(void)
{
	int		num;
	t_str	words[MAX_WORDS];
	int		i;

	scanf("%d", &num);
	i = 0;
	for (i = 0; i < num; i++)
	{
		scanf("%s", words[i].str);
	}
	selection_sort(words, 0,  num - 1);
	char	tmp[MAX_LENGTH] = "";
	for (i = 0; i < num; i++)
	{
		if (ft_strcmp(words[i].str, tmp, 51) == 0)
			continue ;
		ft_strcpy(tmp, words[i].str);
		printf("%s\n", words[i].str);
	}
	return (0);
}

시간 복잡도는 O(N^2) 으로 전체정렬을 배열개수만큼 순회하는 것을 알 수 있습니다. 표준 출력을 위한 라이브러리 외에 함수들을 전부 구현해서 쓰다 보니 코드가 좀 길어보입니다. 버블정렬과 삽입정렬은 간략하게 핵심코드만 봐서 진행하겠습니다.

for (int i = 0; i < COUNT - 1; i++)
{
    for (int j = 0; j < COUNT - 1 - i; j++)
    {
        if (data[j] > data[j + 1])
        {
            temp        = data[j];
            data[j]     = data[j + 1];
            data[j + 1] = temp;
        }
    }
}

버블정렬은 쌍으로 비교해가면서 마지막부터 가장 큰 값이 정렬되어 들어갑니다. 시간 복잡도는 마찬가지로 O(N^2) 이지만 선택정렬처럼 별도의 min값을 메모리에 넣거나 할 필요없이 배열만을 순회해서 짧은 배열을 정렬할때 많이 쓰입니다. 삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘으로

for(i=1; i< COUNT - 1; i++)
{
    key = arr[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
 
    for(j=i-1; j>=0 && arr[j]>key; j--) 
    {
      arr[j+1] = arr[j]; // 한 칸 뒤로 이동 
    }
    arr[j+1] = key; // 알맞은 위치에 key 삽입 
}

선택 정렬이나 버블 정렬에 비해 상대적으로 빠르지만 시간복잡도는 O(N^2) 으로 크게 차이나지 않습니다.

퀵정렬, 병합정렬

퀵정렬은 pivot을 기준으로 정렬하는 알고리즘이고 분할정복 알고리즘으로서 앞의 정렬방식들보다 훨씬 빠른 정렬속도를 가지지만 최악의 경우에는 O(N^2) 의 시간복잡도를 가진다.

#include <stdio.h>

typedef struct
{
	char	str[55];
}	t_str;


int	ft_strlen(const char *word)
{
	int	i;

	i = 0;
	while (word[i])
		i++;
	return (i);
}

int	ft_strcmp(const char *s1,const char *s2, int n)
{
	int		i;

	i = 0;
	while (i < n && !(s1[i] == '\0' && s2[i] == '\0'))
	{
		if (s1[i] == s2[i])
			i++;
		else
			return ((unsigned char)s1[i] - (unsigned char)s2[i]);
	}
	return (0);
}

void	ft_strcpy(char *dest, const char *src)
{
	int	i;

	i = 0;
	while (src[i] != '\0')
	{
		dest[i] = src[i];
		i++;
	}
	dest[i] = '\0';
}

int	compare(const char *s1,const char *s2)
{
	const int len1 = ft_strlen(s1);
	const int len2 = ft_strlen(s2);

	if (len1 != len2)
		return (len2 - len1);
	else
		return (-(ft_strcmp(s1, s2, 51)));
}

void	quick_sort(t_str *words, int start, int end)
{
	t_str	tmp;

	if (start >= end)
		return ;
	int key = start;
	int i = start + 1;
	int j = end;
	while (i <= j)
	{
		while (i <= end && compare(words[i].str, words[key].str) >= 0)
			i++;
		while (j > start && compare(words[j].str, words[key].str) <= 0)
			j--;
		if (i > j)
		{
			tmp = words[j];
			words[j] = words[key];
			words[key] = tmp;
		}
		else
		{
			tmp = words[j];
			words[j] = words[i];
			words[i] = tmp;
		}
	}
	quick_sort(words, start, j - 1);
	quick_sort(words, j + 1, end);
}

int	main(void)
{
	int		num;
	t_str	words[20001];
	int		i;

	scanf("%d", &num);
	i = 0;
	for (i = 0; i < num; i++)
	{
		scanf("%s", words[i].str);
	}
	quick_sort(words, 0,  num - 1);
	char	tmp[55] = "";
	for (i = 0; i < num; i++)
	{
		if (ft_strcmp(words[i].str, tmp, 51) == 0)
			continue ;
		ft_strcpy(tmp, words[i].str);
		printf("%s\n", words[i].str);
	}
	return (0);
}

해당 코드는 백준 알고리즘을 통과하지 못하는데 퀵정렬을 사용한다는 qsort는 통과되는 것을 보면 qsort가 퀵정렬이 아니거나 pivot을 선정하는 최적화 방법을 사용하는 퀵정렬일수도 있다.

병합정렬은 O(NlogN) 의 시간복잡도를 가지며 분할정복으로 퀵정렬처럼 상황에 따라 정렬속도가 크게 차이나가 나지 않는다.

#include <stdio.h>

typedef struct
{
	char	str[55];
}	t_str;

t_str	sort[20001];

int	ft_strlen(const char *word)
{
	int	i;

	i = 0;
	while (word[i])
		i++;
	return (i);
}

int	ft_strcmp(const char *s1,const char *s2, int n)
{
	int		i;

	i = 0;
	while (i < n && !(s1[i] == '\0' && s2[i] == '\0'))
	{
		if (s1[i] == s2[i])
			i++;
		else
			return ((unsigned char)s1[i] - (unsigned char)s2[i]);
	}
	return (0);
}

void	ft_strcpy(char *dest, const char *src)
{
	int	i;

	i = 0;
	while (src[i] != '\0')
	{
		dest[i] = src[i];
		i++;
	}
	dest[i] = '\0';
}

int	compare(const char *s1,const char *s2)
{
	const int len1 = ft_strlen(s1);
	const int len2 = ft_strlen(s2);

	if (len1 != len2)
		return (len2 - len1);
	else
		return (-(ft_strcmp(s1, s2, 51)));
}

void	merge_sort(t_str *words, int start, int middle, int end)
{
	int	i = start;
	int	j = middle + 1;
	int	k = start;
	while (i <= middle && j <= end)
	{
		if (compare(words[i].str, words[j].str) >= 0)
		{
			sort[k] = words[i];
			i++;
		}
		else
		{
			sort[k] = words[j];
			j++;
		}
		k++;
	}
	if (i > middle)
		for (int t = j; t <= end; t++)
		{
			sort[k] = words[t];
			k++;
		}
	else 
	{
		for (int t = i; t <= middle; t++)
		{
			sort[k] = words[t];
			k++;
		}
	}
	for (int t = start; t <= end; t++)
	{
		words[t] = sort[t];
	}
}

void	merge_sort2(t_str *words, int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		merge_sort2(words, start, middle);
		merge_sort2(words, middle + 1, end);
		merge_sort(words, start, middle, end);
	}
}

int	main(void)
{
	int		num;
	t_str	words[20001];
	int		i;

	scanf("%d", &num);
	i = 0;
	for (i = 0; i < num; i++)
	{
		scanf("%s", words[i].str);
	}
	merge_sort2(words, 0,  num - 1);
	t_str	tmp = words[0];
	printf("%s\n", words[0].str);
	for (i = 1; i < num; i++)
	{
		if (ft_strcmp(words[i].str, tmp.str, 51) == 0)
			continue ;
		ft_strcpy(tmp.str, words[i].str);
		printf("%s\n", words[i].str);
	}
	return (0);
}

해당코드는 확실히 시간제한에 걸리지않고 문제를 통과한다.

다음에는 힙정렬을 직접 라이브러리 없이 코드로 구성해보겠다.