Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
erslgoeirjh
0 / 0 / 1
Регистрация: 12.07.2013
Сообщений: 44
1

Правильный алгоритм быстрой сортировки

13.11.2018, 11:30. Просмотров 101. Ответов 7
Метки нет (Все метки)

Уважаемые участники форума, подскажите, пожалуйста, правильный алгоритм быстрой сортировки. Который бы работал во всех случаях, чтобы не было выходов за пределы массива.

Ответ можете написать на любом языке, но желательно--на C++ .
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2018, 11:30
Ответы с готовыми решениями:

Алгоритм быстрой сортировки в детерминированном и стохастическом вариантах
Объясните разницу между ними.

Объясните алгоритм "быстрой сортировки"
Вот мои рассуждения:У нас в начале есть массив, состоящий из N элементов. Определим функцию,которая...

Распараллелить алгоритм быстрой корреляции
Доброго времени суток. Как Распараллелить алгоритм быстрой корреляции ? Алгоритм заключается в...

Разноцветный поезд. Правильный ли алгоритм?
Мой версия алгоритма ниже. (известно, что он не всегда работает) В городе готовится к открытию...

Алгоритм сортировки
Джек разрабатывает новый алгоритм сортировки и в свободное время экспериментирует на сотрудниках...

7
Puporev
Модератор
55479 / 42580 / 29429
Регистрация: 18.05.2008
Сообщений: 100,735
13.11.2018, 12:01 2
Вообще есть один правильный алгоритм быстрой сортировки-сортировка методом Хоара, который нетрудно найти как у нас на форуме так и вообще в интернете, неправильным его делают Ваши кривые руки.
1
Shamil1
Модератор
2165 / 1461 / 335
Регистрация: 26.03.2015
Сообщений: 5,294
13.11.2018, 13:39 3
erslgoeirjh,
Вероятно, Вы где-то написали меньше вместо меньше-равно.
0
renat_dmitriev
376 / 280 / 119
Регистрация: 26.08.2016
Сообщений: 883
15.11.2018, 00:00 4
Puporev, Написал на javascript этот алгоритм, сравнил со встроенным в хроме на массиве в 100 тысяч случайных чисел, встроенный проигрывает по скорости почти в два раза. Я в шоке. Спасибо за указание.
0
Shamil1
Модератор
2165 / 1461 / 335
Регистрация: 26.03.2015
Сообщений: 5,294
16.11.2018, 10:43 5
Цитата Сообщение от renat_dmitriev Посмотреть сообщение
сравнил со встроенным в хроме на массиве в 100 тысяч случайных чисел, встроенный проигрывает по скорости почти в два раза. Я в шоке.
Сравните на неслучайных числах. Например, на почти отсортированном массиве.

Добавлено через 5 минут
Алгоритмов сортировки много. Под любую конкретную задачу можно найти алгоритм, работающий быстрее стандартного универсального алгоритма.

з.ы. Можете ещё для сравнения попробовать сортировку расчёской (простая модификация пузырьковой сортировки) или сортировку Шелла (аналогичная модификация сортировки вставками). Возможно, результат Вас тоже удивит.
0
renat_dmitriev
376 / 280 / 119
Регистрация: 26.08.2016
Сообщений: 883
16.11.2018, 10:59 6
Shamil1, В действительности такие данные показал только хром, на Опере и Мозилле дела намного лучше. Также делал тесты помимо сортировки массива из 100 000 элементов, сортировал 1000 массивов по 100 элементов, там видимо тоже разные браузеры используют разные алгоритмы и результаты отличаются в разы. Но судя по всему на нынешних мощностях разница даже на миллионе строк не превосходит секунды и реально на это никто внимания не обращает. Это я так, из любопытства проверял.
0
Shamil1
Модератор
2165 / 1461 / 335
Регистрация: 26.03.2015
Сообщений: 5,294
16.11.2018, 12:00 7
renat_dmitriev, Сортировка массива случайных чисел - чисто математическая задача. На практике обычно сортируется список объектов по какому-нибудь свойству. При этом, обычно, этот список уже отсортирован по другому свойству объекта, и между свойствами есть некая корреляция.
Например, какие-нибудь счета-фактуры отсортированы в бд по дате создания (просто потому, что в качестве первичного ключа используется счётчик), а нам нужно отсортировать их по дате отгрузки. Понятно, что массив будет уже приблизительно отсортирован в нужном порядке.
1
renat_dmitriev
376 / 280 / 119
Регистрация: 26.08.2016
Сообщений: 883
16.11.2018, 12:18 8
Shamil1, Да, на почти отсортированных хром показывает на порядок другие цифры, буду иметь ввиду. Благодарю.
0
16.11.2018, 12:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.11.2018, 12:18

алгоритм сортировки
каким алгоритмом можно провести сортировку 5 элементов за 7 и менее шагов?

Алгоритм сортировки
Джек разрабатывает новый алгоритм сортировки и в свободное время экспериментирует на сотрудниках...

Оптимальный алгоритм сортировки
Камрады! Есть функция/процедура f(m,n), которая получает 2 номера и возвращает n,m (n>m) т.е....


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

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

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