Быстрый выбор медианы

Question

Как мы можем выбрать медиану 3-элементного разбиения для реализации быстрой сортировки.Точно так же мы можем выбрать медиану из 5, 7 или 11 элементов для быстрой сортировки?Если так, то как ??

Answer 1

Вам следует заглянуть в алгоритм Медиана медиан . Это линейный алгоритм времени со следующим повторением ...

T(n) ≤ T(n/5) + T(7n/10) + O(n)

... что O (n). Алгоритм подробнее ...

1. разделить список на n / 5 подпоследовательностей по 5 элементов в каждой
2. найти медиану каждого списка по грубой силе. их будет n / 5
3. Пусть m_1, ..., m_n / 5 - эти медианы.
4. рекурсивно найти медиану этих медиан. это будет 1 элемент, стержень!

... и некоторый псевдокод ...

MedianOfMedians (A[1],...,A[n]) 
begin
    for i=1 to n/5 do {
        let m_i be the median of A[5i − 4], A[5i − 3],..., A[5i];
    }
    pivot = Select(m1,...,m_n/5, n/10); // the pivot
    return pivot
end

Ссылки

• http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm
• Медиана медиан на Яве
• http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf
• http://www.soe.ucsc.edu/classes/cmps102/Spring05/selectAnalysis.pdf
• http://webee.technion.ac.il/courses/044268/w0809_website/recitations/Median.pdf

Надеюсь, это поможет.
Христо