정렬 알고리즘 (Selection, Insertion, Merge, Quick)
선택정렬 (Selection sort)
주어진 자료들 중에 현재 위치에 맞는 자료를 찾아 선택하여 위치를 교환하는 알고리즘.
한번 순회를 돌게 되면알고리즘 상 전체 자료 중 가장 작은 값의 자료가 0번째 인덱스에 위치하게 되므로,
그다음 순회부터는 1번 인덱스부터 순회를 돌며 반복하면 된다.
- 0번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 0번째 인덱스와 스왑
- 1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 1번째 인덱스와 스왑
... - n-1번 인덱스 ~ n번 인덱스 중 가장 작은 값을 찾아 n번째 인덱스와 스왑
선택정렬은 현재 자료가 정렬이 되어있건 말건 무조건 전체 리스트를 순회, 검사하기 때문에
최선의 경우든 최악의 경우든 한결같이 O(n^2)의 시간복잡도를 가지고 있다.
function selectionSort(arr) {
const leng = arr.length;
let swap = null;
for (let i = 0; i < leng; i++) {
for (let j = 0; j < leng; j++) {
if (arr[i] < arr[j]) {
// 스왑
swap = arr[j];
arr[j] = arr[i];
arr[i] = swap;
swap = null;
}
}
}
return arr;
}삽입정렬 (Insertion sort)
주어진 자료의 모든 요소를 앞에서부터 차례대로 정렬된 자료 부분과 비교하여
자신의 위치를 찾아 삽입하는 알고리즘.
- 0번 인덱스는 건너뜀
- 0 ~ 1번 인덱스 중 1번 인덱스 값이 들어가야 할 위치를 찾아서 삽입
- 0 ~ 2번 인덱스 중 2번 인덱스 값이 들어가야할 위치를 찾아서 삽입
... - 0 ~ n번 인덱스 중 n번 인덱스 값이 들어가야할 위치를 찾아서 삽입
삽입정렬은 최선의 경우 전체 자료를 한번만 순회하여 O(n)의 시간복잡도를 갖지만,
최악의 경우 O(n^2)의 시간복잡도를 갖는다.
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i];
let j;
// 현재 요소 이전의 모든 요소를 비교, 삽입할 위치를 찾음
for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
// 삽입 위치를 찾으면, 뒤로 모두 한 칸씩 이동
arr[j + 1] = arr[j];
}
// 삽입 위치를 찾은 후, currentVal 값을 해당 위치에 삽입
arr[j + 1] = currentVal;
}
return arr;
}병합정렬 (Merge sort)
일종의 분할 정복법중 하나로 큰 문제를 작은 여러개의 문제로 쪼개서 각각을 해결한 후
결과를 모아서 원래의 문제를 해결하는 방법. 병합이라는 이름 그대로 주어진 자료를 잘게
쪼갠 뒤 합치는 과정에서 정렬을 하는 알고리즘.
- [7, 1, 5, 3] 배열에서 length가 1이 될 때까지 반으로 쪼갬
- [7, 1], [5, 3] 를 또 쪼갬 => [7], [1], [5], [3]
- 왼쪽 0번 인덱스와 오른쪽 0번 인덱스를 비교하여 작은 값 먼저 병합 ([7], [1] / [5], [3])
- [1, 7] 생성 [3, 5] 생성 (정렬된 리스트들은 정렬되었기 때문에 작은 인덱스일수록 작은 값을 가진다는 것이 보장)
- 왼쪽 0번 인덱스와 오른쪽 0번 인덱스를 비교하여 작은값 먼저 병합
- [1] 생성 ([7], [3, 5] 가 남음)
- 왼쪽 0번 인덱스와 오른쪽 0번 인덱스를 비교하여 작은 값 먼저 병합
- [1, 3] 생성 ([7], [5] 가 남음)
- 왼쪽 0번 인덱스와 오른쪽 0번 인덱스를 비교하여 작은 값 먼저 병합
- [1, 3, 5] 생성 ([7] 남음)
- 값이 남았으므로 병합
- [1, 3, 5, 7] 정렬 끝
왼쪽 0번 인덱스와 오른쪽 0번 인덱스를 비교하여 작은값 먼저 병합 이 과정이 한무 반복되고 있다.
같은 방식으로 계속 반복하여 병합하기 때문에 병합정렬은 보통 재귀함수로 구현한다.
병합정렬은 항상 O(n log n)의 시간복잡도를 가지기 때문에 효율적이다.
그러나 원소의 개수만큼 리스트를 쪼개고 따로 저장하고 있어야 하기 때문에 O(n)의 공간복잡도를 갖는다.
즉, 메모리를 제물로 속도를 얻고있다.
function mergeSort(arr) {
// 길이가 1 이하일 경우, 그대로 반환
if (arr.length <= 1) {
return arr;
}
// 반으로 나누기 위한 중간 인덱스 계산
const middle = Math.floor(arr.length / 2);
// 반으로 나누어 왼쪽과 오른쪽으로 분할
const leftArr = arr.slice(0, middle);
const rightArr = arr.slice(middle);
// 재귀적으로 분할된 배열을 병합, 정렬된 배열을 반환
return merge(mergeSort(leftArr), mergeSort(rightArr));
}
// 두 개의 배열을 병합하는 함수
function merge(leftArr, rightArr) {
let resultArr = []; // 병합 결과를 저장할 배열
let leftIdx = 0; // 왼쪽 배열의 탐색 인덱스
let rightIdx = 0; // 오른쪽 배열의 탐색 인덱스
// 왼쪽 배열과 오른쪽 배열을 비교하여 작은 값을 결과 배열에 추가
while (leftIdx < leftArr.length && rightIdx < rightArr.length) {
if (leftArr[leftIdx] < rightArr[rightIdx]) {
resultArr.push(leftArr[leftIdx]);
leftIdx++;
} else {
resultArr.push(rightArr[rightIdx]);
rightIdx++;
}
}
// 남은 배열의 요소들을 결과 배열에 추가
return resultArr
.concat(leftArr.slice(leftIdx))
.concat(rightArr.slice(rightIdx));
}퀵정렬 (Quick sort)
병합정렬과 마찬가지로 분할정복을 통한 정렬방법. 차이점은?
병합정렬은 분할 단계에서는 아무것도 안 하고 병합하는 단계에서 정렬을 수행,
퀵정렬은 분할 단계에서 중요한 작업들을 수행하고 병합 시에 아무것도 안 함.
- 입력된 리스트에서 하나의 원소를 고름 (이 원소를 피벗이라고 부른다)
- 피벗을 기준으로 리스트를 둘로 분할
- 피벗을 기준으로 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로 옮김
- 피벗을 기준으로 피벗보다 큰 원소들은 모두 피벗의 오른쪽으로 옮김
function quickSort(arr, left = 0, right = arr.length - 1) {
// 길이가 1보다 작거나 같으면 이미 정렬된 것으로 간주하여 리턴
if (arr.length <= 1) {
return arr;
}
// 피벗을 선택, 피벗은 보통 가운데 값을 선택
const pivot = arr[Math.floor((left + right) / 2)];
// 피벗을 기준으로 작은 값을 왼쪽에, 큰 값을 오른쪽에 모으기 위해 분할
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
// 분할된 두 부분 배열에 대해 재귀적으로 퀵정렬을 수행
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
return arr;
}