정렬의 개념

정렬은 여러 데이터로 구성된 리스트에서, 값의 크기 순서에 따라 데이터를 재배치하는 것을 의미합니다. 컴퓨팅 초기부터 많은 연구가 진행된 분야이고, 가장 많이 활용되는 연산 중 하나이기도 합니다.

내부 정렬 VS 외부 정렬

정렬을 수행하는 시점에, 정렬할 데이터가 어디에 저장되어 있는가에 따라 정렬은 “내부 정렬” 과 “외부 정렬” 로 구분할 수 있습니다.

• 내부 정렬
  입력의 크기가 주기억장치의 용량보다 작아, 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
• 외부 정렬
  모든 데이터를 보조기억장치에 저장한 채 그 중 일부 데이터만 반복적으로 주기억장치로 읽어들여서 정렬하는 방식

안정적 정렬 VS 불안정적 정렬

동일한 값을 갖는 데이터의 상태가 어떻게 되느냐에 따라 정렬은 “안정적 정렬”, “불안정적 정렬” 로 구분할 수 있습니다.

• 안정적 정렬
  동일한 값을 가지는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지됨
• 불안정적 정렬
  동일한 값을 가지는 데이터가 여러 개 있을 때 정렬 전의 상대적인 순서가 정렬 후 유지되지 않음

비교 기반 정렬 VS 데이터 분포 기반 정렬

내부 정렬 알고리즘은 정렬 방식에 따라 “비교 기반 알고리즘”, “데이터 분포 기반 알고리즘” 으로 분류할 수 있습니다.

• 비교 기반 알고리즘: 두 키 값 전체를 직접적으로 비교하여 어떤 값이 큰지, 작은지를 결정하여 정렬을 수행함
  • 버블 정렬 (O(n^2))
  • 선택 정렬 (O(n^2))
  • 삽입 정렬 (O(n^2))
  • 셸 정렬 (O(n^2))
  • 합병 정렬 (O(nlogn))
  • 퀵 정렬 (O(nlogn))
  • 힙 정렬 (O(nlogn))
• 데이터 분포 기반 알고리즘: 데이터의 분포 정보를 활용하여 정렬을 수행함
  • 계수 정렬 (O(n))
  • 버킷 정렬 (O(n))

제자리 정렬

“제자리” 는 “정렬을 수행할 때 얼마나 많은 저장공간을 필요로 하는가?” 를 나타내기 위한 개념입니다. 정렬할 데이터(입력 데이터) 를 저장하는 공간 외에 추가적으로 필요한 저장공간이 상수면, – 입력 크기 n 이 증가해도 추가적인 저장공간이 증가하지 않는다면 해당 알고리즘을 제자리 정렬 알고리즘이라고 부릅니다.