IM

작지만 단단하게

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.
https://github.com/ejImDev/data_structure_study.git

힙정렬

  • 힙 자료구조를 이용하는 정렬
  • 먼저 배열에 저장된 데이터의 키를 우선순위로 하는 최대힙을 구성
  • 루트노드의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 교환한 후 힙 크기를 1로 감소시키고 루트노드로 이동한 숫자로 인해 위배된 힙속성을 downheap 연산으로 복원
  • 힙정렬은 이 과정을 반복하여 나머지 원소들을 정렬

수행 시간

  • 상향식으로 힙을 구성 : O(N) 시간
  • 루트와 힙의 마지막 노드를 교환한 후 downheap() 수행 : O(logN) 시간
  • 루트와 힙의 마지막 노드를 교환하는 횟수 : N-1번
  • 총 수행시간 : O(N) + (N-1) * O(logN) = O(NlogN)
  • 힙정렬은 어떠한 입력에도 항상 O(NlogN) 시간이 소요
  • 루프 내의 코드가 길고, 비효율적인 캐시메모리 사용에 따라 특히 대용량의 입력을 정렬하기에 부적절
  • C/C++ 표준라이브러리(STL)의 partial_sort(부분 정렬)는 힙정렬로 구현됨
    • 부분 정렬 : 가장 작은 k개의 원소만 출력

합병 정렬

  • 크기가 N인 입력을 N/2 크기를 갖는 입력 2개로 분할하고, 각각에 대해 재귀적으로 합병정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병하는 정렬알고리즘
  • 합병이란 두 개의 각각 정렬된 입력을 합치는 것과 동시에 정렬하는 것
  • 분할정복 알고리즘 : 입력을 분할하여 분할된 입력 각각에 대한 문제를 재귀적으로 해결한 후 취합하여 문제를 해결하는 알고리즘들

수행시간

  • 어떤 입력에 대해서도 O(NlogN)시간 보장
  • 입력 크기 N=2^k^ 가정 (2의 차수배일 때)

퀵 정렬

  • 입력의 맨 왼쪽 원소(피벗)를 기준으로 피벗보다 작은 원소들과 큰 원소들을 각각 피벗의 좌우로 분할한 후, 피벗보다 작은 원소들과 피벗보다 큰 원소들을 각각 재귀적으로 정렬하는 알고리즘

### 수행시간

  • 최선경우 : 피벗이 매번 입력을 1/2씩 분할 하는 경우 T(N) = 2T(N)+cN, T(1) = C’으로 합병정렬의 수행시간과 동일. 여기서 c와 c’는 각각 상수
  • 평균경우 : 피벗이 입력을 다음과 같이 분할할 확률이 모두 같을 때, T(N) = O(NlogN)으로 계산
  • 최악경우 : 피벗이 매번 가장 작을 경우 또는 가장 클 경우로 피벗보다 작은 부분이나 큰 부분이 없을 때
  • 따라서 T(N) = T(N-1) + N-1, T(1) = 0
    • T(N) 크기가 N인 입력에 대해 정렬이 수행하는 원소 비교 횟수(시간)

  • T(N) = T(N-1) + N-1 = [T((N-1)-1)+(N-1)-1] + N-1
    = T(N-2) + N-2 + N-1
    = T(N-3) + N-3 + N-2 + N-1
    …
    = T(1) + 1 + 2 + … + N-3 + N-2 + N-1, T(1) = 0
    = N(N-1)/2
    = O(N^2^)

    • 퀵 정렬은 평균적으로 빠른 수행시간을 가지며, 보조배열을 사용하지 않음
    • 최악경우 수행시간 O(N^2^)이므로, 성능 향상 방법들을 적용하여 사용하는 것이 바람직함
    • 퀵 정렬은 원시 타입 데이터를 정렬하는 자바 Standard Edition 6의 시스템 sort에 사용
    • C언어 라이브러리의 qsort, Unix, g++, Visual C++, Python 등에서도 퀵정렬을 시스템 정렬로 사용
    • 자바 SE 7에서는 2009년에 고안한 이중 피벗퀵 정렬이 사용

기수정렬

  • 키를 부분적으로 비교하는 정렬
    • 키가 숫자로 되어있으면, 각 자릿수에 대해 키를 비교
    • 기(radix)는 특정 진수를 나타내는 숫자들
      • 10진수의 기 = 0,1,2, …, 9 / 2진수의 기 = 0,1
    • LSD(Least Significant Difit) 기수정렬 : 자릿수 비교를 최하위 숫자로부터 최상위 숫자 방향으로 정렬
    • MSD(Most Significant Difit 기수 정렬 : 반대 방향으로 정렬

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/9sVo_T0Qzgw

Updated: