数据结构基础(十)

Chapter 7 Sorting

See also here

Preliminaries

void X_sort(ElementType A[], int N);

Insertion Sort

void InsertionSort(ElementType A[], int N){
	int j, p;
	ElementType tmp;
	for(p = 1; p < N; ++p){
		tmp = A[p];
		for(j = p; j > 0 && A[j - 1] > tmp; --j){
			A[j] = A[j - 1];
		}
		A[j] = tmp;
	}
}

$T(N)=O(N)\sim O(N^2)$

Lower Bound for Simple Sorting Algorithm

Inversion: ordered pair (i, j) that i < j and A[i] > A[j]

For simple sorting algorithm, one swap operation removes one inversion, so that $T(N,I)=O(I + N)$

Theorem

Average inversions in an random array: $I=N(N-1)/4$

$T(N)=\Omega(N^2)$

Swap elements that are far apart could remove some inversions at once

Shellsort

多次间隔的插入排序

• Define an increment sequence $h_1=1<h_2<…<h_t$
• Define an $h_k$-sort at each phase for $k=t,t-1,…,1$

$h_{k-1}$-sort remains $h_k$-sort

Shellsort is an in-place but not stability sorting algorithm
Insertion sort is in-place and stability sorting algorithm

Shell’s Increment Sequence

$$h_t=floor(N/2),h_k=floor(h_{k+1}/2):1,2,4,8,…$$

// code omitted

$T_{wst}(N)=O(N^2)$

Pairs of increments are necessarily relatively prime

Hibbard’s Increment Sequence

$$h_k=2^k-1:1,3,7,15,…$$

$T_{wst}(N)=O(N^{3/2})>O(N\log N)$
$T_{avg}=O(N^{5/4})$

Sedgewick’s Increment Sequence

$$h_k=9\times4^i-9\times2^i+1\ \mathrm{or}\ 4^i-3\times2^i+1$$

$T_{wst}(N)=O(N^{4/3})$
$T_{avg}(N)=O(N^{7/6})$

Heapsort

in-place but not stable

Implement 1

{
	BuildHeap(H);
	for(i = 0; i < N; ++i)
		TmpH[i] = DeleteMin(H);
	for(i = 0; i < N; ++i)
		H[i] = TmpH[i];
}

$T(N)=N\log N$
$S(N)=2N$

Implement 2

See also

void percolateDown(ElemType* base, size_t begin, size_t end,int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){  
	size_t parent, lChild, rChild;  
	parent = begin, lChild = 2 * parent + 1, rChild = lChild + 1;  
	while(parent < end){  
		size_t max = parent;  
		if(lChild < end && !(*ptrCompFunc)(base + lChild, base + max))  
			max = lChild;  
		if(rChild < end && !(*ptrCompFunc)(base + rChild, base + max))  
			max = rChild;  
		if(parent == max)   break;  
		swap(base + parent, base + max);  
		parent = max, lChild = 2 * parent + 1, rChild = lChild + 1;  
	}  
}  

// main sort 
void heapSort(ElemType* base, size_t n, int (*ptrCompFunc)(const ElemType* x, const ElemType* y)){  
	for(size_t i = n / 2 - 1; ; --i){  
		percolateDown(base, i, n, ptrCompFunc);  
		if(i == 0)  break;  
	}  
	for(size_t i = n - 1; ; --i){  
		swap(base, base + i);  
		percolateDown(base, 0, i, ptrCompFunc);  
		if(i == 0)  break;  
	}  
}

$T_{avg}(N)=2N\log N-O(N\log\log N)$

Mergesort

See Also

Quicksort

the fastest (not) sorting algorithm

See also

Implementation

$T_{bst}(N)=O(N\log N)$

$T_{wst}(N)=O(N^2)$

Picking the Pivot

1. wrong way

Pivot = A[0]

2. safe maneuver

Pivot = random select from A[]

random number generation is expensive

3. median-of-three partitioning

Pivot = median(left, center, right)