［Lovely］boy＾ ＾/ExtremeAlgorithmStudy/SortingAndOrderStatistics

Sorting Algorithms

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

Heapsort

Foundation of Heapsort

• 수행 시간 : O(nlgn)
• 사용하는 자료구조 : Heap - 자료구조 시간엔 Complete Binary Tree로 구현방법을 배웠었다.
• heap이 무엇인가 하면? A[Parenti) >= 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

• 제기랄. 모든 소스가 재귀다..--; 이해가 안간다 ㅠ.ㅠ

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

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

Medians and Order Statistics

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

---

［Lovely］boy＾_＾/ExtremeAlgorithmStudy