정렬 알고리즘 요약정리

😂 들어가며

기술면접을 대비하기 위해 공부를 하던중, 정렬 알고리즘에 관한 질문이 있었는데 쉽게 답변하지 못했다. 분명 코딩테스트 준비를 하면서 여러가지 정렬 알고리즘에 대해 살펴보고 구현해보았었는데 기록으로 남겨두지 않으니 휘발된 것 같다. 이번 기회에 기본적인 정렬 알고리즘들에 대해 정리해보고자 한다.

정렬 알고리즘?

먼저 정렬 알고리즘이란 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘을 뜻한다.
효율적인 정렬을 위해 정렬 알고리즘이 필요하다고 할 수 있다.
정렬시 고려할 사항으로는 시간 복잡도, 메모리 사용량, 안정성(safety가 아니라 stable -> 데이터의 순서가 바뀌지 않느냐 여부 문제) 등이 있다.

모든경우에 대해 최선의 정답을 내는 알고리즘은 없으므로 정렬 알고리즘의 특성에 대해 잘 알아두고 적절한 상황에 맞는 알고리즘을 택해야한다.

기초적인 정렬 알고리즘 5개에 대해 살펴보자.

버블 정렬(Bubble Sort)

버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다.
버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다.
시간 복잡도가 최고, 평균, 최악 모두O(n^2)이며 공간복잡도는 하나의 배열만 사용하므로 O(n)이다.
동작 방식은 인접한 두 요소간의 대소 비교를 진행한다.

이를 코드로 구현하면 다음과 같다.

배열의 요소 개수만큼 반복하면서, 각 반복시 인접 요소를 비교해 바꾸어주는것이다. 반복시마다 가장 큰 요소는 마지막에 위치하게 되므로 제외하면서 반복한다.

const swap = (arr, i, j) => {
	[arr[i], arr[j]] = [arr[j], arr[i]];
};

const bubbleSort = (arr) => {
	const sortedArr = [...arr];
	const len = sortedArr.length;

	for (let i = 0; i < len; i++) {
		for (let j = 0; j < len - i - 1; j++) {
			if (sortedArr[j] > sortedArr[j + 1]) swap(sortedArr, j, j + 1);
		}
	}

	return sortedArr;
};

삽입 정렬(Insertion Sort)

삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다.
알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다.
모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 O(n)의 시간 복잡도를 가지며 공간복잡도는 하나의 배열만 사용하므로 O(n)이다.

이를 코드로 구현하면 다음과 같다.

첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하는 것이다.

const swap = (arr, i, j) => {
	[arr[i], arr[j]] = [arr[j], arr[i]];
};

const insertionSort = (arr) => {
	const SortedArr = [...arr];
	const len = SortedArr.length;

	for (let i = 1; i < len; i++) {
		for (let j = i; j >= 0; j--) {
			if (SortedArr[j - 1] > SortedArr[j]) swap(SortedArr, j - 1, j);
		}
	}

	return SortedArr;
};

선택 정렬(Selection Sort)

선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘이다.
시간복잡도 최선, 평균, 최악 모두 O(n^2)에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다.

이를 코드로 구현하면 다음과 같다.
배열에서 최소값을 찾아 맨 앞의 값과 바꾼다. 바꿔준 맨 앞 값을 제외하고 같은 방법을 반복한다.

const swap = (arr, i, j) => {
	[arr[i], arr[j]] = [arr[j], arr[i]];
};

const selectionSort = (arr) => {
	const SortedArr = [...arr];
	const len = SortedArr.length;

	for (let i = 0; i < len; i++) {
		let min = i;
		for (let j = i + 1; j < len; j++) {
			if (SortedArr[min] > SortedArr[j]) min = j;
		}
		swap(SortedArr, i, min);
	}

	return SortedArr;
};

덧붙여 선택 정렬은 크게 2가지로 최소 선택 정렬과, 최대 선택 정렬이 있다.
최소 선택 정렬은 위처럼 오름차순으로 정렬하는 것이고 최대 선택 정렬은 내림차순으로 정렬하는 것이다.

퀵 정렬 (Quick Sort)

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다. 파이썬이나 자바에서 언어에서 자체 내장되어 있는 정렬 알고리즘도 퀵 정렬을 기반으로 한다.
시간 복잡도의 경우 최선과 평균일 때 O(nlogn)이며 최악의 경우에는 O(n^2)이다.
공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 O(n)이다.

퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다.
피봇 선택 방법에 따라 퀵 정렬의 성능이 달라지는데 최적의 피봇 선택이 어려워 보통 배열의 첫 번째 값이나 중앙 값을 선택한다.

퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [29, 10, 14, 37, 1, 40]이 있고, 피봇을 임의로 29를 선택했다 가정하자.
이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [10, 14, 1] < 29 < [37, 40]을 생성한다.
다시 왼쪽에서부터 임의의 피봇 10을 설정하여 [1] < 10 < [14]를 생성하고 오른쪽에선 임의의 피봇 37을 설정하여 37 < [40]으로 나눈다.
만약 배열의 길이가 1이라면 정렬이 완료된 것이므로 분할된 배열을 합쳐준다.

이를 코드로 구현하면 다음과 같다.

const quickSort = (arr) => {
	if (arr.length === 0) return [];

	const pivot = arr[0];
	const left = [];
	const right = [];

	for (let i = 1; i < arr.length; i++) {
		if (arr[i] < pivot) left.push(arr[i]);
		else right.push(arr[i]);
	}

	return quickSort(left).concat(pivot, quickSort(right));
};

병합 정렬(Merge Sort)

병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
시간 복잡도의 경우 최선, 평균, 최악 모두 O(nlogn)이며 공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 O(n)이다.
.

퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다.
그러나 퀵 정렬이 피봇 선택후 피봇을 기준으로 대소를 비교하는 반면, 병합 정렬은 배열의 요소가 하나일때까지 이분할 한 다음, 대소관계에 따라 재배열 하며 원래 크기의 배열로 병합한다.
예를 들어 배열 [29, 10, 14, 37, 1, 40]이 있을 때, 첫 번째로 [29, 10, 14]와 [37, 1, 40]으로 분리한다.
두 번째로 [29, 10], [14], [37, 1], [40]으로 나눈다.
세 번째로 [29], [10], [14], [37], [1], [40]으로 나눈다.
이렇게 모든 원소가 분리되면 대소 관계를 고려하여 병합 과정을 거친다.
첫 번째로 [10, 29], [14], [1, 37], [40]이 되며, 두 번째는 [10, 14, 29], [1, 37, 40]이 된다.
마지막으로 하나의 배열로 병합되면서 [1, 10, 14, 29, 37, 40]와 같이 정렬이 완료된다.

이를 코드로 구현하면 다음과 같다.

const merge = (left, right) => {
	const result = [];
	while (left.length !== 0 && right.length !== 0) {
		if (left[0] < right[0]) result.push(left.shift());
		else result.push(right.shift());
	}

	return [...result, ...left, ...right];
};

const mergeSort = (arr) => {
	if (arr.length === 1) return arr;

	const middleIndex = Math.ceil(arr.length / 2);
	const left = arr.slice(0, middleIndex);
	const right = arr.slice(middleIndex);

	return merge(mergeSort(left), mergeSort(right));
};

마치며

위에서 정리한 5가지의 정렬 방법 외에도 힙 정렬, 팀 정렬등 정말 많은 정렬 방법이 존재한다.
모든 정렬 방법을 다 탐구하고 외우기는 어렵지만 적절한 자료구조와 알고리즘을 활용해야 좋은 코드를 작성할 수 있는 만큼 꾸준히 CS 공부를 해야겠다🔥