정렬(Sorting)은 컴퓨터 과학에서 가장 기본적이면서도 중요한 알고리즘 문제 중 하나이다.
데이터를 일정한 기준에 따라 정렬하는 과정은 다양한 알고리즘의 기반이 되며, 실제 서비스에서도 매우 자주 사용된다.
대학교 알고리즘 수업에서 처음 정렬 알고리즘을 접했을 때 가장 인상적이었던 점은 생각보다 많은 종류의 정렬 알고리즘이 존재한다는 것이었다. 대표적으로 알려진 정렬 알고리즘만 해도 15개 이상이 존재하며, 각각 서로 다른 방식으로 데이터를 정렬한다.
각 알고리즘은 다음과 같은 요소에 따라 성능이 달라진다.
- 데이터의 크기
- 데이터의 정렬 상태
- 메모리 사용량
- 알고리즘의 시간 복잡도
따라서 특정 상황에서는 어떤 알고리즘이 더 효율적으로 동작할 수 있다.
정렬 알고리즘을 평가하는 기준
정렬 알고리즘을 비교할 때는 보통 다음 세 가지 기준을 사용한다.
시간 복잡도 (Time Complexity)
시간 복잡도는 입력 데이터의 크기가 증가할 때 연산 횟수가 얼마나 증가하는지를 나타낸다.
| 복잡도 | 의미 |
|---|---|
| O(n) | 선형 시간 |
| O(n log n) | 효율적인 정렬 알고리즘 |
| O(n²) | 비교적 비효율적인 정렬 |
예를 들어
버블 정렬 → O(n²)
선택 정렬 → O(n²)
삽입 정렬 → O(n²)
과 같은 시간 복잡도를 가진다.
공간 복잡도 (Space Complexity)
공간 복잡도는 알고리즘이 실행될 때 추가적으로 필요한 메모리 공간을 의미한다.
정렬 알고리즘은 크게 두 가지 방식으로 나뉜다.
-
In-place 정렬
기존 배열 내부에서 데이터를 교환하면서 정렬 -
Out-of-place 정렬
새로운 배열을 생성하여 정렬
안정성
데이터 내에 동일한 값을 가진 요소들이 정렬 후에도 위치가 유지되는지 여부
EX. 08학번 김철수, 10학번 이영희를 학번순 정렬 시,
동일 이름이 있을 때 기존 순서가 바뀌지 않아야 함
JavaScript의 sort() 함수
JavaScript에서는 배열을 정렬하기 위해 sort() 라는 내장 함수를 제공한다.
하지만 기본적으로 sort() 함수는 숫자 정렬을 수행하지 않는다.
배열의 요소를 문자열로 변환한 뒤 유니코드 값 기준으로 정렬한다.
예를 들어 다음 코드를 실행하면
[10, 2, 5].sort()[10, 2, 5]결과는 다음과 같다.
이는 숫자를 문자열로 변환한 후 정렬하기 때문이다.
유니코드 기준으로 비교하면 "10"이 "2"보다 먼저 오기 때문에 위와 같은 결과가 발생한다.
compare function
숫자를 올바르게 정렬하기 위해서는 sort()에 비교 함수(compare function)를 전달해야 한다.
arr.sort((a, b) => a - b)sort() 함수는 두 값을 비교한 뒤 다음과 같은 규칙에 따라 정렬을 수행한다.
| 반환값 | 의미 |
|---|---|
| 음수 | a가 b보다 앞에 위치 |
| 양수 | b가 a보다 앞에 위치 |
| 0 | 순서 유지 |
오름차순 정렬
arr.sort((a, b) => a - b)내림차순 정렬
arr.sort((a, b) => b - a)sort 함수의 다양한 활용
sort() 함수는 단순한 숫자 정렬뿐만 아니라 다양한 기준으로 정렬을 수행할 수 있다.
1) 문자열 길이 기준 정렬
["apple", "hi", "banana", "cat"]
.sort((a, b) => a.length - b.length)결과
["hi", "cat", "apple", "banana"]2) 객체 속성 기준 정렬
객체 배열에서도 특정 속성을 기준으로 정렬할 수 있다.
const users = [
{ name: "Tom", age: 29 },
{ name: "Jane", age: 21 },
{ name: "Mike", age: 34 }
]
users.sort((a, b) => a.age - b.age)3) 다중 기준 정렬
정렬 기준을 여러 개 설정할 수도 있다.
예를 들어, 나이->이름 순으로 정렬할 경우 다음과 같이 구현할 수 있다.
users.sort((a,b)=>{
if(a.age === b.age){
return a.name.localeCompare(b.name)
}
return a.age - b.age
})Bubble Sort
버블 정렬은 가장 단순한 정렬 알고리즘 중 하나이다.
이 알고리즘은 인접한 두 값을 비교하여 큰 값을 오른쪽으로 이동시키는 방식으로 동작한다.
이 과정을 반복하면 가장 큰 값이 배열의 끝으로 이동하게 된다.
예를 들어 다음 배열이 있다고 가정해보자.
[5,3,4,1]
정렬 과정은 다음과 같다.
3 5 4 1
3 4 5 1
3 4 1 5
첫 번째 반복이 끝나면 가장 큰 값인 5가 배열의 끝에 위치하게 된다.
function bubbleSort(arr){
for(let i = arr.length; i > 0; i--){
for(let j = 0; j < i - 1; j++){
if(arr[j] > arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}시간 복잡도
O(n²)버블 정렬은 구현이 매우 간단하지만 성능이 좋지 않기 때문에 실제 개발에서는 거의 사용되지 않는다.
Selection Sort
선택 정렬은 배열에서 가장 작은 값을 찾아 앞쪽으로 이동시키는 방식으로 동작한다.
정렬 과정은 다음과 같다.
- 배열에서 최소값을 찾는다
- 현재 위치의 값과 교환한다
- 다음 위치에서 다시 최소값을 찾는다
function selectionSort(arr) {
const swap = (arr, idx1, idx2) =>
([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);
for (let i = 0; i < arr.length; i++) {
let lowest = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[lowest] > arr[j]) {
lowest = j;
}
}
if (i !== lowest) swap(arr, i, lowest);
}
return arr;
}시간 복잡도
O(n²)버블 정렬과 동일한 시간 복잡도를 가지지만 swap 횟수가 적다는 특징이 있다.
Insertion Sort
삽입 정렬은 정렬된 부분에 새로운 값을 삽입하는 방식으로 동작한다.
카드를 손에 들고 정렬하는 과정과 매우 유사하다.
정렬 과정
- 두 번째 요소부터 시작한다
- 앞에 있는 값들과 비교한다
- 적절한 위치에 삽입한다
function insertionSort(arr){
var currentVal;
for(var i = 1; i < arr.length; i++){
currentVal = arr[i];
for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
arr[j+1] = arr[j];
}
arr[j+1] = currentVal;
}
return arr;
}시간 복잡도
최악의 경우
O(n²)하지만 배열이 이미 거의 정렬되어 있다면
O(n)까지 성능이 향상될 수 있다.
+) 세 가지의 알고리즘 비교하기
- 이진 탐색(Binary Search)
- 투 포인터 알고리즘
- 중복 제거 알고리즘
들도 정렬된 걸 전제로 다양한 알고리즘의 기반이 된다.
