Algorithm/Javascript로 정리하는 이코테
[Javascript로 정리하는 이코테] 5. 정렬
반응형
http://www.yes24.com/Product/Goods/91433923
개념
- 정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
- 정렬 알고리즘은 이진 탐색의 전처리 과정
선택 정렬
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 맨 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
- 시간복잡도:
O(n^2)
예제 6-1. 선택 정렬
let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];
for (let i = 0; i < array.length; i++) {
let minIdx = i;
for (let j = i + 1; j < array.length; j++) {
if (array[minIdx] > array[j]) {
minIdx = j;
}
}
[array[i], array[minIdx]] = [array[minIdx], array[i]];
}
console.log(array);
예제 6-2. 자바스크립트 스와이프(swap)
let array = [3, 5];
[array[0], array[1]] = [array[1], array[0]];
console.log(array); // [5, 3]
삽입 정렬
- 특정한 데이터를 적절한 위치에 삽입하는 과정을 반복한다.
- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
- 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬되어 있을 때’ 훨씬 효율적이다. 따라서 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 선택 정렬에 비해, 실행 시간 측면에서 더 효율적이다.
- 시간복잡도:
O(n^2)
, 최선의 경우O(n)
예제 6-3. 삽입 정렬
let array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8];
for (let i = 1; i < array.length; i++) {
for (let j = i; j > 0; j--) {
if (array[j - 1] < array[j]) break;
[array[j], array[j - 1]] = [array[j - 1], array[j]];
}
}
console.log(array);
퀵 정렬
- 기준을 설정하고 큰 수와 작은 수를 교환한 후 배열을 반으로 나누는 방식으로 동작한다.
- 기준을 피벗(
pivot
)이라 하며, 이를 어떻게 설정한 것인지에 따라 배열을 분할하는 여러 가지 방식이 있다.
이 책은 호어 분할 방식을 기준으로 설명한다.
- 배열의 첫 번째 데이터를 피벗으로 정한다.
- 배열의 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터는 피벗보다 작은 데이터를 찾는다. 그리고 그 둘을 교환한다.
- 두 값이 엇갈릴 때까지 2번 과정을 반복한다. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값이 엇갈리는 경우, 작은 데이터와 피벗의 위치를 서로 변경한다.
- 이후 배열을 보면 피벗의 왼쪽에는 피벗보다 작은 데이터들이, 오른쪽에는 피벗보다 큰 데이터들이 위치한다. 이러한 작업을 분할(
Divide
) 혹은 파티션(Partition
)이라고 한다.
피벗을 기준으로 좌우 배열 각각에 위의 분할 과정을 반복(배열의 길이가 1이 될 때까지)하면 정렬이 이루어진다. 이는 재귀 함수와 동작 원리가 같다.
시간복잡도
O(nlogn)
, 최악의 경우O(n^2)
- 최선의 경우 배열이 절반씩 분할이 된다면 로그 탐색을 할 수 있다.
- 하지만 이미 정렬이 되어 있는 경우, 분할을 위해 선형 탐색이 이루어지기 때문에 매우 느리게 동작한다.
예제 6-4. 퀵 정렬
let arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];
const n = arr.length;
const quickSort = (arr, start, end) => {
if (start >= end) return;
const p = start;
let left = start + 1;
let right = end;
while (left <= right) {
//피벗보다 큰 데이터 찾을 때까지 탐색
while (left <= end && arr[p] >= arr[left]) {
left++;
}
//피벗보다 작은 데이터 찾을 때까지 탐색
while (right > start && arr[p] <= arr[right]) {
right--;
}
//swap
if (left > right) {
[arr[p], arr[right]] = [arr[right], arr[p]];
} else {
[arr[left], arr[right]] = [arr[right], arr[left]];
}
}
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
};
quickSort(arr, 0, n - 1);
console.log(arr);
예제 6-5. 자바스크립트의 장점을 살린 퀵 정렬
let arr = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8];
const n = arr.length;
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const p = arr[0]; //피벗은 첫 번째 원소
const tail = arr.slice(1); //피벗을 제외한 배열
const leftArr = tail.filter((v) => v <= p); //분할된 왼쪽 부분 (피벗보다 작은 값)
const rightArr = tail.filter((v) => v > p); //분할된 오른쪽 부분 (피벗보다 큰 값)
return [...quickSort(leftArr), p, ...quickSort(rightArr)];
};
console.log(quickSort(arr, 0, n - 1));
계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
- 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하다.
- 다만, 공간 복잡도 측면에서 비효율적일 수 있으니 주의해야 한다.
- 시간복잡도:
O(n + k)
- 데이터의 개수 n, 데이터 중 최대값의 크기 k
예제 6-6. 계수 정렬
const arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2];
const count = [...Array(Math.max(...arr) + 1).fill(0)];
arr.forEach((num) => count[num]++);
let sorted = '';
for (let num = 0; num < count.length; num++)
sorted += num.toString().repeat(count[num]);
console.log([...sorted]);
자바스크립트의 정렬 라이브러리
- 자바스크립트는
sort()
메서드를 제공한다. - 일반적으로 시간복잡도
O(nlogn)
을 보장한다. - 기본 정렬 순서는 유니코드 기반이므로, 숫자를 정렬하기 위해서는 아래와 같이 정렬 순서 정의 함수를 설정해야 한다.
const arr = [21, 4, 11, 38, 1, 5];
const sortedUni = arr.sort();
console.log(sortedUni); //[ 1, 11, 21, 38, 4, 5 ]
const sortedNum = arr.sort((a, b) => a - b);
console.log(sortedNum); //[ 1, 4, 5, 11, 21, 38 ]
실전 문제
위에서 아래로
sort()
를 통해 정렬 →O(nlogn)
const fs = require('fs');
let input = fs.readFileSync('./tc.txt').toString().trim().split('\n');
let [n, ...arr] = input;
arr = arr.map((v) => +v.replace('\r', ''));
function solution(n, arr) {
return arr.sort((a, b) => b - a).join(' ');
}
console.log(solution(n, arr));
성적이 낮은 순서로 학생 출력하기
sort()
를 통해 정렬 →O(nlogn)
- 입력의 최대값이 100이므로
O(n)
을 보장하는 계수 정렬을 이용해도 된다.
const fs = require('fs');
let input = fs.readFileSync('./tc.txt').toString().trim().split('\n');
let [n, ...arr] = input;
const students = arr.map((v) => v.replace('\r', '').split(' '));
function solution(n, students) {
const sortedNames = students
.sort((a, b) => a[1] - b[1])
.map((student) => student[0]);
return sortedNames.join(' ');
}
console.log(solution(n, students));
두 배열의 원소 교체
- A는 오름차순, B는 내림차순으로 각각 정렬하고
- A의 원소가 B의 원소보다 작을 때, 두 배열의 원소를 교체한다.
const fs = require('fs');
let input = fs.readFileSync('./tc.txt').toString().trim().split('\n');
let [nk, A, B] = input;
const [n, k] = nk.split(' ');
A = A.replace('\r', '')
.split(' ')
.map((v) => +v);
B = B.replace('\r', '')
.split(' ')
.map((v) => +v);
function solution(n, k, A, B) {
A.sort((a, b) => a - b);
B.sort((a, b) => b - a);
for (let i = 0; i < k; i++) {
if (A[i] < B[i]) {
[A[i], B[i]] = [B[i], A[i]];
}
}
return A.reduce((a, b) => a + b);
}
console.log(solution(n, k, A, B));
Reference
반응형
'Algorithm > Javascript로 정리하는 이코테' 카테고리의 다른 글
[Javascript로 정리하는 이코테] 7. 다이나믹 프로그래밍 (0) | 2023.03.12 |
---|---|
[Javascript로 정리하는 이코테] 6. 이진 탐색 (0) | 2023.03.11 |
[Javascript로 정리하는 이코테] 4. DFS/BFS (0) | 2023.03.09 |
[Javascript로 정리하는 이코테] 3. 스택, 큐, 재귀 (1) | 2023.03.08 |
[Javascript로 정리하는 이코테] 2. 구현 (0) | 2023.03.07 |