[알고리즘] 정렬의 기본 및 개념

정렬의 개념

• 2개 이상의 자료를 작은 것부터 큰 것 혹은 큰 것부터 작은 것 순서로 재배열하는 것
• 키란?
  • 자료를 정렬하는데 사용하는 기준이 되는 특정 값
• 정렬은 컴퓨터 공학 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나이다.

정렬의 단위

• 레코드
  • 정렬시켜야 할 대상
  • 필드라고 하는 작은 단위로 나누어진다.

ex) 학생들의 레코드

• 이름, 학번, 주소, 전화번호 등이 필드가 될 것이다.
• 여러 필드 중 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 '키'라고 한다.

 

정렬 알고리즘의 개요

• 정렬 알고리즘을 평가하는 효율성의 기준
  1. 비교연산의 횟수
  2. 이동연산의 횟수

정렬 알고리즘

1. 단순하지만 비효율적인 알고리즘
   • 구현하기가 쉽지만 비효율적이다.
   • 삽입정렬
   • 선택정렬
   • 버블정렬
2. 복잡하지만 효율적인 알고리즘
   • 구현하기가 까다롭지만 효율적
   • 퀵정렬
   • 히프정렬
   • 합병정렬
   • 기수정렬

자료의 개수가 적다면 단순한 정렬 방법을 사용하는 것도 좋지만, 자료의 개수가 일정 이상 넘어가면 효율적인 알고리즘은 필수적이다.

 

정렬 방법의 분류

1. 실행 방법에 따른 분류
   • 비교식 정렬: 한 번에 두 개씩 비교하여 교환하는 방식
   • 분산식 정렬: 키 값을 기준으로 여러 개의 부분 집합으로 분해하고, 각 부분집합을 정렬 후 전체를 정렬하는 방식
2. 정렬 장소에 따른 분류
   • 내부 정렬: 정렬할 자료를 메인 메모리에 올려 정렬하는 방식. 정렬 속도가 빠르지만 메모리 용량에 따라 정렬할 수 있는 자료가 제한적이다.
     • 교환 방식: 키를 비교하고 교환하여 정렬
       • 선택정렬, 버블 정렬, 퀵정렬
     • 삽입 방식: 키를 비교하고 삽입하여 정렬하는 방식
       • 삽입 정렬, 쉘 정렬
     • 병합 방식: 키를 비교하고 병학하여 정렬하는 방식
       • 2-way 병합, n-way 병합
     • 분배 방식: 키를 구성하는 값을 여러 개의 부분 집합에 분배하여 정렬하는 방식
       • 기수 정렬
     • 선택 방식: 이진 트리를 사용하여 정렬하는 방식
       • 히프 정렬, 트리 정렬
   • 외부 정렬: 정렬할 자료를 보조 기억 장치에서 정렬하는 방식
     • 병합 방식: 파일을 부분적으로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합하는 정렬 방식
       • 병합 방식