알고리즘 5강 (정렬)

학습개요

1. 이번 강의에서는 우선 힙 자료구조를 이용한 비교 기반의 힙 정렬에 대해서 살펴본다. 그리고 지금까지 학습한 정렬 알고리즘들과는 정렬 방식이 다른, 즉 비교 기반이 아닌 데이터의 분포 특성을 이용한 정렬 알고리즘으로서 계수 정렬, 기수 정렬, 버킷 정렬에 대해서 다룬다.

 학습목표

1. 힙 자료구조의 개념과 장점을 이해할 수 있다.
2. 힙 정렬의 수행 과정과 특징을 이해할 수 있다.
3. 계수 정렬, 기수 정렬, 버킷 정렬의 개념, 처리 과정 및 특징을 이해할 수 있다.

 주요용어

1. (최대) 힙 (maximum heap)
   - 각 노드의 값이 자신의 자식 노드의 값보다 크거나 같다는 조건을 만족하는 완전 이진 트리
2. 힙 정렬 (heap sort)
   - 힙 구조의 장점을 이용한 정렬 알고리즘
   - 힙 구조의 장점 → 임의의 값 삽입과 최댓값 삭제가 용이
3. 계수 정렬 (counting sort)
   - 주어진 데이터 중에서 자신보다 작거나 같은 값을 갖는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 알고리즘
4. 기수 정렬 (radix sort)
   - 주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리즘을 적용하여 정렬하는 알고리즘
5. 버킷 정렬 (bucket sort)
   - 주어진 데이터의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든 뒤, 각 데이터를 해당하는 버킷에 넣고, 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후, 버킷 순서대로 각 데이터를 나열하여 정렬하는 알고리즘

정리하기

1. 1. 힙 정렬
     ⦁ (최대)힙 → 각 노드의 값이 자신의 자식 노드의 값보다 크거나 같은 완전 이진트리
     - 장점 → 임의의 값 삽입과 최댓값 삭제가 쉬움
     - 일차원 배열로 구현 → 간단한 인덱스 계산을 통해 부모/자식 노드에 대한 용이한 접근이 가능
     ⦁ 힙 정렬 → 힙 자료구조를 이용한 정렬
     - 단계 1 → 주어진 일차원 배열을 초기 힙으로 구축하는 단계
     - 단계 2 → 최댓값 삭제 및 힙으로 재구성하는 과정을 반복하는 단계 → 힙의 루트 노드의 값과 힙에서의 맨 마지막 노드의 값을 교환한 후, 루트 노드로부터 리프 노드로 진행하면서 힙의 조건을 만족하도록 조정하는 과정을 반복
     ⦁ 초기 힙을 구축하는 두 가지 방법 → ① 입력 배열의 각 원소에 대해 힙에서의 삽입 과정을 반복하는 방법, ② 입력 배열을 우선 완전 이진트리를 만든 다음 아래에서 위로 그리고 오른쪽에서 왼쪽으로 진행하면서 각 노드의 아랫부분에 대해서 힙의 조건을 만족시키는 방법
     ⦁ O(nlogn), 불안정적, 제자리
2. 2. 계수 정렬
     ⦁ 데이터 분포 정보를 활용한 정렬 알고리즘 → 계수 정렬, 기수 정렬, 버킷 정렬 → 선형 시간의 성능을 가짐
     ⦁ 주어진 데이터 중에서 자신보다 작거나 같은 값을 갖는 데이터의 개수를 계산하여 정렬할 위치를 찾아 정렬하는 방식 → 우선 입력값의 범위만큼 배열을 할당하고, 각 입력값에 대한 출현횟수의 누적값을 계산한 후, 입력 배열의 끝에서부터 시작해서 각 입력값이 정렬 후 위치할 곳을 바로 찾아서 정렬하는 방법
     ⦁ 입력값의 범위가 데이터의 개수보다 작거나 비례할 때 → O(n)
     ⦁ 안정적 정렬, 제자리 정렬이 아님, 보편성이 떨어짐
3. 3. 기수 정렬
     ⦁ 데이터 분포 기반의 정렬 알고리즘
     ⦁ 입력값을 자릿수별로 구분해서 부분적인 비교를 통해 정렬하는 방식 → 주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리즘을 적용하여 정렬하는 방식
     ⦁ 입력 데이터의 자릿수가 상수일 때 → O(n)
     ⦁ 안정적 정렬, 제자리 정렬이 아님
4. 4. 버킷 정렬
     ⦁ 데이터 분포 기반의 정렬 알고리즘
     ⦁ 주어진 데이터들의 값의 범위를 균등하게 나누어 여러 개의 버킷을 만든 뒤, 각 데이터를 해당하는 버킷에 넣고, 각 버킷을 삽입 정렬과 같은 안정적인 정렬을 수행한 후, 버킷 순서대로 각 데이터를 나열하는 정렬 방식
     ⦁ 입력 데이터의 값이 확률적으로 균등하게 분포하고, 버킷의 개수가 입력 데이터의 개수에 비례할 때 → O(n)
     ⦁ 안정적 정렬, 제자리 정렬이 아님
5. 5. 정렬 알고리즘의 비교
      ⦁ 표 확인 <아래>

 정리하기_계속