Sorting Algorithm   정렬 알고리즘

(2019-03-09)
1. 정렬 알고리즘 (Sorting Algorithm)

  ㅇ 정렬 : 수많은 자료를 특정 목적에 맞게 순서있게 재배열하는 것
     - 레코드들을 키 값의 순서로 재배열하는 것
        . (키 : 자료를 정렬하는데 사용되는 값들 ☞ 키(Key) 참조)

  ㅇ 정렬 알고리즘 : 정렬을 수행하는 다양한 알고리즘
      - 탐색의 효율성, 실용성, 이론 설명 등을 위해서도 정렬 알고리즘이 필요함
      * 100개 이상의 정렬 알고리즘들이 개발되어 왔음


2. 정렬 알고리즘 분류

  ㅇ 정렬 장소에 따른 분류
     - 내부 정렬 : 정렬 전 모든 데이터가 주기억장치에 올라와있음
     - 외부 정렬 : 대부분 데이터가 외부기억장치에 있고, 필요시 일부분씩 만 주기억장치에 올림
     - 제자리 정렬 : 입력 자료에 할당된 메모리 이외 일정 상수 만큼 작은 추가 메모리 만 필요
        . 例) 교환 정렬, 삽입 정렬, 선택 정렬

  ㅇ 정렬의 안정함에 따른 분류
     - 안정함 : 자료의 입력 순서 그대로 정렬
        . (키 값이 값을 경우에도 입력 순서 그대로 정렬. 특히 다중 키 정렬시 중요)
     - 안정하지 못함 : 자료의 입력 순서가 바뀔 수 있는 정렬

  ㅇ 단순성,효율성에 따른 분류
     - 단순하지만 비효율적 : 버블 정렬, 선택 정렬, 삽입 정렬
     - 복잡하지만 효율적   : 퀵 정렬,  정렬, 병합 정렬, 기수 정렬 등
 
  ㅇ 실행 방식에 따른 분류
     - 비교 기반 정렬 방식
        . 항목 비교하며 `교환`하는 방식 : 버블 정렬, 선택 정렬, 퀵 정렬
        . 적절한 위치에 `삽입`하는 방식 : 삽입 정렬, 셀 정렬
        . 자료를 먼저 분할하고, `병합`하면서 정렬하는 방식 : 병합 정렬
     - 키 값의 분포을 이용하는 정렬 방식
        . 기수 정렬, 계수 정렬


3. 주요 정렬 알고리즘버블 정렬 (Bubble Sort) 또는 교환 정렬 (Exchange Sort)
     - 정렬 방법
        . 이웃 요소 간에 대소 비교하고, 필요시 교환을 수행하며,
        . 이 과정을 전체 자료에 걸쳐 반복 수행
     - 주요 연산 : 비교(compare), 교환(swap)
     - 키 비교 횟수 : 총 n(n-1)/2회
     - 계산 효율성 : O(n2)

     * 교환 정렬 (Exchange Sort)은, 버블 정렬과 거의 같으나, 
        . 인접 위치의 두 수간에 비교/교환이 아니라,
        . 두 수의 위치 중 하나를 고정하고 다른 위치를 이동하며 비교/교환을 수행

  ㅇ 선택 정렬 (Selection Sort)
     - 정렬 방법
        . 가장 큰/가장 작은 자료를 선택하고(찾고),
        . 선두로 옮기는(교환하는) 과정을 반복적으로 수행
     - 주요 연산 : 비교(compare), 교환(swap)
     - 키 비교 횟수 : 총 n(n-1)/2회로써, `버블 정렬,교환 정렬`과 같음
     - 계산 효율성 : O(n2)

  ㅇ 삽입 정렬 (Insertion Sort)
     - 정렬 방법
        . 선택한 요소를 그보다 더 앞쪽의 알맞은 위치로의 삽입을 반복적으로 수행
     - 특징 : 크기가 작은 정렬 문제에 효율적

  ㅇ 병합 정렬 (Merging Sort)
     - 자료를 여러 부분 집합으로 나누고 이를 병합하면서 정렬하는 방식
     - 계산 효율성 : O(nlogn)

  ㅇ  정렬 (Heap Sort)
     - 트리 구조를 통해 정렬하는 방식

  ㅇ 퀵 정렬 (Quick Sort)
     - 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
        . 1962년 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 발표
     - 주요 연산 : 비교(compare), 교환(swap)
     - 계산 효율성 : O(nlogn)

  ㅇ 기수 정렬 (Radix Sort)
     - 키 값을 여러 부분 집합으로 분배한 후 이를 이용하는 정렬하는 방식


[정렬 알고리즘] 1. 정렬 알고리즘 2. 버블 정렬 3. 선택 정렬 4. 삽입 정렬

 
        최근수정     요약목록     참고문헌