정렬
개요
특징
- 정렬 기준은 사용자가 정할 수 있습니다.
- 크게 비교식과 분산식 정렬로 나눌 수 있습니다.
- 대부분의 언어에서 빌트인으로 제공됩니다.
- 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재합니다.
비교식 정렬
버블 정렬
- 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 O(n^2) 시간복잡도를 가집니다.
선택 정렬
- 선택한 요소와 가장 우선순위가 높으 요소를 교환하는 정렬 알고리즘 O(n^2) 시간복잡도를 가집니다.
삽입 정렬
- 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘 O(n^2) 시간복잡도를 가집니다.
분산식 정렬
분할 정복 (Divide & Conquer)
- 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략 다양한 알고리즘에 응용됩니다.
합병 정렬
- 분학 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘 O(n log n) 시간복잡도를 가집니다.
퀵 정렬
- 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬 O(n log n) 시간복잡도를 가집니다.
JS 에서의 정렬 구현
const array = [2,3,4,5,10];
array.sort();
console.log(array);
array.sort((a, b) => a - b);
console.log(array);
array.sort((a, b) => b - a);
console.log(array);