정렬 알고리즘

---

정렬 알고리즘(sorting algorithm)

자료를 원하는 순서대로 배열하는 알고리즘으로 다양한 방식들이 존재하며 이를 직접 구현해본다.

1. 순차 정렬(sequential sort)

배치할 자리에 있는 수를 뒤 쪽과 비교하여 오름, 내림차순으로 정렬한다.

#include <stdio.h>

// 자리교체 함수
void Swap(int* _base1, int* _base2);
// 정렬 함수
void MySort(int* _base);
// 출력 함수
void Printf(int* _base);

int main()
{
	// 정렬할 자료
	int Arr[10] = { 5, 4, 1, 3, 6, 9, 2, 7, 10, 8 };
	// 자료의 메모리 주소
	int* Base = Arr;
	
	// 정렬 전 배열 출력
	printf("before sorting\n");
	Printf(Base);
	
	// 정렬
	MySort(Base);

	// 정렬 후 배열 출력
	printf("after sorting\n");
	Printf(Base);

	return 0;
}

void Swap(int* _base1, int* _base2)
{
	int tmp = *_base1;
	*_base1 = *_base2;
	*_base2 = tmp;
}

void MySort(int* _base)
{
	// 반복문으로 각 요소끼리 비교하여 자리교체
	for (int i = 0; i < 10; ++i)
	{
		for (int j = i + 1; j < 10; ++j)
		{
			// 부등호에 따라서 오름차순, 내림차순 결정
			if ((*(_base + i)) > (*(_base + j)))
			{
				Swap((_base + i), (_base + j));
			}
			// 각 동작이 어떻게 진행되는지 확인용 출력
			Printf(_base);
		}
	}
}

void Printf(int* _base)
{
	for (int k = 0; k < 10; ++k)
	{
		printf(" %d, ", _base[k]);
	}
	printf("\n");
}

구현이 간단하지만 각 인덱스의 모든 요소를 비교하기 때문에 연산이 많이 필요하다.

2. 버블 정렬(bubble sort)

앞에서부터 이웃하는 수를 비교하여 위치를 교환하는 작업을 반복해서 뒤에서 부터 수를 채운다.

#include <stdio.h>

// 자리교체 함수
void Swap(int* _base1, int* _base2);
// 정렬 함수
void MySort(int* _base, int _length);
// 출력 함수
void Printf(int* _base);

int main()
{
	// 정렬할 자료
	int Arr[10] = { 5, 4, 1, 3, 6, 9, 2, 7, 10, 8 };
	// 자료의 메모리 주소
	int* Base = Arr;
	// 배열 길이
	int Length = sizeof(Arr) / sizeof(int);
	
	// 정렬 전 배열 출력
	printf("before sorting\n");
	Printf(Base);
	
	// 정렬
	MySort(Base, Length);

	// 정렬 후 배열 출력
	printf("after sorting\n");
	Printf(Base);

	return 0;
}

void Swap(int* _base1, int* _base2)
{
	int tmp = *_base1;
	*_base1 = *_base2;
	*_base2 = tmp;
}

void MySort(int* _base, int _length)
{
	for (int i = 0; i < _length - 1; ++i)
	{
		for (int j = 0; j < _length - 1 - i; ++j)
		{
			// 부등호 오름, 내림차순 결정 
			if ((*(_base + j)) > (*(_base + j + 1)))
			{
				Swap((_base + j), (_base + j + 1));
			}
			Printf(_base);
		}
	}
}

void Printf(int* _base)
{
	for (int k = 0; k < 10; ++k)
	{
		printf(" %d, ", _base[k]);
	}
	printf("\n");
}

구현이 간단하지만 순서에 맞지 않는 요소들도 인접한 요소와 교환하는 과정이 생겨 하나의 요소가 가장 왼쪽에 도달하기 까지 많은 교환을 거쳐야한다. 매우 간단한 방식이지만 이런 번잡함 때문에 일반적으로 거의 쓰이지 않는다.

3. 선택 정렬(selection sort)

제일 크거나 작은 값을 찾아서 맨 앞 요소와 위치를 바꾼다.

#include <stdio.h>

// 자리교체 함수
void Swap(int* _base1, int* _base2);
// 정렬 함수
void MySort(int* _base, int _length);
// 출력 함수
void Printf(int* _base);

int main()
{
	// 정렬할 자료
	int Arr[10] = { 5, 4, 1, 3, 6, 9, 2, 7, 10, 8 };
	// 자료의 메모리 주소
	int* Base = Arr;
	// 배열 길이
	int Length = sizeof(Arr) / sizeof(int);
	
	// 정렬 전 배열 출력
	printf("before sorting\n");
	Printf(Base);
	
	// 정렬
	MySort(Base, Length);

	// 정렬 후 배열 출력
	printf("after sorting\n");
	Printf(Base);

	return 0;
}

void Swap(int* _base1, int* _base2)
{
	int tmp = *_base1;
	*_base1 = *_base2;
	*_base2 = tmp;
}

void MySort(int* _base, int _length)
{
	int min = 0;

	for (int i = 0; i < _length; ++i)
	{
		// 최소값 기준
		min = i;
		for (int j = i; j < _length; ++j)
		{
			// 최소값 보다 작은 값 찾으면 그 인덱스를 최소값으로
			if ((*(_base + min)) > (*(_base + j)))
			{
				min = j;
			}
		}
		// 기준 인덱스 값을 최소값과 교환
		Swap(_base + i, _base + min);
		Printf(_base);
	}

}

void Printf(int* _base)
{
	for (int k = 0; k < 10; ++k)
	{
		printf(" %d, ", _base[k]);
	}
	printf("\n");
}

자료의 이동 횟수가 미리 결정되지만 안정성을 만족하지 않는다. 값이 같은 경우 상대적인 위치가 변경되는 일이 생긴다.

4. 삽입 정렬(insert sort)

두 번째 인덱스부터 시작한다. 한 칸 씩 앞으로 전진하면서 바로 앞칸의 값과 비교하여 자리를 교환한다.

#include <stdio.h>

// 자리교체 함수
void Swap(int* _base1, int* _base2);
// 정렬 함수
void MySort(int* _base, int _length);
// 출력 함수
void Printf(int* _base);

int main()
{
	// 정렬할 자료
	int Arr[10] = { 5, 4, 1, 3, 6, 9, 2, 7, 10, 8 };
	// 자료의 메모리 주소
	int* Base = Arr;
	// 배열 길이
	int Length = sizeof(Arr) / sizeof(int);
	
	// 정렬 전 배열 출력
	printf("before sorting\n");
	Printf(Base);
	
	// 정렬
	MySort(Base, Length);

	// 정렬 후 배열 출력
	printf("after sorting\n");
	Printf(Base);

	return 0;
}

void Swap(int* _base1, int* _base2)
{
	int tmp = *_base1;
	*_base1 = *_base2;
	*_base2 = tmp;
}

void MySort(int* _base, int _length)
{
	// 기준이 되는 인덱스 값
	int key = 0;

	for (int i = 1; i < _length; ++i)
	{
		// 처음 key위치는 i의 위치
		key = i;
		// key 기준으로 한 칸씩 앞으로
		for (int j = i - 1; j >= 0; --j)
		{
			// key 값과 한 칸 앞의 값 비교, 자리 교환
			if ((*(_base + key)) < (*(_base + j)))
			{
				Swap(_base + key, _base + j);
				Printf(_base);
			}
			// 키 위치 한 칸씩 앞으로
			key--;
		}
	}
}

void Printf(int* _base)
{
	for (int k = 0; k < 10; ++k)
	{
		printf(" %d, ", _base[k]);
	}
	printf("\n");
}