Maintenance script: Repair batch-0004 pages from live compare

2026-03-27T00:37:13Z

Repair batch-0004 pages from live compare

← Older revision		Revision as of 00:37, 27 March 2026
Line 8:		Line 8:
	* 수행 시간 : O(nlgn)		* 수행 시간 : O(nlgn)
	* 사용하는 자료구조 : Heap - 자료구조 시간엔 Complete Binary Tree로 구현방법을 배웠었다.		* 사용하는 자료구조 : Heap - 자료구조 시간엔 Complete Binary Tree로 구현방법을 배웠었다.
	* heap이 무엇인가 하면? A[~~Parent[[i~~)]] >= A[i] (결국 부모는 무조건 자식보다 커야한단 말입니다.)		* heap이 무엇인가 하면? A[Parenti) >= A[i] (결국 부모는 무조건 자식보다 커야한단 말입니다.)
	** Parent(i) : floors( (i-1) / 2 ) (책에는 맨 처음 index가 1이지만.. 우린 0에 익숙하므로..)		** Parent(i) : floors( (i-1) / 2 ) (책에는 맨 처음 index가 1이지만.. 우린 0에 익숙하므로..)
	** Left(i) : 2i + 1		** Left(i) : 2i + 1
Line 60:		Line 60:

	----		----
	["[~~[Lovely]]boy^_^~~/ExtremeAlgorithmStudy"]		[[［Lovely］boy＾_＾/ExtremeAlgorithmStudy]]

imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:37Z

New page

__TOC__

= 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"]

［Lovely］boy＾ ＾/ExtremeAlgorithmStudy/SortingAndOrderStatistics - Revision history

Maintenance script: Repair batch-0004 pages from live compare

imported>Unknown at 05:28, 7 February 2021

［Lovely］boy＾＾/ExtremeAlgorithmStudy/SortingAndOrderStatistics - Revision history