Заблокирован
|
||||||
1 | ||||||
Тонкости быстрой сортировки16.11.2011, 05:50. Показов 2413. Ответов 18
Метки нет (Все метки)
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий.
Представляется, что в этой сортировке есть какая-то тонкость, но какая вот? Вот часть моего кода, осуществляющая патишинирование. Не могу понять правильно она рабботает или нет. По отдельности вроде правильно (ну в смысле, когда оформляется в виде отдельной функции: вот так:
Самое забавное, это то,что практически все алгоритмы, которые предлагаются в качестве алгорита быстрой сортировки, легко опровергаются (то есть простенькие тестовые массивы не сортируются) путем замены индекса элемента массива, служащего раздеелителем исходного массива на два подассива. Вообще складывается такое впечатление, что никто и никогда так и не написал этой быстрой сортировки, и существует она только в теории, а все остальное выдаетсяя за нее, но таковой на самом деле не является.
0
|
16.11.2011, 05:50 | |
Ответы с готовыми решениями:
18
Пример быстрой сортировки массива строк и сортировки методом выбора Алгорим быстрой сортировки Не алгоритм быстрой сортировки Метод быстрой сортировки |
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,021
|
|
16.11.2011, 06:26 | 2 |
Эта функция будет работать неправильно в случае если head или tail перескочат элемент с partition. В лучшем случае она выполнит лишнюю работу, в худшем не выполнит основную задачу.
0
|
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,021
|
|
16.11.2011, 07:15 | 4 |
thick_int, А ты умеешь только готовыми алгоритмами пользоваться? тебе нужно что бы и все проверки за тебя сделали. Эту функцию нужно доработать и она будет делать что надо.
Например не давай элементам перепрыгнуть partition, как дошел, так останавливай его.
0
|
Заблокирован
|
|
16.11.2011, 07:40 [ТС] | 5 |
Нет, я пытаюсь написать этот алгоритм сам, но встречая трудности, смотрю то, что сделали люди и предложили в качестве образца. Ну так вот первое с чем я столкнулся, это то что эти образцы, описываеммые даже в книжках, ломаются очень легко.
Ну и второе совершенно непонятны Ваши утверждения насчет перескока. Ведь перескок означает необходимость произзвести обмен. Главное чтобы они обе одновременно череез один и тот же элемент не скакнули. Ну а лишняя работа вообще непонятна, где она там может быть.
0
|
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,021
|
|
16.11.2011, 07:55 | 6 |
thick_int, Очень просто. Так как движения хвоста и головы идет не равномерно может получиться так что один из них подойдет к partition. Что произойдет дальше?
1. Если это хвост то partition поменяется местами с головой. И твои указатели сдвинутся, голова вперед, хвост назад. И тут как раз ты увидишь что и хвост и голова оказались с одной стороны partition. Они начнут сортировать то что между ними. Если там все элементы больше partition то это будет пустая работа, так как результат уже получен, однако вернется из функции не номер элемента с partition, а вообще непонятно какой номер. Если там есть элементы меньше partition, то они как были справа от partition так справа и останутся, следовательно функция свою задачу не выполнит. 2. Если голова, то ситуация похожая. Ты вручную попробуй нарисовать и сразу все понятно будет.
0
|
16.11.2011, 07:58 | 7 | |||||
Найдите изъяны данного алгоритма:
0
|
Заблокирован
|
||||||||||||||||||||||||||
16.11.2011, 08:56 [ТС] | 8 | |||||||||||||||||||||||||
Да с ходу. Я тоже пытался им воспользоваться, но в этом алгоритме сразу же легко усматривается выход за границы массива.
Кроме того, замените выражение в 7 строчке на a[0] и сразу же получите крэш. Логика рекурсивных вызовов не такая тут примитивная, она должна проверять, каковы яявляются массива после патишинации. И КСТАТИ, ЕСЛИ АЛГОРИТМ СОРТИРОВКИ НАПИСАН ПРАВИЛЬНО, ТО ВЫ ЛЕГКО МОЖЕТЕ В ЭТОМ УБЕДИТЬСЯ, ЗАМЕНЯЯ ВЫБРАННЫЙ ВАМИ PARTITION НА ЛЮБОЙ ДОПУСТИМЫЙ ЭЛЕММЕНТ МАССИВА. ТО ЕСТЬ, ЕСЛИ АЛГОРИТМ НАПИИСАН КОРРЕКТНО, ТО В ВАШЕМ СЛУЧАЕ ЗАМЕНА, КОТОРУЮ Я УКАЗАЛ, НИКАК НЕ ОТРАЖАЛАСЬ ЮЫ НА РАБОТОСПОСОБНОСТИ АЛГОРИТМА. ТАК ВОТ, ЧТОБЫ УБЕДИТЬСЯЯ В ЛАЖОВОСТИ ВАШЕГО АЛГОРИТМА ДОСТАТОЧНО СДЕЛАТЬ ЭТУ ЗЗАМЕНУ И ВЫЗВАТЬ ЕГО ВОТ С ТАКИМ НАБОРОМ ДАННЫХ int a[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; Попробуйте и посмотрите на run-time error. У мен лично сразу же выскочила эта ошибка от Вашего алгоритма. Добавлено через 24 минуты А наконец допетрил, как ммне кажется и у меня получилось вот что. Во всякомм случае не крешится как у Вас Комментарии все достаточно поясняют
Проверил работоспособность все отлично, во вском случае вот с такими даннымми креша нет и сортируется все отлично: double a[ARRSIE] = {1000.2, 100.4, 8.2, 9.4, 100.4, 8.2, 2.1, 1.4, 5.5, -5.9};
0
|
Заблокирован
|
|
16.11.2011, 10:01 [ТС] | 10 |
Нет, конечно некорректно. Это просто означает, что Вы его слабенькое тестировали.
Немного повозившись, Вы самми сможете найти контрприер (состоящий из массива из трех элементов), на котором Ваш алгоритм ломается и без вской модификации. Но, в целом, иногда алгоритм быстрой сортировки, вот в такой убогой форме, в которой Вы его представили, может давать правильные результаты, но это отнюдь не означает, что то, что предложено Вами, абсолютно правильно. Я уже сказал, что в Вашем алгоритме явно видно возможное нарушение, свзанное с выходомм за допустимые границы массива. (А в моей программе этого нет).
0
|
16.11.2011, 11:25 | 11 |
Пока не приведете контрпример, утверждение звучит голословно (даже чересчур). Это не моя сортировка, ее приводят во многих учебниках. Вроде я анализировал этот алгоритм и в любом случае он работает корректно.
0
|
Заблокирован
|
||||||
16.11.2011, 12:38 [ТС] | 12 | |||||
Да, Вы знаете, я его тоже проанализировал вот так:
0
|
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,021
|
|
16.11.2011, 12:56 | 14 |
Проверь на вот этом тесте при partition равном 5
int a[10] = {10, 9, 8, 2, 5, 4, 3, 2, 1, 1};
0
|
Заблокирован
|
|
16.11.2011, 13:21 [ТС] | 15 |
А это разве хорошо, что реализаци такая хрупенькая?
Вообще этот алгоритм лучше всего прописывать в термиинах указателей, а не индексов. Тогда, по крайней мере, становтся очевидными вопросы, такие как, а двигался ли хвост, где находится голова. Ну и к тому же мо реализаци позволяет дальнейшее улучшение за счет оптимального выбора партиции. Ваша наверно тоже, но в Вашем случае нужно быть, крайне осторожным. Добавлено через 22 минуты Да, но у Вас тоже не все так плохо. Кстати, проверка показывает, что Ваша программа может работать с массивом, по крайней мере в 100000 элементов, а моя крешится уже при 3200. Есть куда копать.
0
|
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,021
|
|
16.11.2011, 13:29 | 16 |
thick_int, Вы спорите о размерности, когда обе программы на небольших тестах лажают. У обоих прог принцип одинаков, отличаются только детали, которые доводятся до ума чисто при отладке...
0
|
Заблокирован
|
|
16.11.2011, 13:42 [ТС] | 17 |
Добавлено через 3 минуты Мне, например, пока в голову лезут только такие способы улучшения: 1) Использовать быструю сортировку только для массивов, размеры которых не менее заданного (также подумать о верхней границе) 2) Если первый элемент массива меньше последнего, то обменть их мместами, и только затем приступать к сортировке, в противном случае, подумать, куда их поставить. Кстати тест, который Вы предложили, спокойно проходится и моей программой и программмой от Thinker
0
|
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,021
|
|
16.11.2011, 13:55 | 18 |
thick_int, Ты проверил на тесте, который я написал? Честно говоря ради интереса проверил на одной из ваших прог, думал вдруг ошибаюсь, оказалось действительно сортирует некорректно, почему я писал выше.
Раньше писал, сейчас нет особо времени писать прогу, так как мне пока без надобности. Добавлено через 3 минуты thick_int, Проходит то он проходит, но программа неверно сортирует! Добавлено через 3 минуты Сейчас еще раз проверю, может неправильно написал тебе тест
0
|
Заблокирован
|
|
16.11.2011, 14:00 [ТС] | 19 |
Нет я еще раз проверил и свою программу и программу от Thinker.
Все работает корректно и сортирует корректно.
0
|
16.11.2011, 14:00 | |
16.11.2011, 14:00 | |
Помогаю со студенческими работами здесь
19
Алгоритм Быстрой Сортировки на C++ Алгоритм быстрой сортировки Иллюстрация быстрой сортировки Реализация быстрой сортировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |