[간단 정리] 정렬 알고리즘(버블, 선택, 삽입)

*오름차순 기준입니다

 

1. 버블정렬

첫 번째 자료부터 마지막 자료까지 인접한 자료끼리 비교해가면서 교환한다. 정렬이 되어 있지 않은 자료를 기준으로(최악) 최초에 n-1번, 그다음에 n-2번, 그다음에 n-3번, 이렇게 해서 최대 횟수는 1 + 2 + .. + (n-1) = n(n-1)/2이므로 시간복잡도는 O(N^2)이다. 최고, 평균, 최악의 경우 모두 O(N^2). 구현은 매우 간단하고 성능이 안 좋다. 교환할 때마다 3번의 임시복사가 일어나기 때문이다.

 

>>구현

#include <cstdio>
#include <cstdlib>

void BubbleSort(int arr[], int size);
void Swap(int& value1, int& value2);
void PrintArr(int arr[], int size);

int main()
{
	int arr[] = { 7, 5, 2, 3, 1, 6, 4 };
	BubbleSort(arr, _countof(arr));
	PrintArr(arr, _countof(arr));	
	return 0;
}

void Swap(int& value1, int& value2)
{
	int temp = value1;
	value1 = value2;
	value2 = temp;
}

void BubbleSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; ++i)
	{
		for (int j = 0; j < size - 1; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(arr[j], arr[j + 1]);
			}
		}
	}
}

void PrintArr(int arr[], int size)
{
	for (int i = 0; i < 7; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

 

 

2. 선택정렬

최소값을 '선택'한 다음에 맨 앞에 놓는 것이 기본 개념. 전체 배열 중에서 가장 작은 값을 찾아 맨 앞에 놓는다. 정확히는 둘이 교환한다. 그다음에는 맨 앞 원소를 뺀, 두 번째 원소부터 마지막까지의 원소 중에서 가장 작은 값을 찾아 맨 앞(전체 배열에서는 두 번째)에 놓는다. 이 과정을 반복한다. 마지막에는 하나의 원소만 남고 이미 정렬된 상태이기 때문에 수행하지 않아도 된다.  시간복잡도는, 구현에서 보면 내부 반복문이 n-1, n-2..으로 진행되며 외부 반복문은 n-1회다. 즉 (n-1) + (n-2) + .. + 1 이기 때문에 n(n-1) / 2이므로 O(N^2)이다.

 

>>구현

#include <cstdio>
#include <cstdlib>

void SelectionSort(int arr[], int size);
void Swap(int& value1, int& value2);
void PrintArr(int arr[], int size);

int main()
{
	int arr[] = { 7, 5, 2, 3, 1, 6, 4 };
	SelectionSort(arr, _countof(arr));
	PrintArr(arr, _countof(arr));
	return 0;
}

void SelectionSort(int arr[], int size)
{
	for (int i = 0; i < size - 1; ++i)
	{
		int leastIndex = i;
		for (int j = i + 1; j < size; ++j)
		{
			if (arr[leastIndex] > arr[j])
			{
				leastIndex = j;
			}
		}
		if (leastIndex != i)
		{
			Swap(arr[i], arr[leastIndex]);
		}
	}
}

void Swap(int& value1, int& value2)
{
	int temp = value1;
	value1 = value2;
	value2 = temp;
}

void PrintArr(int arr[], int size)
{
	for (int i = 0; i < 7; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

 

 

3. 삽입정렬

특정 원소를 원하는 위치에 '삽입'하는 과정을 반복해 정렬을 수행한다. 특정 원소의 선택은 두 번째 원소부터 시작해 역순으로 대소 비교를 통해 원하는 위치에 특정 원소를 삽입한다. 원하는 위치에 특정 원소를 삽입하기 위해서는 기존 원소를 한 칸씩 밀어내면 된다. 즉, 두 번째 원소를 시작으로, 첫 번째 원소와 비교하고, 세 번째 원소는 두 번째, 첫 번째 원소와 비교를 한다. 즉, 특정 원소의 인덱스보다 작은 원소는 정렬이 된 상태이기 때문에, 이미 정렬이 완료된 자료의 경우에만 내부 반복문을 수행하지 않으므로 시간 복잡도가 O(N)이며, 나머지 경우는 O(N^2)이다.

 

간단하게 {1, 2, 3}을 예로 들어 두 번째 원소인 2부터 시작해보자. 첫 번째 원소인 1이 더 작으므로 삽입은 이루어지지 않는다. 세 번째 원소인 3 역시 역순의 첫 번째 순서인 두 번째 원소가 더 작으므로 삽입이 이루어지지 않는다. 2번만에 수행이 끝난다. 버블 정렬이나 선택 정렬의 경우에는 정렬이 되어 있는 경우라도 내부 반복문을 타야 한다.

 

>>구현

#include <cstdio>
#include <cstdlib>

void InsertionSort(int arr[], int size);
void PrintArr(int arr[], int size);

int main()
{
	int arr[] = { 7, 5, 2, 3, 1, 6, 4 };
	InsertionSort(arr, _countof(arr));
	PrintArr(arr, _countof(arr));
	return 0;
}

void InsertionSort(int arr[], int size)
{
	int key = 0;
	int j = 0;
	for (int i = 1; i < size; ++i)
	{
		key = arr[i];
		for (j = i - 1; j >= 0 && key < arr[j]; --j)
		{
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = key;
	}
}

void PrintArr(int arr[], int size)
{
	for (int i = 0; i < 7; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}