usjing c++

file contains a brief description of what you are planning to accomplish in your project. Discuss the basic architecture of your system, such as main data structures, main components of the algorithm, design of the user-interface for input/output, etc.

Idea 1: Median finding, Order Statistics and Quicksort:

Median Finding:

Implement the following order statistics algorithms:

Median of Median with groups of 3, 5 and 7.

Randomized median finding algorithm.

Make your code generic enough so that it can answer order statistics for any k . For example, k = n 2 gives the median and k = n gives the max.

Quicksort:

Implement Quicksort where the pivot is chosen differently. Compare the performance of Quicksort with median as pivot with the following practical implementations:

Randomized Quicksort which chooses a random element in the array as the pivot.

(Simplified) real world quick sort with the following heuristics:

If L and R partitions are of unequal sizes, sort the smallest partition first.

If array size

Use the following idea for getting the pivot:

middle = (start+end)/2

if array size > 40

length = array size / 8

pivot1 = median (start, start - length, start - (2*length))

pivot2 = median (end, end+length, end + 2*length)

pivot3 = median (middle, middle-length, middle+length)

pivot = median (pivot1, pivot2, pivot3)

else

pivot = median (start, middle, end)

Compare the performance of different implementations of Quicksort. Test it with large arrays (e.g. 10000, 100000 or higher) with random elements.