[알고리즘 공부] 정렬(선택, 삽입, 퀵, 계수)
선택 정렬 (Selection Sort)
선택 정렬은
가장 작은 값을 탐색한 다음 그 값을 정렬이 안된 배열의 맨 앞에 위치한 값과 교체하는 알고리즘.
선택정렬 알고리즘 구현
const selectionSort = (arr) => {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) min = j;
}
[arr[i], arr[min]] = [arr[min], arr[i]];
}
return arr;
};
selectionSort([2, 4, 33, 17, 8, 45, 1, 7, 10, 37]);
// [1, 2, 4, 7, 8, 10, 17, 33, 37, 45]i라는 시작점을 두고 j반복문을 돌려 최솟값을 찾아 시작점과 교체해주는 반복을 거쳐서 정렬해주는 방식
삽입 정렬 (Insertion Sort)
삽입 정렬은
아직 정렬되지 않은 임의의 데이터를 이미 정렬된 배열 부분과 비교하여,자신의 위치를 찾아 삽입함으로써정렬을 완성하는 알고리즘
삽입정렬 알고리즘 구현
const insertionSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let cur = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > cur) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = cur;
}
return arr;
};
insertionSort([10, 34, 45, 50, 8, 48, 14, 41, 43, 1, 46, 9, 7, 25, 36]);
// [1, 7, 8, 9, 10, 14, 25, 34, 36, 41, 43, 45, 46, 48, 50]삽입 정렬의 i의 방향은 오른쪽 j의 방향은 왼쪽으로 서로 반대방향을 가리킨다.
i의 기준이 되는 배열 값을 하나 담아두고
기준의 왼쪽 방향 즉, j 방향으로 하나씩 당겨주면서 정렬을 실시한다.
그러다가 i의 기준이 되는 배열 값의 적절한 위치에 도착하면 그 위치에 값을 넣어주는 형식이다.
퀵 정렬
pivot(중심축) 을 정하고, 중심축 보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보내는 것이다.
이렇게 pivot을 정해서 왼쪽 오른쪽으로 나누고 다시금 왼쪽 오른쪽에 대해 재귀적으로 pivot을 정해서 왼쪽 오른쪽을 나누고,, 이 과정을 반복하면 결국 정렬이 완성 된다.
퀵정렬 알고리즘 구현
const quickSort = function (arr) {
if (arr.length <= 1) return arr;
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]);
}
const lSorted = quickSort(left);
const rSorted = quickSort(right);
return [...lSorted, pivot, ...rSorted];
};퀵 정렬, 병합 정렬 차이점
- 병합정렬은 배열을 분할하는 방식이 반으로 쪼개는 것
- 퀵 정렬은 크게 두 가지 분할 방법이 있다.
- 퀵 정렬은 병합정렬과 달리 다른 메모리 공간을 사용하지 않는다. (오직 재귀 콜 스택을 위한 메모리만 사용됨, 그에 반면 병합정렬은 매 번 새로운 배열을 만들어 내므로 메모리 사용량이 더 큼)
- 드물지만, 파티션의 방법에 따라 최악의 경우에 O(n²) 까지 성능이 낮아질 수 있음.
- 병합정렬은 stable 하지만, 퀵 정렬은 unstable 하다. (원소들 중에 같은 값이 있는 경우에 정렬 이후 순서가 초기 순서와 달라 질 수 있기 때문에)
계수 정렬
정렬 중에 그나마 빠른 힙정렬의 경우에도 시간복잡도 O(Nlog₂N)인데
계수정렬은 시간복잡도가 O(N)으로 굉장히 빠르다.
-
그러나 정렬해야할 수의 범위가 작을 때에만 유리하다는 것을 유의해야 함.
-
정렬해야할 수가 0,100,2,10,1000 이라면 고작 5개의 수를 정렬하는데 0부터 1000까지 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 함.
-
가장 큰 수를 구한다.
-
가장 큰 수의 크기만큼 배열을 선언하고 0으로 초기화 한다.
-
숫자의 개수를 세어 count 배열에 저장한다.
-
누적합을 구한다.
-
누적합이 가리키는 인덱스를 바탕으로 결과에 숫자를 집어넣는다.
-
계수정렬 알고리즘 구현
const numbers = [5, 2, 3, 1, 4, 2, 3, 5, 1, 7];
const countingSort = (numArr) => {
const max = Math.max(...numArr); // 가장 큰 수를 구한다
const count = new Array(max + 1).fill(0); // 가장 큰 수의 크기만한 배열을 생성하고 모든 숫자의 개수를 0으로 초기화
const sortedArray = [];
numArr.forEach((val) => {
// 숫자의 개수를 세어 저장한다.
count[val]++;
});
for (let i = 0; i < max; i++) {
// 누적합을 구한다.
count[i + 1] += count[i];
}
numArr.forEach((val) => {
// 누적합이 가리키는 인덱스를 바탕으로 결과에 숫자를 집어넣는다.
sortedArray[count[val] - 1] = val;
count[val]--;
});
return sortedArray;
};
console.log(countingSort(numbers));
