Word of GOD

하나님이 세상을 이처럼 사랑하사 독생자를 주셨으니 이는 그를 믿는 자마다 멸망하지 않고 영생을 얻게 하려 하심이라
요한복음 3장 16절

정렬 알고리즘 개요

데이터를 특정한 조건에 따라 일정한 순서가 되도록 나열하는 것을 정렬이라고 합니다. 정렬 알고리즘은 프로그래밍에 있어 가장 기초적이며 또한 매우 중요한 알고리즘입니다. 정렬 알고리즘은 자료를 탐색함에 있어 필수적입니다. 

정렬 알고리즘을 사용할 때, 정렬시켜야 하는 대상을 "레코드(Record)"라고 부르고 레코드는 "필드(Field)"라고 하는 단위로 나누어지니다. 이때 레코드와 레코드를 식별해주는 필드를 "키(Key)"라고 부릅니다.

정렬 알고리즘 종류

현재까지 개발된 정렬 알고리즘은 매우 많으나, 모든 경우에서 최적의 성능을 보이는 알고리즘은 존재하지 않습니다. 즉, 상황에 맞는 알고리즘을 택하여 사용해야 합니다. 이때 효율을 평가하는 기준은 정렬을 위해 필요한 "비교 연산의 횟수"와 "이동 연산의 횟수"입니다. 빅오 표기법을 통해 근사적으로 이들을 추정하며 자신의 상황에 맞는 알고리즘을 선택해야 합니다.

현재까지 개발된 정렬 알고리즘은 매우 많기에 이 포스팅에서 다 적을 수는 없고 대표적인 정렬 알고리즘만 살펴보겠습니다. 기본적으로 정렬 알고리즘은 다음과 같이 분류할 수 있습니다.

  • 단순하지만 비효율적인 방법: 버블 정렬, 삽입 정렬, 선택 정렬 등
  • 복잡하지만 효율적인 방법: 합병 정렬, 퀵 정렬, 기수 정렬 등

또 내부 정렬과 외부 정렬로도 구분할 수 있습니다.

  • 내부 정렬: 정렬하기 전, 모든 데이터가 메인 메모리에 올라와 있는 정렬
  • 외부 정렬: 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 하는 정렬

그리고 정렬 알고리즘을 공부하기 전 알아야하는 중요한 개념이 있습니다. 바로 "안정성(Stability)"입니다. 안정성이란 입력 데이터에 동일한 키값을 가지는 레코드가 여러 개 존재할 때, 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않는다는 것입니다. 반대로 "불안정성(Unstability)"이란 같은 키값을 가지는 레코드들이 정렬 후에 위치가 바뀌게 되는 것입니다.

 

예시로, [20, 20, 10, 30]이라는 정렬되지 않은 레코드들이 있다고 합시다. 이를 정렬하고 나서 [10, 20, 20, 30]이 되면 안정적인 것이고 정렬 후, [10, 20, 20, 30]이 되면 불안정하다는 것입니다.

 

정렬의 안정성이 필수적으로 요구되는 경우에는 "삽입 정렬", "버블 정렬", "합병 정렬" 등을 사용해야 합니다.

이제부터 본격적인 정렬 알고리즘들을 살펴보도록 하겠습니다.

버블 정렬 (Bubble Sort)

버블 정렬 방법

n개의 원소를 정렬하고자 할 때, 버블 정렬은 1번째 원소와 2번째 원소, 2번째 원소와 3번째 원소... 그리고 (n-1)번째 원소와 n번째 원소까지 정렬한 후, 다시 1번째 원소와 2번째 원소, 2번째 원소와 3번째 원소... 그리고 이번에는 (n-2)번째 원소와 (n-1)번째 원소와 정렬한 후, 다시 또 처음으로 돌아가 계속하여 정렬하여 최대 $\frac{n(n-1)}{2}$번 정렬하게 되는 것입니다. 

버블 정렬 구현 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )

int list[MAX_SIZE];
int n;

void bubble_sort(int list[], int n)
{
	int i, j, temp;
	for (i = n - 1; i>0; i--) {
		for (j = 0; j<i; j++)
			/* 앞뒤의 레코드를 비교한 후 교체 */
			if (list[j]>list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}

int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

	bubble_sort(list, n); // 선택정렬 호출
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

버블 정렬의 시간 복잡도 분석

버블 정렬의 시간 복잡도를 분석해보도록 하겠습니다.

버블 정렬의 시간 복잡도는 최선의 경우, 최악의 경우, 평균의 경우 모두 항상 일정하고 다음과 같은 결과가 나오게 됩니다. 

$$ \sum\limits_{i = 1}^{n-1} \ i = \frac{n(n-1)}{2} = O(n^2) $$ 

그 이유는 바로 정렬이 되어있든 되어있지 않든 교환이 일어나지 않아도 비교는 계속해서 진행되기 때문입니다.

 

그렇기에 버블 정렬은 속도가 매우 느리고 비효율적인 방법입니다. 코드가 짧고 구현하기가 간단하다는 이점 외에는 장점이 거의 없는 알고리즘입니다. 그렇기에 가능하면 버블 정렬을 사용하지 말아야 합니다.

선택 정렬 (Selection Sort)

선택 정렬 방법

n개의 원소를 정렬하고자 할 때, 선택 정렬은 버블 정렬과 달리 1번째 원소부터 마지막 원소까지 확인하여 가장 작은 원소를 1번째 원소로 배정하고, 2번째 원소부터 마지막 원소까지 확인하여 가장 작은 원소를 2번째 원소로 배정하고, 3번째 ... 이렇게 (n-1)번 반복하여 정렬을 완료하는 정렬 방법입니다.

선택 정렬 구현 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t) = (x), (x) = (y), (y) = (t) )

int list[MAX_SIZE];
int n;

void selection_sort(int list[], int n)
{
	int i, j, least, temp;
	for (i = 0; i < n - 1; i++) {
		least = i;
		for (j = i + 1; j < n; j++) 	// 최소값 탐색
			if (list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);
	}
}
//
int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

	selection_sort(list, n); // 선택정렬 호출
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

선택 정렬의 시간 복잡도 분석

선택 정렬의 시간 복잡도를 분석해보도록 하겠습니다. 

선택 정렬의 시간 복잡도 또한 최선의 경우, 최악의 경우, 평균의 경우 모두 항상 일정하고 다음과 같은 결과가 나오게 됩니다. (버블 정렬과 같은 시간 복잡도를 가집니다.)

$$ \sum\limits_{i = 1}^{n-1} \ i = \frac{n(n-1)}{2} = O(n^2) $$ 

그러나, 선택 정렬은 버블 정렬과 달리 매번 자료의 SWAP을 반복하지 않고 오직 자료의 이동 횟수는 $3(n-1)$번으로 고정되어 있기에 버블 정렬보다는 대략 2배 정도 빠릅니다.

 

다만, 선택 정렬은 최소값이 자기 자신이면 자료 이동을 하지 않기에 안정성을 만족하지 않으며 $3(n-1)$번이라는 이동 횟수도 상당히 큰 편이기에 속도가 그리 빠르진 않다는 단점이 있습니다.

삽입 정렬 (Insertion Sort)

삽입 정렬 방법

n개의 원소를 정렬하고자 할 때, n번째 원소를 1부터 n-1까지와 비교하여 어떤 위치가 적절한지 판단한 후 그 위치에 삽입하고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 정렬 방식입니다. 자료들을 뒤로 밀어내는 방식이기에 자료구조에 따라 뒤로 밀어내는데 걸리는 시간이 다릅니다.

삽입 정렬 구현 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10

int list[MAX_SIZE];
int n;

// 삽입정렬
void insertion_sort(int list[], int n)
{
	int i, j, key;
	for (i = 1; i<n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0 && list[j]>key; j--)
			list[j + 1] = list[j]; /* 레코드의 오른쪽 이동 */
		list[j + 1] = key;
	}
}
//
int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력
		list[i] = rand() % 100; // 난수 발생 범위 0~99

	insertion_sort(list, n); // 삽입정렬 호출
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

삽입 정렬의 시간 복잡도 분석

삽입 정렬의 시간 복잡도를 분석해보도록 하겠습니다.

입력 자료가 이미 정렬되어 있는 경우(최선의 경우)에는 외부 루프를 n-1번 실행되는 동안 1번만 비교하고 2번만 이동하기에 비교횟수는 (n-1), 이동횟수는 2(n-1)이 되어 시간 복잡도는 $O(n)$이 됩니다.

입력 자료가 역순인 경우(최악의 경우)에는 각 단계마다 앞에 있는 자료들이 뒤로 한 칸씩 이동해야하므로 다음의 시간 복잡도를 가지게 됩니다.

$$ \sum\limits_{i = 1}^{n-1} \ i = 1+2+ \cdots + (n-1) = \frac{n(n-1)}{2} = O(n^2) $$ 

삽입 정렬은 많은 레코드들의 이동을 포함하기에, 레코드 양이 많고 레코드 크기가 클 때는 적합하지 않습니다. 그러나 레코드의 수가 적을 경우에는 알고리즘이 단순하기에 다른 복잡한 정렬 방법보다 유리합니다. 그리고 삽입 정렬은 안정성을 가진 정렬 방법이고, 레코드가 대부분 정렬되어있을 때 삽입 정렬은 빛을 발합니다.

합병 정렬 (Merge Sort)

합병 정렬 방법

n개의 원소를 정렬하고자 할 때, 먼저 리스트 안의 원소의 개수가 1 또는 0이 될 때까지 하나의 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬하고, 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 방법입니다. 합병 정렬은 다음의 단계들로 이루어집니다.

  • 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 "분할"을 진행한다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다.

예시를 통하여 이 개념들을 더 자세히 알아보겠습니다. [27, 10, 12, 20, 25, 13, 15, 22] 라는 배열이 있다고 가정하겠습니다.

  • 분할(Divide): 배열을 [27, 10, 12, 20]과 [25, 13, 15, 22]의 2개의 부분 배열로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬하여 [10, 12, 20, 27]과 [13, 15, 22, 25]를 얻는다.
  • 결합(Combine): 부분 배열을 통합하여 [10, 12, 13, 15, 20, 22, 25, 27]를 얻는다.

이때 2번째 과정인 정복을 더 알아볼 필요가 있습니다. 이 과정에서 "부분 배열을 정렬한다"라고 하는데, 이 과정은 사실 순환적인 분할 과정이 들어가는 것입니다. 즉, 부분 배열을 또 분할하여 원소의 개수가 1개가 될 때까지 분할해야 정렬 과정을 진행할 수 있는 것입니다. 결국 합병 정렬의 "정렬"은 결합 과정에서 일어나는 것입니다.

 

합병 정렬 구현 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10
int sorted[MAX_SIZE];   // 추가 공간이 필요

/* i는 정렬된 왼쪽 리스트에 대한 인덱스
		j는 정렬된 오른쪽 리스트에 대한 인덱스
		k는 정렬될 리스트에 대한 인덱스 */
void merge(int list[], int left, int mid, int right)
{
	int i, j, k, l;
	i = left;  j = mid + 1;  k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i>mid)	/* 남아 있는 레코드의 일괄 복사 */
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else	/* 남아 있는 레코드의 일괄 복사 */
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	/* 배열 sorted[]의 리스트를 배열 list[]로 재복사 */
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
}

void merge_sort(int list[], int left, int right)
{
	int mid;
	if (left<right) {
		mid = (left + right) / 2;     /* 리스트의 균등 분할 */
		merge_sort(list, left, mid);    /* 부분 리스트 정렬 */
		merge_sort(list, mid + 1, right); /* 부분 리스트 정렬 */
		merge(list, left, mid, right);    /* 합병 */
	}
}

int main() {
    int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100; 

	merge_sort(list, 0, n-1); // 합병 정렬 호출 
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
  
}

합병 정렬의 시간 복잡도 분석

합병 정렬의 시간 복잡도를 분석해보도록 하겠습니다.

합병 정렬을 진행하는 배열의 크기가 $N = 2^k$라고 하면 합병 단계는 k번 일어나게 되고 $ k = \log_{2}n $임을 쉽게 알 수 있습니다. 일반적인 합병의 경우 최대 n번 비교 연산이 필요한데, 합병 단계는 k번만큼 있으므로 비교 연산은 최대 $n\log_{2}n$번 필요하게 됩니다. 이동 연산의 경우, 총 부분 배열에 들어있는 요소의 개수가 n이면 레코드의 이동은 2n번 발생하기에 이동 연산은 총 $2n\log_{2}n$번 필요합니다.

 

즉, 합병 정렬의 시간 복잡도는 $O(n \log n)$입니다. 합병 정렬은 안정적인 정렬 방법이며 데이터의 분포에 영향을 덜 받는다는 장점이 있습니다. 그렇기에 최악, 평균, 최선의 경우 상관없이 모두 동일한 시간복잡도 결과가 나옵니다. 다만 합병 정렬은 임시 배열이 필요하며, 레코드의 크기가 큰 경우 이동 횟수가 많아 매우 큰 시간적 낭비가 생기게 됩니다. 다만 연결 리스트로 합병 정렬을 할 경우 이 시간적 낭비의 문제는 해결됩니다.

퀵 정렬 (Quick Sort)

퀵 정렬 방법

합병 정렬과 달리 퀵 정렬 방식은 비균등하게 분할하는 방식입니다. n개의 원소를 정렬하고자 할 때, 먼저 한 원소를 선택해 피벗으로 삼습니다. 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮겨집니다. 그렇게 피벗을 기준으로 작은 부분과 큰 부분이 구분되면 각각의 부분(큰 부분과 작은 부분)에서 다시 새로운 피벗을 설정하여 같은 과정을 반복합니다. 이를 Partition이라고 합니다. 그렇게 각각의 크기가 0이나 1이 될 때까지 반복합니다. 이렇게 파티션 스텝을 반복하여 정렬하는 방법이 퀵 정렬 방법입니다.

퀵 정렬 구현 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

int list[MAX_SIZE];
int n;

int partition(int list[], int left, int right)
{
	int pivot, temp;
	int low, high;

	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do
			low++;
		while (list[low]<pivot);
		do
			high--;
		while (list[high]>pivot);
		if (low<high) SWAP(list[low], list[high], temp);
	} while (low<high);

	SWAP(list[left], list[high], temp);
	return high;
}

void quick_sort(int list[], int left, int right)
{
	if (left<right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

//
int main(void)
{
	int i;
	n = MAX_SIZE;
	srand(time(NULL));
	for (i = 0; i<n; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100; 

	quick_sort(list, 0, n-1); // 퀵정렬 호출 
	for (i = 0; i<n; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

퀵 정렬의 시간 복잡도 분석

퀵 정렬의 시간 복잡도를 분석해보도록 하겠습니다.

퀵 정렬은 합병 정렬과 마찬가지로 비교 연산을 $n \log_{2}n $번 실행하게 되어 $O(n \log_{2}n)$의 복잡도를 가집니다. 그러나 최악의 경우 퀵 정렬의 순환 호출 깊이가 n이 되고 한 단계에서 평균 n번의 비교 연산이 진행되어 $O(n^2)$의 복잡도를 가지게 됩니다.

 

퀵 정렬은 평균적인 경우 시간 복잡도가 $O(n \log_{2}n)$로 나타나며, 같은 복잡도를 가진 다른 알고리즘과 비교했을 때 가장 빠른 것으로 나타납니다. 그 이유는 바로 퀵 정렬이 불필요한 데이터 이동을 줄이고 한 번 결정된 피벗들이 연산에서 제외되기 때문입니다. 그렇기에 퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않습니다. 그러나 정렬된 리스트에 대해서는 수행시간이 더 많이 걸리기도 하고, 또한 불안정한 정렬 기법이라는 단점이 있습니다.

기수 정렬 (Radix Sort)

기수 정렬 방법

지금껏 알아본 정렬 방법들은 모두 레코드들을 비교하여 정렬하기에, 비교가 불가능한 레코드들은 정렬이 불가능합니다. 그러나 기수 정렬은 레코드를 비교하지 않고 정렬하는 색다른 기법입니다. 기수 정렬은 데이터의 각 자리수의 값에 따라서 정렬하는 방법입니다.

 

예를 들면 다음과 같습니다. [18, 53, 29, 71, 42, 92, 68, 36]이라는 숫자들이 있다고 하면, 1의 자리수와 10의 자리수를 따로 사용하여 정렬을 진행하는 것입니다. 1의 자리수로 먼저 정렬하면 [71, 42, 92, 53, 36, 18, 68, 29]로 정렬이 됩니다. 그 후, 10의 자리수로 정렬하면 [18, 29, 36, 42, 53, 68, 71, 92]로 정렬이 되어 오름차순 정렬이 완료됩니다. 

 

지금 본 것과 같이 가장 낮은 자리수부터 비교하는 방법은 LSD(Least Significant Digit)이고 가장 높은 자리수부터 비교하는 방법은 MSD(Most Significant Digit)입니다. 기수 정렬 방법에서는 각각 버킷(데이터를 정렬하기 위해 필요한 저장공간)에서 먼저 들어간 숫자들은 먼저 나와야 하기에 버킷은 "큐"로 구현이 됩니다. 또한 버킷의 개수는 키의 표현 방법과 관련이 있는데 키를 2진법으로 표현한다면 버킷은 2개만 있으면 되고, 키를 알파벳으로 표현한다면 버킷은 26개 있으면 됩니다. 

 

여기서 알 수 있는 것은 기수 정렬 방법은 레코드들의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어야 한다는 것이며, 추가적인 메모리(버킷)를 필요로 한다는 것입니다.  

기수 정렬 구현 (C언어)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_QUEUE_SIZE 100
#define BUCKETS 10
#define DIGITS  4
#define  SIZE 10

typedef int element;
typedef struct { // 큐 타입
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} QueueType;

// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 공백 상태 검출 함수
void init_queue(QueueType *q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

void radix_sort(int list[], int n)
{
	int i, b, d, factor = 1;
	QueueType queues[BUCKETS];

	for (b = 0; b<BUCKETS; b++) init_queue(&queues[b]);  // 큐들의 초기화

	for (d = 0; d<DIGITS; d++) {
		for (i = 0; i<n; i++)			// 데이터들을 자리수에 따라 큐에 삽입
			enqueue(&queues[(list[i] / factor) % 10], list[i]);

		for (b = i = 0; b<BUCKETS; b++)  // 버킷에서 꺼내어 list로 합친다.
			while (!is_empty(&queues[b]))
				list[i++] = dequeue(&queues[b]);
		factor *= 10;					// 그 다음 자리수로 간다.
	}
}

int main(void)
{
	int list[SIZE];
	srand(time(NULL));
	for (int i = 0; i<SIZE; i++)      	// 난수 생성 및 출력 
		list[i] = rand() % 100;

	radix_sort(list, SIZE); // 기수정렬 호출 
	for (int i = 0; i<SIZE; i++)
		printf("%d ", list[i]);
	printf("\n");
	return 0;
}

기수 정렬의 시간 복잡도 분석

기수 정렬의 시간 복잡도를 분석해보도록 하겠습니다. 기수 정렬을 할 입력 리스트가 n개의 정수를 가지면 알고리즘의 내부 루프는 n번 반복되고, 각각의 정수가 k개의 자리수를 가진다면 알고리즘의 외부 루프는 k번 반복됩니다. 그렇기에 기수 정렬의 시간 복잡도는 $O(kn)$입니다. 기수 정렬 알고리즘의 시간복잡도는 k에 비례하기에 알고리즘의 실행 시간은 정수의 자리수와 관련이 있습니다.

 

기수 정렬은 다른 정렬 알고리즘에 비해 매우 빠르게 정렬을 마칠 수 있으나, 정렬에 사용되는 키값이 숫자로 표현되어야 한다는 제한이 있습니다. 한글이나 한자 등으로 이루어진 키값을 정렬한다면 매우 많은 버킷이 필요하게 되기 때문입니다. 

정렬 알고리즘 비교

각각의 정렬 알고리즘들을 시간 복잡도와 정렬 수행 시간(정수 60,000개)을 비교해보면 다음과 같습니다. 결국 중요한 것은 모든 상황에 최적인 정렬 알고리즘은 없기에 자신이 겪고 있는 상황에 맞춰서 정렬 알고리즘을 선택하면 됩니다. 내가 안정성을 중시해야 하는지?, 쉬운 알고리즘 구현이 가장 중요한지?, 알고리즘이 복잡하더라도 빠른 수행 속도를 원하는지? 등을 고려하면 됩니다.

 

알고리즘 최선 평균 최악  실행 시간
(단위: sec)
버블 정렬 $O(n^2)$ $O(n^2)$ $O(n^2)$ 22.894
선택 정렬 $O(n^2)$ $O(n^2)$ $O(n^2)$ 10.842
삽입 정렬 $O(n)$ $O(n^2)$ $O(n^2)$ 7.438
합병 정렬 $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ 0.026
퀵 정렬 $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(n^2)$ 0.014
기수 정렬 $O(kn)$ $O(kn)$ $O(kn)$  
반응형
저작자표시

최근 댓글

최근 글

인기 글

©2023 Swkinah | All Rights Reserved

loading

티스토리툴바