10강 제5강 정렬 알고리즘 (합병, 퀵, 힙, 비교기반하한)

5.6 합병 정렬과 퀵 정렬

2020/04/26 - [방송통신대학/알고리즘] - 3강 제 2 장 분할정복 알고리즘

3강 제 2 장 분할정복 알고리즘

2020/04/27 - [방송통신대학/알고리즘] - 4강 제2장 분할정복 알고리즘 2

4강 제2장 분할정복 알고리즘 2

합병 정렬과 퀵 정렬( 3, 4 강 참조 ) 은 분할 정복 방법이 적용된 알고리즘이다.

 

 

 

5.6.1 합병정렬 

(1) 성능과 특징

 

>> 최선, 최악, 평균 수행 시간이 모두 O(nlogn)

>> 안정적인 정렬 알고리즘

>> 제자리 정렬 알고리즘이 아님

 

 

 

 

 

 

 

 

5.6.2 퀵 정렬

 

 

 

배열의 첫번째 원소를 피벗으로 정한 후

피벗이 제자리를 잡게 한 뒤 피벗을 중심으로 

왼쪽과 오른쪽을 부분배열로 만들고 이를 반복 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(1) 성능과 특징

>> 최악 수행 시간 O(n2),최선/평균 수행 시간 O(nlogn)

    >>피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음

>> 안정적이지 않은 정렬 알고리즘

>> 제자리 정렬 알고리즘 

 

 

 

 

5.7 힙 정렬

5.7.1 개념과 원리 

>힙 자료구조의 장점을 활용한 정렬 방식

  - 임의의 값 삽입과 최댓값 삭제가 용이

> 힙 ( heep )

  - 완전 이진 트리

  - 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다. ( 최대 힙 )

  - 자신의 자식노드 의 값보다 작거나 같다. ( 최소 힙 ) 

 

 

힙의 장점

 

임의의 값의 삽입 후 :: 힙의 조건 : 자식노드는 부모 노드보다 크거나 같다. (작거나 같다. ) >> 자식과 부모 교체

 

 

 

5.7.2 알고리즘 

초기 힙 구축 

> 1차원 입력 배열  >>(변환) >> 힙

> 두 가지 접근 방법

 * 방법 1 >> 주어진 입력 배열의 각 원소에 대한 힙에서의 삽입 과정을 반복

 * 방법 2 >> 주어진 입력 배열을 우선 완전 이진 트리로 만든 다음에 아래에서 위로 그리고 오른쪽에서 왼쪽으로 진행하면서 각 노드에 대해서 힙의 조건을 만족할 수 있도록 조정

 

5.7.3 성능 분석 

> 최선,최악,평균의 경우 모두 O(nlogn)

  > 초기 힙 생성,최댓값 삭제 및 힙 재구성 

    * 바깥 루프 → 입력 크기 n에 비례 

    * 안쪽 루프 → 완전 이진 트리의 높이 logn에 비례

 

 

5.7.4 특징 

> 안정적이지 않은 정렬 알고리즘

> 제자리 정렬 알고리즘 

 

 

 

5.8 비교 기반 정렬의 하한 

> 키값과 키값을 직접적으로 비교해서 크고 작음에 따라 순서를 정하는 방식

  * 기본 성능 O(n2)인 알고리즘 → 버블 정렬,선택 정렬,삽입 정렬,셸 정렬

  * 향상된 성능 O(nlogn)인 알고리즘 → 합병 정렬, 퀵 정렬, 힙 정렬

> 비교 기반으로서 O(nlogn)보다 더 효율적인 성능의 정렬 알고리즘을 개발할 수 있는가? 

  - 비교 기반 정렬 알고리즘의 하한이 O(nlogn)인가? 

    * 하한 lowerbound→ 최소한으로 필요한 성능,가장 좋은 성능

 

(1) 특징

> n=3인 세 개의 다른 숫자 a,b,c를 정렬하는 결정 트리