정렬 알고리즘 개념

정렬의 기본 개념

• 정렬(Sort)의 개념
• 순서 업이 배열되어 있는 자료들을 재 배열 하는 것
• 오름차순(ascending)
• 내림차순(descending)

• 정렬의 대상
• 레코드
• 정렬의 기준
• 정렬 키(Sort Key)필드
  
  
• 정렬방법의 분류
• 실행 방법에 따른 분류
• 비교식 정렬(comparative sort)
  - 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환함으로써 정렬을 실행하는 방식
  
  
• 분산식 정렬(distribute sort)
  - 키 값을 기준으로 하여 자료를 여러 개의 부분집합으로 분해하고, 각 부분집합을 정렬함으로써 전체를
      정렬하는 방식
  
  
• 정렬방법의 분류
• 정렬 장소에 따른 분류
• 내부 정렬(Internal sort)
• 컴퓨터 메모리 내부에서 정렬
• 정렬 속도는 빠르지만 자료의 양이 메인 메모리의 용량에 따라 제한된다.
• 내부 정렬 종류
  - 교환 방식 : 키를 비교하고 교환하여 정렬(선택정렬, 버블정렬, 퀵정렬)
  - 삽입 정렬 : 키를 비교하고 삽입하여 정렬(삽입정렬, 셀정렬)
  - 병합 정렬 : 키를 비교하고 병합하여 정렬(2-way 병합, n-way 병합)
  - 분배 방식 : 키를 구성하는 값을 여러 개의 부분집합에 분배하여 정렬(기수 정렬)
  - 선택 방식 : 이진 트리를 사용하여 정렬(힙 정렬, 트리 정렬)
  
  
• 외부 정렬(external sort)
• 메모리의 외부인 보조 기억 장치에서 정렬
• 내부 정렬로 처리할 수 없는 대용량의 자료를 정렬
• 병합 방식 : 파일을 부분 파일로 분리하여 각각을 내부 정렬 방법으로 정렬하여 병합
                         (2-way병합, n-way병합)