# Binary search Sorted array에서 특정 값을 찾을 때 사용되는 search algorithm이다. 배열의 모든 값을 처음부터 순회하며 탐색하는 sequential search는 시간 복잡도가 O(n)인데 반해, binary search는 O(logn)이기 때문에 정렬되지 않은 배열을 탐색하는 것이 아니라면 binary search를 사용하는 것이 권장된다. # Process array의 중간값과 목표값의 크기를 비교한다. 중간값과 목표값이 같다면 해당 값의 index를 반환한다. 중간값이 목표값보다 작다면 중간값의 오른쪽 sublist에서 위 동작을 반복한다. 중간값이 목표값보다 크다면 중간값의 왼쪽 sublist에서 위 동작을 반복한다. # JavaScript로 구현 Binary ..
# Counting Sort Counting Sort는 제한적인 사용 조건을 가진 대신 매우 빠른 정렬 알고리즘으로 non-comparison sort algorithm이다. O(n + k)의 시간 복잡도를 가지며 comparison sort 범주에 속하는 sorting algorithm보다 빠르다. 다만, k는 데이터의 범위를 나타내는 변수로, 데이터의 수는 적은데 범위만 매우 크다면 다른 알고리즘을 사용하는 것이 현명하다. 또한, count sort는 input data의 크기와 범위에 비례하는 추가 메모리가 필요하므로 메모리에 제약이 있는 상황에서도 사용하기가 어렵다. Counting Sort를 사용하기 위해선 데이터가 다음 조건에 맞아야 한다. 항상 양의 정수여야 한다. (따라서 실수 자료형인 경..
# Merge Sort 시간 복잡도가 O(nlogn)인 매우 효율적인 정렬 알고리즘 중 하나로 다음과 같은 특징을 가진다. comparison sort: 비교 연산자를 통한 sorting이다. divide-conquer algorithm: Input을 여러 partition으로 나누어 정렬하는 작업을 재귀적으로 진행한다. stable sort: 같은 값을 가지는 index에 대하여 index 순서가 유지되며 정렬된다. Linked list를 사용할 경우 in-place로 구현 가능하다. (array의 경우 불가) 기본적인 특징들은 quick sort와 매우 유사하나 일반적으로 quick sort보다 약간 느리다고 한다. 하지만 quick sort는 최악의 경우 O(n2)의 시간 복잡도를 가지는데 반해 m..
# Quick Sort 이름 그대로 매우 빠른 속도의 정렬 방법이며 divide and conquer algorithm을 사용하는 정렬이다. Merge sort나 heap sort에 비해서도 살짝 빠르다고 한다. Quick sort는 in-place algorithm이고 unstable하다. 따라서, 메모리를 크게 요구하지 않으며 같은 값을 가지는 index의 순서 정렬은 보장되지 않는다. 평균적으로 O(nlogn), worst case인 경우 O(n2)의 시간 복잡도를 가진다. # Process Quick sort는 divide and conquer 방법을 사용한다. Input의 값 중 임의의 값 하나를 pivot으로 삼아 이것과의 상대적인 크기로 partition을 나누고, 각각의 partition에..
# Insertion Sort 각 iteration마다 하나의 값을 정렬된 값들 사이 적절한 위치에 삽입하는 방식으로 동작하는 정렬이다. Insertion sort의 특징은 다음과 같다. 코드량이 짧다 (C/C++의 경우 세 줄로도 가능하다고 한다.) 최악의 경우 시간 복잡도가 O(n2)이기에 주로 작은 데이터 처리 시 활용된다. 일반적인 경우 selection sort, bubble sort 등 다른 quadratic algorithm보다 빠르다. Input이 어느 정도 정렬된 경우 효율적이다 (Adaptive sort) 두 인덱스에서 같은 값을 가지는 경우 인덱스 순서대로 정렬된다. (Stable) Input 크기에 비례하는 추가 메모리를 필요로 하지 않는다. (In-place) Input이 일부분씩..
JavaScript로 swap을 구현할 때 두 가지 방법이 자주 사용되는 것으로 보인다. 이 두 방법의 효율성을 비교해 보았다. # Swap의 두 가지 방법 1. temp 변수를 이용한 swap let a = 0; let b = 1; // swap let temp = a; a = b; b = temp; console.log(`a = ${a}, b = ${b}`); // a = 1, b = 0 2. destructuring을 이용한 swap let a = 0; let b = 1; // swap [a, b] = [b, a]; console.log(`a = ${a}, b = ${b}`); // a = 1, b = 0 # 효율성 측정 length가 2인 array를 만들고 두 element를 10000번 바꾸는..
