특정 순서에 따라 주어진 데이터를 나열하는 것
크기 순으로 오름차순 or 내림차순 나열하는 것
검색의 기본 요건이다

데이터

• 레코드(n개의 필드), 필드, 키(식별자)로 구성되어 있다.
• 구별할 수 있는 식별자 역할을 하는 학번이 키.
• 한 학생의 학번, 이름, 주소 정보가 필드.
• 이러한 학생들의 모음이 레코드.
  

정렬 알고리즘의 평가 요소

• 비교 횟수
• 이동 횟수
  위의 두가지를 고려하여 O(n)을 구하여 평가한다.

정렬 방법

단순하고 쉬운 방법 (But 비효율적)

• 삽입 정렬
• 버블 정렬
• 선택 정렬

복잡하고 어려운 방법 (But 효율적)

• 퀵 정렬
• 힙 정렬
• 합병 정렬

-> 비효율적이지만 선택 정렬을 사용하는 경우 :

• 데이터의 개수가 적은 경우
• 직접 정렬을 만들어야 하는 경우
  -> 그 외의 경우는 일반적으로 퀵정렬 or 제공되는 정렬을 사용한다

정렬 알고리즘 분석

알고리즘	최선	평균	최악	안정성
삽입 정렬	O(n)	O(n^2)	O(n^2)	O
선택 정렬	O(n^2)	O(n^2)	O(n^2)	X
버블 정렬	O(n^2)	O(n^2)	O(n^2)	O
쉴 정렬	O(n)	O(n^1.5)	O(n^1.5)	X
퀵 정렬	O(nlogn)	O(nlogn)	O(n^2)	X
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)	X
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)	O
기수 정렬	O(dn)	O(dn)	O(dn)	O

안정성

• 중복된 키가 존재하는 경우 그 순서가 정렬 후에도 유지될 때 안정성이 있다고 한다.
  정렬 전 : 3 5 2(a) 10 2(b)
  정렬 후 : 2(a) 2(b) 3 5 10
  이 경우 중복되는 2가 존재하고, 정렬 후에도 두개의 2의 순서가 유지된다. 이러한 경우 안정성이 있다고 한다.

외부 정렬

• 데이터가 너무 커서 메모리에서 정렬을 수행할 수 없는 경우
  외부 저장장치를 사용
  외부 저장장치는 내부 저장장치(메모리)와 다르게 입출력 시간이 크다
• 기본적인 정렬 방법은 합병 정렬
• 성능은 원소의 비교가 아니라 입력 전체를 처리하는 시간