Simple in Complex with Simple

 총 앞선 6가지 정렬 (버블,선택,삽입,병합,힙,퀵)의 비교 표

1. 개요

 퀵 정렬은 속도는 같은 O(nlogn)이지만 모든 정렬중에서 일반적으로 가장 빠름.

 하지만 최악의 경우 속도는 O(n^2)에 수렴. (최악의 경우는 이미 정렬된 데이터면서 pivot으로 맨 우측을 선택할 때)

 병합 정렬과 마찬가지로 분할 정복의 좋은 예.

 하지만 재귀 전 작업을 하기 때문에 재귀 오버헤드가 큼.(아래 출력사진에서 확인) 

 병합 정렬은 높은 안정성으로 인해 데이터 크기 1억까지도 수행할 수 있지만 퀵 정렬은 현재 데이터 크기 10만에 터짐.

 두 번째 다른 점은 병합 정렬은 항상 1/2로 나누지만 퀵 정렬은 나누는 기준(pivot)이 다름.

 알고리즘 4단계

 (1) 배열을 2개로 나누는데 필요한 기준(pivot) 찾기.

 (2) pivot을 찾는 과정에서 정렬이 이뤄짐.

 (3) pivot으로 인해 나뉜 두 배열이 위의 (1)-(2) 과정을 반복함.

 세밀한 설명은 코드 주석으로 처리함.

2. 코드

2-1) 메인

2-2) 퀵 정렬 알고리즘

2-3) 출력

      *터진 이유: Stack Overflow 에러로 재귀 오버헤드가 쌓여서 발생

3. 해설

 병합 정렬보다 나은 장점

 (1) 평균적인 경우 병합 정렬보다 조금 더 빠를 수 있다.

 (2) 병합 정렬은 배열로 구성할 경우 임시 배열로인해 공간 복잡도가 O(n)이 필요.(리스트 기반일 경우 O(1))

 기억해야할 것

 (1) 인덱스의 범위는 정교해야한다. 인덱스 범위 한 치라도 틀릴 경우 알고리즘은 무너진다.

 (2) 결국 병합 정렬과 사촌과 같은 관계다.

1. 개요

 우선순위 큐의 특징을 살린 알고리즘.

 한번의 삽입, 삭제 과정이 이론적으로 O(logn)의 시간이 걸림.

 전체 데이터 삽입, 삭제 과정은 이론적으로 O(nlogn)의 시간이 걸림.

 힙 정렬은 힙 내부에서 정렬되는 속성을 이용.

 알고리즘은 단순히 데이터 전체를 힙에다 넣었다가 빼는 과정.

 그러므로 O(nlogn)+O(nlogn) = O(2nlogn) => O(nlogn)

 힙(우선순위큐)에 대한 설명이 아님.

 이번 코드는 STL 라이브러리의 우선순위큐 사용. 하지만 속도가 버블 정렬보다 느림. (추후 직접 구성하여 비교해봐야 함)

2. 코드

2-1) 메인

2-2) 힙(우선순위큐) 정렬 알고리즘

2-3) 출력

3. 해설

 C++의 STL 라이브러리의 우선순위큐를 이용해서 정렬시켰지만 그 속도가 현재 버블 정렬보다 느리다. 

 데이터가 10000개 이상일 시 시간이 5분이 걸려도 계산을 끝마치지 못했다.

 힙 정렬을 하려면 STL 라이브러리 사용않고 직접 힙을 구성해야 할 듯하다.

 기억해야할 것

 (1) 그냥 병합 정렬이나 퀵 정렬 쓰는 것이 낫다.

 (2) 그러나 우선순위큐의 원리는 알아야한다. (추후 작성)