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. 퀵 정렬
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
              1. 알고리즘 분류
              2. 그래프 알고리즘
          1.   기초 알고리즘
          2.   정렬 알고리즘
            1.   1. 정렬 알고리즘
                2. 버블 정렬
                3. 선택 정렬
                4. 삽입 정렬
                5. 병합 정렬
                6. 퀵 정렬
          3.   검색 알고리즘
        3.   알고리즘 전략
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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