Sorting Algorithm   정렬 알고리즘

(2023-09-08)

정렬 , in-place 정렬, 안정 정렬


1. 정렬 이란?

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

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

  ㅇ 정렬 알고리즘의 구성 요소
     - 비교 연산 (compare) : 키 값 비교
     - 이동 연산 (swap) : 키 값 비교 후, 자료의 위치 바꿈(교환)


2. 정렬 알고리즘의 특징별 분류

  ㅇ 정렬 수행시 데이터 저장 위치에 따른 분류
     - 내부 정렬 (internal sort)
        . 정렬 전 모든 데이터주기억장치에 올라와있음
        . 따라서, 대용량 데이터에는 적용 어려움
        . 例) 교환 정렬, 삽입 정렬, 선택 정렬 등
     - 외부 정렬 (external sort)
        . 정렬 전 모든 데이터외부기억장치에 있고, 
        . 필요시 일부분씩 만 주기억장치에 올려 정렬
        . 속도가 느린 외부 보조기억장치를 사용하므로, 내부 정렬 보다 느림
        . 例) 병합 정렬 등

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

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

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

  ㅇ 정렬의 계산효율성에 따른 분류
     - 단순하지만 비효율적 : 버블 정렬, 선택 정렬, 삽입 정렬 등
        . 계산효율성평균적으로,  Θ(n2)
        . (실무에서는 거의 구현할 일 없으나, 이론적 비교 검토 필요)
     - 복잡하지만 효율적   : 퀵 정렬,  정렬, 병합 정렬, 기수 정렬 등
        . 계산효율성평균적으로,  Θ(n log n)

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


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

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

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

  ㅇ 삽입 정렬 (Insertion Sort)
     - 정렬 방법
        . 선택한 요소를 정렬된 영역에서 알맞은 위치를 찾아 삽입을 반복적으로 수행
     - 특징 : 크기가 작은 정렬 문제에 효율적
     - 계산 효율성 : O(n2)

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

  ㅇ 퀵 정렬 (Quick Sort)
     - 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용됨
     - 정렬 방법
        . 피봇 값을 선정해, 해당 값을 기준으로 정렬 수행
     - 계산 효율성 : O(nlogn)

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

  ㅇ 기수 정렬 (Radix Sort)
     - 정렬 방법
        . 키 값을 여러 부분 집합으로 분배한 후, 이를 이용하여 정렬 수행
        . 데이터의 자리수를 바탕으로 비교해가며, 정렬 수행

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


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"