Sorting Algorithm   정렬 알고리즘

(2019-12-23)

정렬

1. 정렬 이란?

  ㅇ 정렬 (Sorting)
     - 수많은 자료를 특정 목적에 맞게 순서있게 재배치하는 것
     - 컴퓨터에서는, 레코드들을 키 값의 순서로 재배치하는 것
        . (키 : 자료를 정렬하는데 기준이 되는 값들 ☞ 키(Key) 참조)

  ㅇ 정렬 알고리즘 (Sorting Algorithm)
     - 컴퓨터에서, 가장 많이 이용되는 연산 중 하나
        . 자료검색효율성 제고, 실용성, 이론 설명 등을 위해서도 정렬 알고리즘이 필요함
     - 정렬을 수행하는 다양한 알고리즘들이 있음
        . 100개 이상의 정렬 알고리즘들이 개발되어 왔음


2. 정렬 알고리즘 분류

  ㅇ 정렬 수행시 데이터 저장 위치에 따른 분류
     - 내부 정렬 : 정렬 전 모든 데이터주기억장치에 올라와있음
        . 교환 정렬, 삽입 정렬, 선택 정렬 등
     - 외부 정렬 : 모든 데이터가 외부기억장치에 있고, 필요시 일부분씩 만 주기억장치에 올려 정렬
        . 병합 정렬 등

  ㅇ 정렬 수행시 저장공간 필요량에 따른 분류
     - 제자리 정렬 : 입력 자료에 할당된 메모리 이외 일정 상수 만큼 작은 추가 메모리 만 필요
        . 즉, 입력 크기가 커지더라도 추가 저장공간이 필요치 않음
           .. 교환 정렬, 삽입 정렬, 선택 정렬 등

  ㅇ 정렬의 안정함에 따른 분류
     - 안정함 : 자료의 입력 순서 그대로 정렬
        . 입력시 키 값이 값을 경우에도, 입력되는 순서 그대로 유지됨
           .. 버블 정렬 등 
     - 안정하지 못함 : 자료의 입력 순서가 바뀔 수 있는 정렬
        . 다중 키 정렬시, 먼저 정렬한 내용이 보존되지 않는 경우

  ㅇ 재귀적 여부에 따른 분류
     - 재귀적 : 퀵 정렬
     - 비 재귀적 : 선택 정렬, 삽입 정렬
     - 둘 다 사용 : 병합 정렬

  ㅇ 정렬의 효율성에 따른 분류
     - 단순하지만 비효율적 : 버블 정렬, 선택 정렬, 삽입 정렬 등
        . 계산효율성평균적으로 Θ(n2)
     - 복잡하지만 효율적   : 퀵 정렬,  정렬, 병합 정렬, 기수 정렬 등
        . 계산효율성평균적으로 Θ(n log n)

  ㅇ 실행 방식에 따른 분류
     - 비교 기반의 정렬 방식
        . 항목 비교하며, `교환`하는 방식 : 버블 정렬, 선택 정렬, 퀵 정렬
        . 적절한 위치에, `삽입`하는 방식 : 삽입 정렬,  정렬
        . 자료를 먼저 분할하고, `병합`하면서 정렬하는 방식 : 병합 정렬
        . (비교 기반 정렬 방식의 특징)
           .. 키 값 전체를 비교의 대상으로 삼고 정렬 수행
           .. 키 값의 비교 횟수 만을 알고리즘 수행 시간으로 간주
     - 키 값의 분포 기반의 정렬 방식
        . 기수 정렬, 계수 정렬


3. 주요 정렬 알고리즘 요약버블 정렬 (Bubble Sort)
     - 가장 간단한 정렬 알고리즘
     - 정렬 방법
        . 이웃 요소 간에 대소 비교하고, 필요시 교환을 수행하며,
        . 이 과정을 전체 자료에 걸쳐 반복 수행
        . 비교를 좌(위)에서 우(아래)로 또는 우(아래)에서 좌(위)로도 진행 가능
     - 주요 연산 : 비교(compare), 교환(swap)
     - 계산 효율성 : O(n2)

  ㅇ 교환 정렬 (Exchange Sort) (때론, 버블 정렬과 동의어로 쓰이기도 함)
     - 정렬 방법 : 버블 정렬과 거의 같으나, 
        . 인접 위치의 두 수 간에 비교/교환이 아니라,
        . 두 수의 위치 중 하나를 고정하고 다른 위치를 이동하며 비교/교환을 수행
     - 계산 효율성 : O(n2)

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

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

  ㅇ  정렬 (Heap Sort)
     -  이라는 완전 이진 트리 구조를 통해 정렬하는 방식

  ㅇ 퀵 정렬 (Quick Sort)
     - 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
     - 주요 연산 : 비교(compare), 교환(swap)
     - 계산 효율성 : O(nlogn)

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

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


[정렬 알고리즘] 1. 정렬 알고리즘 2. 버블 정렬 3. 선택 정렬 4. 삽입 정렬 5. 병합 정렬 6. 퀵 정렬

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