Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
SharpersAreGoodGuys
0 / 0 / 1
Регистрация: 29.01.2017
Сообщений: 17
#1

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

29.11.2017, 18:10. Просмотров 148. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Модификация quicksort: выбор разделяющего элемента медианой (C++):

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

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

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

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

QuickSort - C++
Помогите с алгоритмом и кодом на C++ быстрой сортировки! Наработок вообще нет!

Quicksort - C++
Дан массив, необходимо отсортировать его в порядке возрастания. Использую квиксорт, но в одном из тестов не проходит по времени (2с). ...

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

QuickSort на C++11 - C++
Написал быструю сортировку, добился работоспособности и сразу захотелось улучшить сам код. #include <iostream> #include...

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

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

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


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

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

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