Median finding, Order Statistics and Quick Sort

Thanks For Listening

Order Statistics

In statistics, the kth order statistic of a statistical sample is equal to its kth-smallest value.[1] 

Example

4th order statistic

Lower median = floor(n/2)

Upper median = ceiling(n/2)

Where n = number of elements in the array

(Simplified) real world quicksort

Deterministic algorithm

(Simplified) real world quicksort with the following :

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

ii. if array size <= 10, use insertion sort

Number of comparisons in DeterministicSelect is O(n). same as quickselect (linear time efficiency )

Running time

//Input array A with size n and k ≤ n.

DeterministicSelect(A[0…n-1],K)

1)Divide array A to n/5 groups (each with size 5)

2)Look for the median in each group.

3) calculate the median of medians recursively. Say this is (p).

5)Select p to be the pivot and split A into 2 sub-arrays - sub-arrayLess and sub-arrayGreater.

6)find the K-th smallest element recursively from the suitable sub-array.

Sorted Array

iii.use median as pivot

General Quick Sort Algorithm

p

Input : unsorted array.

Output: the ith order statistics element array[i]

Two linear algorithms proposed: Randomized and Deterministic

Quickselect algorithms:

Running Time Comparison Analysis

Optimal Solution

First step Choosing the pivot

Randomized Algorithm (QuickSelect)

Depending on the pivot the algorithm may

run very fast, or in quadric time

The median-of-three choice:

Take the first, the last and the middle element.

Choose the median of these three elements.

Example:

8, 3, 25, 6, 10, 17, 1, 2, 18, 5

The first element is 8, the middle - 10, the last - 5.

The median of [8, 10, 5] is 8

(Randomized quicksort )

Each time select any random element

in the array as the pivot.

Worst-case is O(nlogn)

//Input array A with size n and k - n.

QuickSelect(A[0…n-1],K)

1)Select a random pivot piv from A.

2)Divide A into two sub-arrays, one that contains elements LESS than the piv (sub-arrayLess) and the other one contains elements GREATER than the piv (sub-arrayGreater)

3)Count number of elements less than the piv (nLess)

If nLess = k - 1, output piv.

else If nLess > k -1,

call QuickSelect(sub-arrayLess, k).

else If nLess < k -1,

call QuickSelect(sub-arrayGreater, k - L - 1)

Some fixed element:

the first, the last.

This is a bad choice - the pivot may turn to be the smallest or the largest element,

then one of the partitions will be empty.

P

Empty

The median of the array

Smaller than Pivot

P

Greater than Pivot

if the array has N numbers, the median is the [N/2] largest number.

This is difficult to compute - increases the complexity.

Comparison between Algorithms

number of comparisons in QuickSelect is O(n).

If we want to split array in more than 2 sub-array. what we can do ?

YES

O(N)

O(N)

n

n

n

n

key comparision

key comparision

key comparision

key comparision

O(NlogN)

Worst case O(N2)

NO

O(N)

Worst case o(n2)

YES

Median finding, Order Statistics and Quick Sort

By

Hend AlShaya, Ashwaq AlOtebi, Latifah AlHarthi, Abeer AlSuhaim, Sarah AlKabli

SUPERVISOR

Prof. Abdelfettah Belghith

Outline

• Order Statistics
• Problem: Finding the Median
• Randomized Algorithm (QuickSelect)
• Deterministic algorithm
• General Quick Sort Algorithm
• Running Time Comparison Analysis