U E D R , A S I H C RSS

[Lovely]boy^_^/Extreme Algorithm Study/Sorting And Order Statistics


1. Sorting Algorithms

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

1.1. Heapsort

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.3. Building a Heap


1.1.4. The heapsort algorithm


1.1.5. Priority Queue

  • QuickSort에 자주 까이면서도(책에는 beat라는 표현을..) 존재하는 이유 중의 하나가 우선순위큐를 구현할때라는데..a라고 써있네요..;
  • 주요 기능
    • Insert
    • Maximum
    • Extract_Maximum

1.2. Quicksort

  • 평균 수행 시간 : 세타(nlgn)
  • 최악의 시간 : 세타(n*n)
  • 근데 Heapsort보다 좋다고 한다. 왜인지는 아직 안 나왔군.
  • STL의 소트 알고리즘이 이걸 약간 변형시킨 거라고 하네요.
  • 여기서 잠깐, Comparison Sort(이건 또 뭐지?--;)는 아무리 빠르게 해봤자 세타(nlgn)보다는 빠르게 못한답니다.

1.2.1. Description

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

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

1.2.2. Performance of Quicksort

  • ...
  • 생전 듣도 보도 못한 풀이로 증명을 하고 있다. --;

1.3. Sorting in linear time

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

1.3.1. Radix Sort (요건가 봅니다)


1.3.2. Bucket Sort (요것도?)


1.4. Medians and Order Statistics

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


["Lovelyboy^_^/ExtremeAlgorithmStudy"]
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.3958 sec