Chap04. Sorting

Quick-Sort :: O(nlgnnlgnnlgn)

Outline of average case analysis for quick-sort(informal analysis)

Algorithm inPlaceQuickSort(S, l, r)		// preorder traversal
	/* Input: sequence S, ranks l and r
	Output sequence S with the
		elements of rank between l and r
		rearranged in increasing order */
	if l >= r
		return
	i <- a random integer between l and r
	x <- S.elemAtRank(i)
	(h, k) <- inPlacePartition(x)		// visit()
	inPlaceQuickSort(S, l, h-1)		// L
	inPlaceQuickSort(S, k+1, r)		// G

In-Place Partitioning

pivot = 6
L, E U G

jとkが出会うまで次の3つのステップを繰り返します
1.jを使用してpivot以上の値を検索
2.kを使用してpivot未満の値を検索
3.2つのインデックスjとkを

Merge sort :: O(nlgnnlgnnlgn)

Merge(A, B, C)
if (A is empty)
	rest of C = rest of B
else if (B is empty)
	rest of C = rest of A
else if (first of A ≤ first of B)
	first of C = first of A
	Merge (rest of A, B, rest of C)
else
	first of C = first of B
	Merge (A, rest of B, rest of C)
return

Using Divide and Conquer: Mergesort

void mergeSort(Element[] E, int first, int last)	// postorder traversal
if (first < last)
	int mid = (first+last)/2;
	mergeSort(E, first, mid);		// left
	mergeSort(E, mid+1, last);		// right
	merge(E, first, mid, last);		// visit()
return;