정렬

**정렬(Sort)**이란?

요소들을 일정한 순서대로 열거하는 알고리즘

정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것을 말한다. 사용자가 정의한 순서는 오름차순이나 내림차순일 수도 있고 임의의 조건이 될 수도 있다.

정렬의 특징

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 대부분의 언어가 빌트인으로 제공해준다.
  • 기본 내장 자바스크립트 정렬
• 삽입, 선택, 버블, 머지, 힙, 퀵, 기수 정렬 등 다양한 정렬 방식이 존재한다.

정렬이 필요한 이유

데이터를 정렬하면 원하는 데이터를 쉽게 찾을 수 있기 때문이다.

예를 들어, 데이터의 중앙값을 찾아야할 경우 :

• 정렬하지 않으면 모든 데이터를 확인하고 비교해야 한다.
• 정렬하면 데이터의 값을 보거나 비교할 필요 없이 데이터 전체 크기에서 중간 위치의 값만 찾으면 된다.

이처럼 정렬은 알고리즘의 효율을 크게 높여준다.

비교식 정렬

다른 요소와 비교를 통해 정렬하는 방식

• 버블 정렬(Bubble Sort)
  • 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘,
  • 시간복잡도 : O(n²)
  • n - 1번 순회하면 정렬 완료
• 선택 정렬(Selection Sort)
  • 최솟값을 찾아 맨 앞으로 보내고, 그 다음 작은 값을 찾아 2번째 위치로 보내는 식으로 정렬
  • 시간복잡도: O(n²)
  • 제자리 정렬 알고리즘
• 삽입 정렬(Insertion Sort)
  • 한 번에 한 원소씩 정렬된 배열을 만들어가는 알고리즘
  • 시간복잡도: O(n²)
  • 크기가 작은 배열이라면 선택, 버블 정렬보다 성능 우수
  • 어느 정도 정렬된 배열이라면 퀵 정렬보다 빠른 성능