CLRS 9.1 Largest i numbers in sorted order

http://clrs.skanev.com/09/problems/01.html

Given a set of n numbers, we wish to find the i largest in sorted order using a comparison based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running time of the algorithms in terms of n and i.

1. Sort the numbers, and list the i largest
2. Build a max-priority queue from the numbers, and call `EXTRACT-MAX` i times
3. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the i largest numbers.

Sorting

We can sort with any of the nlgn algorithms, that is, merge sort or heap sort and then just take the first i elements linearly.

This will take nlgn+i time.

Max-priority queue

We can build the heap linearly and then take each of the largest i elements in logarithmic time.

This takes n+ilgn.

Partition and sort

Let's assume we use the SELECT algorithm from the chapter. We can find the ith order statistic and partition around it in n time and then we need to do a sort in ilgi.

This takes n+ilgi

https://github.com/gzc/CLRS/blob/master/C09-Medians-and-Order-Statistics/problem.md

Given a set of n numbers, we wish to find the i largest in sorted order using a comparison- based algorithm. Find the algorithm that implements each of the following methods with the best asymptotic worst-case running time, and analyze the running times of the algorithms in terms of n and i.

a. Sort the numbers, and list the i largest. b. Build a max-priority queue from the numbers, and call EXTRACT-MAX itimes. c. Use an order-statistic algorithm to find the ith largest number, partition around that number, and sort the ilargest numbers.

a和b的代码在这里.code. 如果先排序的话，就需要O(nlgn)+O(i)的时间. 用堆的话，需要O(n)+O(ilogn)的时间.

	def sort1(items, i): items = sorted(items,reverse=True)
	return items[:i]
	def sort2(items, i):
	pq = PriorityQueue()
	for element in items:
	pq.put((-element, element))
	array = []
	for k in range(i):
	array.append(pq.get()[1])
	return array

对于c，code 利用顺序统计量的话，找到这个值需要O(n)的时间，然后需要对i个数排序需要O(ilogi)时间.

	// A simple function to find median of arr[]. This is called // only for an array of size 5 in this program.
	int findMedian(int arr[], int n)
	{
	sort(arr, arr+n); // Sort the array
	return arr[n/2]; // Return middle element
	}
	// Returns k'th smallest element in arr[l..r] in worst case
	// linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
	int kthSmallest(int arr[], int l, int r, int k)
	{
	if (k > 0 && k <= r - l + 1)
	{
	int n = r-l+1; // Number of elements in arr[l..r]
	// Divide arr[] in groups of size 5, calculate median
	// of every group and store it in median[] array.
	int i, median[(n+4)/5]; // There will be floor((n+4)/5) groups;
	for (i=0; i<n/5; i++)
	median[i] = findMedian(arr+l+i*5, 5);
	if (i*5 < n) //For last group with less than 5 elements
	{
	median[i] = findMedian(arr+l+i*5, n%5);
	i++;
	}
	// Find median of all medians using recursive call.
	// If median[] has only one element, then no need
	// of recursive call
	int medOfMed = (i == 1)? median[i-1]:kthSmallest(median, 0, i-1, i/2);
	// Partition the array around a random element and
	// get position of pivot element in sorted array
	int pos = partition(arr, l, r, medOfMed);
	if (pos-l == k-1)
	return arr[pos];
	if (pos-l > k-1)
	return kthSmallest(arr, l, pos-1, k);
	return kthSmallest(arr, pos+1, r, k-pos+l-1);
	}
	return INT_MAX;
	}
	void swap(int *a, int *b)
	{
	int temp = *a;
	*a = *b;
	*b = temp;
	}
	// It searches for x in arr[l..r], and partitions the array
	// around x.
	int partition(int arr[], int l, int r, int x)
	{
	int i;
	for (i=l; i<r; i++)
	if (arr[i] == x)
	break;
	swap(&arr[i], &arr[r]);
	i = l;
	for (int j = l; j <= r - 1; j++)
	{
	if (arr[j] <= x)
	{
	swap(&arr[i], &arr[j]);
	i++;
	}
	}
	swap(&arr[i], &arr[r]);
	return i;
	}
	// Driver program to test above methods
	int main()
	{
	int arr[] = {12, 3, 5, 7, 4, -2, 26};
	int n = sizeof(arr)/sizeof(arr[0]), k = 3;
	int r = kthSmallest(arr, 0, n-1, k);
	vector<int>v;
	for(int i = 0;i < n;i++)
	if(arr[i] >= r)
	v.push_back(arr[i]);
	sort(v.begin(), v.end());
	for(auto e : v)
	cout << e << " ";
	return 0;
	}