알고리즘 - 정렬

정렬

정렬은 요소들을 일정한 순서대로 열거하는 알고리즘입니다. 정렬 기준은 사용자가 정할 수 있으며, 크게 비교식과 분산식 정렬로 나눌 수 있습니다. 대부분의 언어가 빌트인으로 제공해주며, 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재합니다.

상황에 따라서 적합한 정렬 방식이 있기 때문에 절대적으로 빠르다라고 말할 수 있는 정렬 방식은 없습니다.

• 비교식 정렬
  • 버블 정렬: 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘입니다. O(n^2)를 가집니다.
  • 선택 정렬: 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘입니다. O(n^2)를 가집니다.
  • 삽입 정렬: 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘입니다. O(n^2)를 가집니다.
• 분산식 정렬 : 분산식 정렬의 핵심은 분할 정복입니다. 분할 정복이란 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략입니다.
  • 합병 정렬: 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘입니다. O(n log n)을 가집니다.
  • 퀵 정렬: 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬입니다. O(n log n)을 가집니다.
• 정렬 구현 : 자바스크립트에서는 정렬의 사용이 매우 간단합니다. 단, 그냥 정렬함수를 이용한다면 아스키코드 순서로 정렬되기 때문에 오름차순 정렬과 내림차순 정렬 시 유의하셔야합니다.

const nums = [5,9,10,3,8,3,2];
// 다음과 같이 그냥 정렬하면 아스키 순서로 정렬
array.sort(); // [10,2,3,3,5,8,9];
// 10이 먼저 나오는 이뉴는 아스키 순서에서 문자 1이 문자2보다 작기 때문

// 숫자 정렬
array.sort((a,b)=> a-b); // 오름차순
array.sort((a,b)=> b-a); // 내림차순

// 문자 정렬
strs.sort((a,b)=> a<b ? -1 : 1); // 오름차순
strs.sort((a,b)=> b<a ? -1 : 1); // 내림차순