정렬알고리즘_힙정렬을 이용한 문자열 정렬 예시 [8/8]

숫자 정렬보다는 문자열 정렬이 실제로 더 많이 사용되므로 제일 맘에 들었던 힙정렬을 이용해서 문자열 정렬을 한 번 해보겠습니다.

 

---

 

구현 방식은 완전히 같습니다. 다만 문자열을 서로 비교해서 무엇이 더 큰지만 잘 비교해주면 됩니다. strcmp() 함수가 있는걸 깜박하고 그냥 만들어 썼는데 그냥 기본 함수를 써도 무방합니다.

 

#include <stdio.h>

int compare_text(char text1[], char text2[]);
void swap(char* arr[], int x, int y);
void arr_printf(char* arr[], int size);

void main()
{
	char* arr[] = { "banana", "pine", "candy", "home", 
		"apple", "apple2", "apple3","banana", "July", "Banana"};
	int size = sizeof(arr) / sizeof(char*);

	/* 힙트리 생성 */
	for (int i = 1; i < size; i++)
	{
		int c = i;	// 현재 노드
		while (c > 0)
		{
			int p = (c - 1) / 2;  // 부모노드
			if (compare_text(arr[p], arr[i]) == 1)  // 부모노드가 작을 경우
			{
				swap(arr, p, i);
				c = p;
				continue;
			}
			else break;  // 자식노드가 작을경우 반복문 빠져나감
		}
	}
	// 정렬할 때 한번에 넣으려면 이거 하나 하려고 반복문을 한 번 더 돌려야함
	swap(arr, 0, size - 1); 
	

	/* 정렬 */
	for (int i = size - 1; i > 1; i--)
	{
		int p = 0;  // 부모노드
		while (p < i / 2)  // 부모노드는 자식노드가 있는 것만 확인하면 됨
		{			
			int c = (p * 2) + 1;  // 자식노드
			
			if (c + 1 < i && compare_text(arr[c], arr[c + 1]) == 1)
				c++;  // 자식노드 중 더 큰 문자열

			if (compare_text(arr[p], arr[c]) == 1)
				swap(arr, p, c);  // 부모노드 < 자식노드면 교체

			p = c;			
		}
		swap(arr, 0, i - 1);
	}

	arr_printf(arr, size);
}

/* 문자열 비교 */
/* parameter : 비교할 문자열 2개 */
/* return : 같은문자 == 0, 첫번 째가 작음 == 1, 두번 째가 작음 == 2 */
int compare_text(char text1[], char text2[])
{
	int i = 0;
	while (1)
	{
		if (text1[i] < text2[i])
			return 1;
		else if (text1[i] > text2[i])
			return 2;
		/* 같은 글자 + 알파일 때, 먼저 끝나는 쪽이 작은걸로 침 */
		else if (text1[i] == '\0')
			return 1;
		else if (text2[i] == '\0')
			return 2;
		i++;
	}
	return 0;
}

void swap(char* arr[], int x, int y)
{
	char* temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}


void arr_printf(char* arr[], int size)
{
	for (int i = 0; i < size; i++)
		printf("%s ", arr[i]);
}

 

---

 

만약 대소문자 구분 없이 하려면 아래와 같이 strcmp() 함수를 직접 만들어서 좀 수정해야합니다. 같은 문자끼리 대소문자에 다시 우선순위를 부여하는 것도 조금 수정하면 됩니다. 대문자가 섞이는 경우가 안섞이는 경우보다 많으니 가장 뒷쪽에 else if 구문으로 넣어줬습니다.

※ Point (대소문자 변환)
- 아마 기본함수에도 있겠으나, 직접 구현하는 것이 더 쉬울 것 같음
- "대문자 + 32" = 소문자
- "소문자 - 32" = 대문자
- 아스키코드 상 대문자와 소문자의 차이는 32이므로 더하거나 빼주면 됨

 

/* 문자열 비교 */
/* parameter : 비교할 문자열 2개 */
/* return : 같은문자 == 0, 첫번 째가 작음 == 1, 두번 째가 작음 == 2 */
int compare_text(char text1[], char text2[])
{
	int i = 0;
	char t1, t2;
	while (1)
	{
		t1 = text1[i], t2 = text2[i];	// 임시로 담아줌
		
		/* 대문자면 소문자로 치환 */
		if (t1 < 91)
			t1 += 32;
		if (t2 < 91)
			t2 += 32;

		if (t1 < t2)
			return 1;
		else if (t1 > t2)
			return 2;
		/* 같은 글자 + 알파일 때, 먼저 끝나는 쪽이 작은걸로 침 */
		else if (t1 == '\0')
			return 1;
		else if (t2 == '\0')
			return 2;
		
		/* 같은 글자라면 대소문자간 우선순위 비교 */
		else if (t1 == t2)
		{
			if (text1[i] < text2[i])
				return 1;
			else if (text1[i] > text2[i])
				return 2;
		}
		i++;
	}
	return 0;
}