Форум программистов, компьютерный форум, киберфорум
Наши страницы
C++
Войти
Регистрация
Восстановить пароль
 
SharpersAreGoodGuys
0 / 0 / 0
Регистрация: 29.01.2017
Сообщений: 21
#1

Модификация quicksort: выбор разделяющего элемента медианой

29.11.2017, 18:10. Просмотров 159. Ответов 0
Метки нет (Все метки)

Требуется модифицировать стандартный quicksort добавив выбор разделяющего элемента с помощью медианы. Сам не понимаю как это работает, единственное что нашел это небольшое описание с примером кода:
Выбор медианы из первого, среднего и последнего элементов в качестве разделяющего элемента и отсечение рекурсии меньших подмассивов может привести к существенному повышению эффективности быстрой сортировки. Функция median возвращает индекс элемента, являющегося медианой трех элементов. После этого он и средний элемент массива меняются местами, при этом медиана становится разделяющим элементом. Массивы небольшого размера (длиной M = 11 и меньше) в процессе разделения игнорируются, затем для окончания сортировки используется сортировка вставками.
C++
1
2
3
4
5
6
7
8
9
10
 const int M = 10
  void quicksort(a: T[n], int l, int r)
     if (r - l \leqslant M)
        insertion(a, l, r)
        return
     int med = median(a[l], a[(l + r) / 2], a[r])
     swap(a[med], a[(l + r) / 2])
     int i = partition(a, l, r)
     quicksort(a, l, i)
     quicksort(a, i + 1, r)
Только здесь еще и сортировка вставками, и вообще не очень понятно написано. Кто-нибудь может привести код функции быстрой сортировки с выбором разделяющего элемента с помощью медианы?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2017, 18:10
Ответы с готовыми решениями:

ListView выбор элемента
Есть handle ListView'a чужой программа, вопрос в том, как выбрать определенный...

Вычислить разницу между средним арифметическим и медианой
Вычислить разницу между средним арифметическим и медианой для каждой строки...

Выбор элемента из сортировки
Не подскажите как можно сделать так, чтобы из отсортированных элементов (по...

Выбор случайного элемента массива
Понимаю что вопрос простой, но все же, подскажите, как выбрать случайную...

Создания события, разделяющего правый и левый клик мышью
при динамическом создании PictureBox я добавлял события ImageBox.Click +=...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.11.2017, 18:10

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

найти угол между медианой
найти угол между медианой и высотой треуг АВС, выходящими из вершины А(1,-5),...

Найдите угол между стороной и медианой
Даны два вектора AB={-4;8;-1}, BC={-2;16;1} совпадающие со сторонами...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru