Подскажите пожалуйста каким образом лучше всего выбирать опорный элемент в быстрой сортировке. То есть так, чтобы это был примерно средний по значению в массиве. Для того, чтобы массив делился на примерно две равные половины. Спасибо.

Выбирите случайно 20 элементов и из них возьмите средний.

Не совсем понял вас. Но ведь я таким образом тоже могу случайно выбрать самый маленький или самый большой, что приведёт к вырожденному массиву и повысит сложность сортировки до O(n^2). 

Спасибо.

Это сообщение отредактировал(а) xreal - 12.6.2010, 04:05

припоминаю, что когда-то кто-то упоминал про алгоритм "медиана медиан"

там массив делился на части, у каждой части выбиралась медиана, потом уже из них выбиралась медиана тем же алгоритмом, получалось O(n)

подробностей алгоритма не помню, но можно попробовать поискать

Самый маленький вы никогда не выберите вообще.

2maxim1000, спасибо, интересный вариант, скорее всего реализую именно его.

2esperanto, почему вы решили, что невозможно выбрать самый маленький?

Если тебе именно QuickSort нужен то сложность O(n log n) 
Вот код. 

2 v1m, на сколько я помню паскаль, у вас опорный элемент x выбирается просто как средний элемент массива. Это не лучший вариант. Потому что элемент всегда выбирается детерминированно. В книге кормена предлагается выбирать каждый раз случайный элемент из сортируемого подмассива. Тогда вероятность попадания на наибольший или наименьший элементы самая маленькая. Спасибо вам за код, но не подходит)

А если вы подумали, что мне просто нужен алгоритм, код быстрой сортировки, то это не нужно) я его прекрасно знаю) Дело в том, что в некоторых случаях сложность быстрой сортировки не O(n log n), а может быть O(n^2). Вот таких случаев надо постараться избежать, не смотря на то, что они могут быть и очень редкими. 

Поэтому остановлюсь на одном из вариантов:

1. Выбор каждый раз случайного элемента.

2. Или предложенный выше алгоритм медианы медиан.

Это сообщение отредактировал(а) xreal - 12.6.2010, 17:51

Вам (1) вариант один не подходит, вы же сами про это сказали.


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



Мой вариант намного лучше вашего варианта (1).


Вариант 2 гарантирует с вероятностью 1 О(п лог п)  но  там большая константа получается. Так как на каждом шаге за линейное время ищут медиану.

Быстрая случайная сортировка выдаст квадратичную сложность с вероятностью 
 2 встепени (-п)   
с точностью до константы.

Для данных длиной больше 30 это очень маленькое число.


Это сообщение отредактировал(а) esperanto - 12.6.2010, 19:39

Возможно я чего-то не понимаю. Вы предлагаете выбрать 20 случайных элементов, а потом непонятно чем отсортировать их и взять среднее по значению. Или из этих 20 элементов взять средний по индексу?


Вообще не понял, что вы имеете ввиду в этой записи.

1) отсортировать 20 элементов стоит О(1) времени.


2) там написано два в степени минус эн.

Всем спасибо за советы)

только перед этим лучше бы поискать его полное описание
а то я сильно сомневаюсь, что у меня - полное