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

Quiсk sort - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Даны два двухмерных массива одинаковых размеров. Создать третий массив такого же размера, каждый элемент которого равен 100 http://www.cyberforum.ru/cpp-beginners/thread43617.html
Даны два двухмерных массива одинаковых размеров. Создать третий массив такого же размера, каждый элемент которого равен 100, если соответствующие элементы двух первых массивов имеют одинаковый знак,...
C++ Дан двухмерный массив.Найти сумму элементов побочной диагонали и сумму элементов главной диагонали Дан двухмерный массив.Найти сумму элементов побочной диагонали и сумму элементов главной диагонали... Программу надо в С. http://www.cyberforum.ru/cpp-beginners/thread43613.html
C++ НОД для трех чисел.
Здорова народ! Как найти найболшый общий делитель для трьох чисел?
C++ Дан двухмерный массив.Выямнить является ли произведение элементов заданного столбца массива трехзначным числом
Дан двухмерный массив.Выямнить является ли произведение элементов заданного столбца массива трехзначным числом
C++ Сформировать два массива.... http://www.cyberforum.ru/cpp-beginners/thread43599.html
Дан массив из 20 элементов. Сформировать два массива размером 10, включив в первый из них элементы с четными номерами, во второй с нечетными. Не могу сформировать массив, Если не сложно напишите всю...
C++ Не работает MessageBox Не работает след строчка MessageBox("Test"); Выдает ошибку error C2664: 'MessageBoxW' : cannot convert parameter 1 from 'char ' to 'const unsigned short * Среда разработки Microsoft Embedded... подробнее

Показать сообщение отдельно
Otaka
1824 / 680 / 18
Регистрация: 11.12.2008
Сообщений: 1,019
11.07.2009, 20:41
Ну не знаю. Я просто сказал, то что написано в книге "Алгоритмы. Построение и анализ". В этой книге куча алгоритмов на разные темы и быстрая сортировка разобрана очень подробно, приведлен её математический анализ.
(страница 161)
Идея состоит в привнесении случайности, обеспечивающее нужное распределение. Например, перед началом сортировки можно случайным образом переставить элементы, после чего уже все перестановки станут равновероятными(это можно сделать за О(n)). Такая модификация не увеличит серьезно время работы, но теперь мат ожидание времени работы не зависит от порядка входных элементов.
...
Для такого вероятностного алгоритма быстрой сортировки нет неудобных входов.
...
Там же даны и другие улучшения: процедура разбиения Ламуто, разбиение с помощью медианы трех элементов.
Есть еще куча улучшений данной сортировки, и они справляются со всеми этими неудобными входами(например реализация в том же линуксе).
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru