검색: 특정 데이터를 얻기 위해 자료 구조의 항목을 반복적으로 접근하는 것
정렬: 자료 구조의 항목을 순서대로 위치시키는 것
1. 검색
1) 선형 검색
특징:
- 정렬된 자료와 정렬되지 않은 자료 모두에 사용 가능하다. (유연한 사용)
- 이진 검색에 비해 시간 복잡도가 높다.
동작 방식:
- 배열의 각 항목을 한 인덱스씩 순차적으로 접근하면서 동작한다.
- 최악의 경우 모든 n개의 항목을 반복 접근한다.
시간 복잡도:
- O(n)
2) 이진 검색
특징:
- 정렬된 자료에 대해 사용 가능하다.
- 선형 검색에 비해 시간 복잡도가 낮다.
동작 방식:
- 배열의 중간 값이 원하는 값보다 큰지 작은지를 비교하여, 더 작은 쪽 혹은 더 큰 쪽을 검색한다.
시간 복잡도:
- O(logN)
2. 정렬
데이터를 보다 빠르고 효율적으로 찾기 위하여 정렬을 수행한다.
0) 선행 참고
1 swap 함수
배열 내 두 항목 값을 교환하는 함수다. 정렬 알고리즘에서 도움 함수로 주로 사용된다.
const swap = (array, index1, index2) => {
let temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}2 stable sort(안정적인 정렬), unstable sort(불안정적인 정렬)
- list에서 동일한 키를 지닌 항목이 두 개 있다고 가정할 때, 정렬이 완료된 배열에서 동일한 키 항목의 앞 뒤 순서가 항상 바뀌지 않는 것이 안정적인 정렬이고, 순서가 바뀔 수도 있는 것이 불안정적인 정렬이다.
1) Bubble sort (거품 정렬)
특징:
- 모든 항목을 비교한다.
- nested for loop를 사용한다.
동작 방식:
- 전체 배열을 순회하면서 항목이 다음 항목보다 큰 경우 두 항목을 교환한다.
시간 복잡도:
- O(n2)
공간 복잡도:
- O(1)
2) Selection sort (선택 정렬)
특징:
- nested for loop를 사용한다.
- 거품 정렬 알고리즘보다 약간 더 효율적이다.
동작 방식:
- 가장 작은 항목을 찾아서, 배열의 현 위치에 삽입한다.
시간 복잡도:
- O(n2)
공간 복잡도:
- O(1)
3) Insertion sort (삽입 정렬)
특징:
- nested for loop를 사용한다.
- 선택 정렬과 비슷하나, 선택 정렬 알고리즘보다 약간 더 비효율적이다.
동작 방식:
- 배열을 순차적으로 검색하면서, 정렬되지 않은 항목을 배열의 정렬된 부분으로 이동시킨다.
시간 복잡도:
- O(n2)
공간 복잡도:
- O(1)
4) Quick sort (빠른 정렬)
특징:
- 배열의 중간 값을 기준으로 동작하는 것이 가장 효율적이다.
- 그러나 정렬되지 않은 배열의 중간 값을 얻기 위해서는 계산에 선형 시간이 소요된다.
- 이런 이유로 인해 분할 부분의 첫 번째 항목, 중간 항목, 마지막 항목의 중간 값을 주로 기준점으로 삼는다.
- 재귀 정렬이므로 분할 정복 방식을 사용한다. 따라서 O(nlog2(n))의 시간복잡도를 가지지만, 모든 항목이 한쪽으로만 위치되는 기준점을 선택하는 (최악의)경우 O(n2)의 시간 복잡도를 가진다.
- 재귀 정렬이므로 콜 스택을 사용하여 비교적 높은 공간 복잡도를 가진다.
- 평균 성능이 최적화되어야 하는 경우 사용하기 좋다. (메모리 참조가 지역화되어 있어 캐시의 히트율이 높아지기 때문에 평균 접근 시간이 낮아서 그러하다.)
동작 방식:
- 기준점을 지정한 후, 이 기준점을 기준으로 배열을 나누는 과정을 반복한다.
시간 복잡도:
- 평균: O(nlog2(n))
- 최악의 경우: O(n2)
공간 복잡도:
- O(log2(n))
5) Quick select (빠른 선택)
특징:
- 정렬되지 않은 목록에서 K번째로 작은 항목을 찾는 선택 알고리즘이다.
- quick sort과 같은 접근법을 사용하나, quick sort가 기준점의 양쪽 모두를 재귀적으로 수행하는 반면 quick select는 한쪽만을 재귀적으로 수행한다.
- 그러므로 시간복잡도가 quick sort 비해 낮다.
동작 방식:
- 기준점을 지정한 후, 이 기준점을 기준으로 배열을 나누는 과정을 반복한다.
시간 복잡도:
- O(n)
공간 복잡도:
- O(log2(n))
5) Merge sort (병합 정렬)
특징:
- 배열을 나눌 때 n개의 배열을 생성하고, 이후에 병합할 n개의 배열을 생성하기 때문에 공간 복잡도가 크다.
- 안정적인 정렬이 필요할 때 사용하기 좋다.
- 시간복잡도가 항상 O(nlog2(n))으로 보장된다.
동작 방식:
- 각 하위 배열에 하나의 항목이 존재할 때까지 배열을 하위 배열로 나눈다.
- 이후 각 하위 배열을 정렬된 순서로 병합한다.
시간 복잡도:
- O(nlog2(n))
공간 복잡도:
- O(n)
5) Count sort (계수 정렬)
특징:
- 배열의 항목들을 비교하지 않는다. (대신 각 항목의 등장 횟수를 센다.)
- 숫자에 대해서만 동작한다.
- 특정 범위가 주어져야 한다.
- 제한된 범위의 정수를 정렬할 때 가장 빠르게 사용할 수 있다.
동작 방식:
- 범위 내 항목의 등장 횟수를 세어, 등장 횟수와 인덱스를 이용해 새로운 배열을 생성한다.
시간 복잡도:
- O(k+n)
공간 복잡도:
- O(k)
6) Array.sort()
특징:
- 자바스크립트 내장 정렬이다.
- 기본 조건에서 알파벳 오름차 순으로 정렬한다.
- 숫자 오름차순은
(a, b) => a - b비교 함수를 sort의 인자로 전달하여 구현한다. - 숫자 내림차순은
(a, b) => b - a비교 함수를 sort의 인자로 전달하여 구현한다. (return 값이 양수이면 항목을 교체하고, 음수이거나 0이면 항목을 그대로 두는 방식이라고 생각된다.)
동작 방식:
- 범위 내 항목의 등장 횟수를 세어, 등장 횟수와 인덱스를 이용해 새로운 배열을 생성한다.
시간 복잡도:
- O(k+n)
공간 복잡도:
- O(k)
💡 Software Engineer - F.E