검색
선형 검색
function linearSearch(arr, n) {
return arr.some((val) => val === n);
}
이진 검색
이분탐색은 정답을 기계적으로 찾기 힘들지만(eg. 보통 brute-force를 고려하면 지수적으로 나옴), 정답의 범위가 정해졌으며, 추측한 답과 정답과의 오차(+/- 를 알 수 있어야)를 선형시간에 판단 할 수 있는 조건의 문제에 효율적으로 적용 할 수 있다.
function binarySearch(arr, n) {
let lowIndex = 0;
let highIndex = arr.length - 1;
while (lowIndex <= highIndex) {
const midIndex = Math.floor((highIndex + lowIndex) / 2);
if (arr[midIndex] === n) return midIndex;
else if (n > arr[midIndex]) lowIndex = midIndex;
else highIndex = midIndex;
}
return -1;
}
정렬
거품 정렬
function swap(arr, index1, index2) {
const temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0; i -= 1) {
for (let j = 0; j < i; j += 1) {
if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
}
}
}
선택 정렬
function swap(arr, index1, index2) {
const temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function selectionSort(arr) {
const size = arr.length;
for (let i = 0; i < size - 1; i += 1) {
let min = i;
for (let j = i + 1; j < size; j += 1) {
if (arr[j] < arr[min]) min = j;
}
if (i !== min) swap(arr, i, min);
}
}
삽입 정렬
function insertionSort(arr) {
const size = arr.length;
for (let i = 1; i < size; i += 1) {
const val = arr[i];
let j = i - 1;
// 정렬된 부분의 값이 정렬되지 않은 부분의 값보다 큰 경우 하나씩 이동시킨다.
// 이는 값을 삽입할 공간을 만든다.
for (; j >= 0 && arr[j] > val; j -= 1) {
arr[j + 1] = arr[j];
}
arr[j + 1] = val;
}
}
빠른 정렬
function swap(arr, index1, index2) {
const temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function partition(arr, left, right) {
const pivot = arr[Math.floor((left + right) / 2)];
while (left <= right) {
while (pivot > arr[left]) {
left += 1;
}
while (pivot < arr[right]) {
right -= 1;
}
if (left <= right) {
if (left !== right) swap(arr, left, right);
left += 1;
right -= 1;
}
}
return left;
}
function quickSortHelper(arr, left, right) {
if (arr.length > 1) {
const index = partition(arr, left, right);
if (left < index - 1) quickSortHelper(arr, left, index - 1);
if (index < right) quickSortHelper(arr, index, right);
}
}
function quickSort(arr) {
quickSortHelper(arr, 0, arr.length - 1);
}
빠른 선택
function swap(arr, index1, index2) {
const temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
function partition(arr, left, right) {
const pivot = arr[Math.floor((left + right) / 2)];
let leftIndex = left;
let rightIndex = right;
while (leftIndex <= rightIndex) {
while (pivot > arr[leftIndex] && leftIndex <= right) leftIndex += 1;
while (pivot < arr[rightIndex] && rightIndex >= left) rightIndex -= 1;
if (leftIndex <= rightIndex) {
if (leftIndex !== rightIndex) swap(arr, leftIndex, rightIndex);
leftIndex += 1;
rightIndex -= 1;
}
}
return leftIndex;
}
function quickSelectInPlace(arr, k) {
let left = 0;
let right = arr.length - 1;
while (left < right) {
const index = partition(arr, left, right);
if (index > k - 1) right = index - 1;
else left = index;
}
return arr[k - 1];
}
병합 정렬
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return [...result, ...left.slice(leftIndex), ...right.slice(rightIndex)];
}
function mergeSort(arr) {
if (arr.length === 1) return arr;
const middle = Math.floor(arr.length / 2);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
계수 정렬
function countSort(arr) {
const hash = {};
const countArr = [];
arr.forEach((val) => {
if (!hash[val]) hash[val] = 1;
else hash[val] += 1;
});
for (key in hash) {
for (let i = 0; i < hash[key]; i += 1) {
countArr.push(parseInt(key));
}
}
return countArr;
}