Сортировка массива с использованием медианов

Question

Итак, давайте предположим, что у вас есть алгоритм для метода, который находит медиану массива и позволяет вызвать этот метод X. X будет в основном найти медиану массива a (a isortort) в O (n) время. Как я смогу разработать алгоритм O (n log n) -time для сортировки массива a, используя X в качестве вспомогательного метода. Cant действительно понимает тот факт, что медиана поможет мне отсортировать массив ... ??

Благодаря

Answer 1

Вы можете решить эту проблему, применяя X рекурсивно. Рассмотрим следующую подпрограмму Y:

1. Учитывая массив длины n в качестве входных данных, мы сначала применяем метод X, чтобы найти средний m входных чисел, это занимает много времени O(n).
2. Затем мы сканируем входной массив, чтобы переупорядочить числа в массиве так, чтобы все числа, меньшие, чем m, находились в левой части массива, тогда как все числа, большие, чем m, находятся в правой части массива (и m находится в середине массива), обратите внимание, что этот шаг также занимает время O(n).

Следовательно, на входном массиве длины n подпрограмма Y принимает O(n) всего времени.

Так что, если вы рекурсивно применить подпрограмму Y к подмассивам слева и справа от срединной m и продолжить процесс, выход будет отсортированный массивом и общее время определяется по формуле:

T(n) = O(n) + 2 * O(n/2) + 4 * O(n/4) + ... + 2^log(n) * O(n/2^log(n)) 
    = O(n) + O(n) + O(n) + ... + O(n)  // log(n) terms in total 
    = O(n log(n)) 

Answer 2

В быстрой сортировке, в худшем случае сложность для сортировки массива является O (N^2), если ось выбираются случайным образом.

Но есть варианты быстрого сортировки, чья наихудшая временная сложность - O (nlgn). В этих вариантах элемент pivot - это медианный (n/2-й элемент) массива или позиция поворота - это функция размера массива, так что он может разделить массив на две части, которые являются функциями размера массива (не константы).