[C/C++] 버블 정렬, 카운트 정렬

알고리즘 복습과 C 공부를 동시에 하기 위해 예전에 했던거 복습

위의 두줄은 버블 정렬이고 아래 두줄은 카운팅정렬이다.

1. 버블 정렬

배열 내에서 인접한 두자리를 비교하면서 정렬하는 방법이다.

정렬중에 가장 쉽게 구현할수 있다.

여기서 가끔 헷갈리는 건 이중 반복문에서 범위를 지정하는 부분이다.

항상 앞에서부터 차례대로 비교하면서 뒤에 차곡차곡 쌓는 느낌으로만 기억한다.

(바깥 반복문은 정렬할 위치를 지정하고, 안쪽 반복문에서는 실제 비교 및 정렬을 수행한다.)

void bubble(int *arr, int arr_size)
{
	int tmp;
	for (int i = arr_size - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[j+1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

2. 카운팅 정렬

정렬할 수들중 최대 값이 작은 경우 빠르게 수행할수 있는 정렬이다. (최소, 최대 범위가 작은 경우도 가능할것이다)

void counting(int* arr, int *arr_sort, int arr_size, int max_val)
{
	int* count = (int*)calloc(max_val + 1, sizeof(int));
	// counting
	for (int i = 0; i < arr_size; i++)
	{
		count[arr[i]]++;
	}
	//accumulating
	for (int i = 1; i < arr_size; i++)
	{
		count[i] += count[i - 1];
	}
	// sorting
	for (int i = arr_size - 1; i >= 0; i--)
	{
		arr_sort[--count[arr[i]]] = arr[i];
	}
    free(count);
}

누적합을 사용해서 같은 숫자의 순서가 바뀌지 않지만, 순서가 크게 필요하지 않는 경우 조금 다른 방식으로 고쳐서 사용할수 있을듯하다.

3. 알고리즘 외 새로 배운것

배열의 크기를 변수로 사용하기 위해 동적 배열을 사용했다.

malloc과 calloc이 있는데 ma;lloc은 자리만 선언하기 때문에 memset으로 초기화를 하거나 값을 직접 넣어줘야하고, calloc은 원하는 값으로 직접 지정해줄수 있다.

사용처가 다르니 함수에 들어가는 인자도 조금 다르다

동적 할당을 하다보면 계속 포인터가 들어가는데 배열을 사용하면서 더 연습해야겠다.

 

4. 전체 코드

 

#define _CRT_SECURE_NO_WARNING
#include<cstdio>
#include<cstdlib>

void bubble(int *arr, int arr_size)
{
	int tmp;
	for (int i = arr_size - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[j] > arr[j+1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

void counting(int* arr, int *arr_sort, int arr_size, int max_val)
{
	int* count = (int*)calloc(max_val + 1, sizeof(int));
	// counting
	for (int i = 0; i < arr_size; i++)
	{
		count[arr[i]]++;
	}
	/*printf("count:\n");
	for (int i = 0; i < max_val+1; i++)
	{
		printf("%d\t", count[i]);
	}
	printf("\n");*/
	//accumulating
	for (int i = 1; i < arr_size; i++)
	{
		count[i] += count[i - 1];
	}
	/*printf("acc_count:\n");
	for (int i = 0; i < max_val+1; i++)
	{
		printf("%d\t", count[i]);
	}
	printf("\n");*/
	// sorting
	for (int i = arr_size - 1; i >= 0; i--)
	{
		arr_sort[--count[arr[i]]] = arr[i];
	}
}

int main() {
	int arr[] = {10,20,62,73,34,26,1,63,812,26,4,42,3};
	int arr_len = sizeof(arr) / sizeof(int);
	for (int i = 0; i < arr_len; i++)
	{
		printf("%d\t", arr[i]);
	}
	printf("\n");
	bubble(arr, arr_len);
	for (int i = 0; i < arr_len; i++)
	{
		printf("%d\t", arr[i]);
	}
	printf("\n");
	int arr2[] = { 0,4,1,3,1,2,4,1 };
	int arr2_len = sizeof(arr2) / sizeof(int);
	int* arr2_sort = (int*)malloc(arr2_len * sizeof(int));
	for (int i = 0; i < arr2_len; i++)
	{
		printf("%d\t", arr2[i]);
	}
	printf("\n");
	counting(arr2, arr2_sort, arr2_len, 4);
	for (int i = 0; i < arr2_len; i++)
	{
		printf("%d\t", arr2_sort[i]);
	}
	printf("\n");
	free(arr2_sort);
	return 0;
}