[[TableOfContents]]

= Sorting Algorithms =
 * Bubble Sort나 Shell Sort(? 맞나--; 이름이 생각이 안나네) 같이 좀 수행성능이 떨어지는건 아예 안다루나 봅니다.

== Heapsort ==
=== Foundation of Heapsort ===
 * 수행 시간 : O(nlgn) 
 * 사용하는 자료구조 : Heap - 자료구조 시간엔 Complete Binary Tree로 구현방법을 배웠었다.
 * heap이 무엇인가 하면? A[Parent[i)] >= A[i] (결국 부모는 무조건 자식보다 커야한단 말입니다.)
  * Parent(i) : floors( (i-1) / 2 ) (책에는 맨 처음 index가 1이지만.. 우린 0에 익숙하므로..)
  * Left(i) : 2i + 1
  * Right(i) : 2i + 2 - 뭐 이것들은 Binary Tree의 기초니..--;
  * height : 세타(lgn)

=== Maintaining the heap property ===
 * 제기랄. 모든 소스가 재귀다..--; 이해가 안간다 ㅠ.ㅠ

=== Building a Heap ===

=== The heapsort algorithm ===

=== Priority Queue ===
 * QuickSort에 자주 까이면서도(책에는 beat라는 표현을..) 존재하는 이유 중의 하나가 우선순위큐를 구현할때라는데..--a라고 써있네요..--;
 * 주요 기능
  * Insert
  * Maximum
  * Extract_Maximum
 
== Quicksort ==
 * 평균 수행 시간 : 세타(nlgn)
 * 최악의 시간 : 세타(n*n)
 * 근데 Heapsort보다 좋다고 한다. 왜인지는 아직 안 나왔군.
 * STL의 소트 알고리즘이 이걸 약간 변형시킨 거라고 하네요.
 * 여기서 잠깐, Comparison Sort(이건 또 뭐지?--;)는 아무리 빠르게 해봤자 세타(nlgn)보다는 빠르게 못한답니다.

=== Description ===
 * Divide and Conquer paradigm 을 쓴답니다.(보나마나 재귀군..--;)
 * 주요 프로시저
  * Divide (현재 배열을 둘로 나눈 다음 샤바샤바.--; 앞 배열의 원소들은 뒤 배열의 원소보다 작게..)
  * Conquer : 각각 소트 한다음
  * Combine : 합친다.

 * 모든 재귀 함수는 반복 함수로 만들수 있다는데..(증명도 됐다) .. 왜 이렇게 어려운 거샤 ㅠ.ㅠ

=== Performance of Quicksort ===
 * ...
 * 생전 듣도 보도 못한 풀이로 증명을 하고 있다. --;

== Sorting in linear time ==
 * 그래서 여기서 선형 시간 내에 정렬하는 방법이 나올...거 같네요.(이상하네)
 * 뭔가 다른 방법을 쓰나 봅니다. 정리해 나가면서 고쳐야겠죠.

=== Radix Sort (요건가 봅니다) ===

=== Bucket Sort (요것도?) ===

== Medians and Order Statistics ==
 * 뭐 몇번째로 작은 뭐, 몇번쨰로 큰 뭐 이런걸 선형시간(평균, 최악의 경우에는 세타(n*N))내에 찾을수 있는 방법이 있다네요.

----
["[Lovely]boy^_^/ExtremeAlgorithmStudy"]