[알고리즘][정렬] 정렬의 정의와 종류

정렬

			* 레코드(record): 정렬 대상
			* 필드(field): 레코드의 세분화된 단위
			* 키(key): 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드

• 정렬: 순서 없이 배열된 있는 자료들을 그 값에 따라 순서에 따라 재배열하는 것
• 키(key): 자료를 정렬하는 데 사용하는 자료의 값

-정렬의 종류/ 정렬 순서(sort order)

• 오름차순(ascending): 작은 값부터 시작하여 값이 증가흔 순서대로 배열하는 것
• 내림차순(descending): 큰 값부터 시작하여 값이 감소하는 순서대로 배열하는 것

-정렬 선택 시 고려사항

• 정렬의 효율성(sort efficiency): 얼마만큼 빠르게 정렬을 실시하는지
  • 비교 연산의 횟수와 이동 연산의 횟수가 효율성의 기준
  • 빅오 표기법(big-O)을 사용한 수행 속도 판별
• 정렬의 안정성(stability): 같은 키 값을 가지는 자료들을 입력 순서 그대로 정렬하는지
  • 안정 정렬(stable sort): 기존 정렬 내용이 유지됨 (삽입 정렬, 버블 정렬, 합병 정렬 등)
  • 불안정 정렬(unstable sort): 기존의 정렬 내용이 유지되지 않음

• 정렬에 사용되는 키가 여러 개 있을 때 다중 키(Multiple-Key) 정렬이라고 함 -> 다중 키 정렬에서 안정성 여부가 중요한 차이를 발생시킴

정렬의 종류

정렬 방법의 분류1

1. 정렬이 수행되는 장소
   1) 내부 정렬(Internal Sort)

   • 컴퓨터 메모리 내부에서 정렬
   • 장점: 빠른 정렬
   • 단점: 대용량 데이터 정렬 불가

   2) 외부 정렬(External Sort)

   • 외부 보조 기억 장치(ex. 하드 드라이브) 에서 정렬
   • 장점: 대용량의 데이터 정렬 가능
   • 단점: 수행 속도 느림

2. 실행 방법
   1) 교환(Exchange)

   • 키 값을 비교하고 자료를 교환
   • 버블 정렬, 퀵 정렬

   2) 삽입(Insertion)

   • 키 값을 비교하고 자료를 삽입
   • 삽입 정렬, 셀 정렬

   3) 병합(Merging)

   • 키 값을 비교하고 자료를 병합
   • 2-way정렬, n-way정렬

   4) 분배(Distribution)

   • 키 값을 여러 개의 부분 집합으로 분배한 다음 이를 이용하여 자료를 정렬
   • 기수 정렬

   5) 선택(Selection)

   • 특정 자료구조를 통하여 정렬
   • 선택 정렬, 힙 정렬

정렬의 분류2

• 자료의 개수가 일정 개수를 넘어가면 반드시 효율적인 알고리즘 사용

-참고 자료

• 열혈 강의 자료구조(프리렉/이상진 지음)
• C언어로 쉽게 풀어쓴 자료구조(생능출판/천인국,공용해,하상호 지음)

정렬 알고리즘의 비교