1. Sorting Algorithms ¶
- Bubble Sort나 Shell Sort(? 맞나--; 이름이 생각이 안나네) 같이 좀 수행성능이 떨어지는건 아예 안다루나 봅니다.
1.1.1. Foundation of Heapsort ¶
- 수행 시간 : O(nlgn)
- 사용하는 자료구조 : Heap - 자료구조 시간엔 Complete Binary Tree로 구현방법을 배웠었다.
- heap이 무엇인가 하면? A[Parenti) >= Ai (결국 부모는 무조건 자식보다 커야한단 말입니다.)
- Parent(i) : floors( (i-1) / 2 ) (책에는 맨 처음 index가 1이지만.. 우린 0에 익숙하므로..)
- Left(i) : 2i + 1
- Right(i) : 2i + 2 - 뭐 이것들은 Binary Tree의 기초니..--;
- height : 세타(lgn)
1.1.2. Maintaining the heap property ¶
- 제기랄. 모든 소스가 재귀다..--; 이해가 안간다 ㅠ.ㅠ
1.1.5. Priority Queue ¶
- QuickSort에 자주 까이면서도(책에는 beat라는 표현을..) 존재하는 이유 중의 하나가 우선순위큐를 구현할때라는데..
a라고 써있네요..;
- 주요 기능
- Insert
- Maximum
- Extract_Maximum
1.2. Quicksort ¶
- 평균 수행 시간 : 세타(nlgn)
- 최악의 시간 : 세타(n*n)
- 근데 Heapsort보다 좋다고 한다. 왜인지는 아직 안 나왔군.
- STL의 소트 알고리즘이 이걸 약간 변형시킨 거라고 하네요.
- 여기서 잠깐, Comparison Sort(이건 또 뭐지?--;)는 아무리 빠르게 해봤자 세타(nlgn)보다는 빠르게 못한답니다.
- Divide and Conquer paradigm 을 쓴답니다.(보나마나 재귀군..--;)
- 주요 프로시저
- Divide (현재 배열을 둘로 나눈 다음 샤바샤바.--; 앞 배열의 원소들은 뒤 배열의 원소보다 작게..)
- Conquer : 각각 소트 한다음
- Combine : 합친다.
- 모든 재귀 함수는 반복 함수로 만들수 있다는데..(증명도 됐다) .. 왜 이렇게 어려운 거샤 ㅠ.ㅠ
1.2.2. Performance of Quicksort ¶
- ...
- 생전 듣도 보도 못한 풀이로 증명을 하고 있다. --;
1.3. Sorting in linear time ¶
- 그래서 여기서 선형 시간 내에 정렬하는 방법이 나올...거 같네요.(이상하네)
- 뭔가 다른 방법을 쓰나 봅니다. 정리해 나가면서 고쳐야겠죠.
1.4. Medians and Order Statistics ¶
- 뭐 몇번째로 작은 뭐, 몇번쨰로 큰 뭐 이런걸 선형시간(평균, 최악의 경우에는 세타(n*N))내에 찾을수 있는 방법이 있다네요.
["
Lovelyboy^_^
/ExtremeAlgorithmStudy"]
