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

Тонкости быстрой сортировки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
thick_int
Заблокирован
16.11.2011, 05:50     Тонкости быстрой сортировки #1
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий.
Представляется, что в этой сортировке есть какая-то тонкость, но какая вот?

Вот часть моего кода, осуществляющая патишинирование. Не могу понять правильно она рабботает или нет. По отдельности вроде правильно (ну в смысле, когда оформляется в виде отдельной функции: вот так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//Функция должна разделять массив на два подмассива - левый и правый.
//В левом подмассиве должны содержаться все элементы массива, меньшие или равные partition.
//В правом подмассиве должны содержаться все элементы массива, большие partition.
// Функция возвращает индекс массива, который служит начальным элементом правого подмассива.
int section(double* array, int size, double partition)
{
    double* head = array;
    double* tail = array + size - 1;
    do 
    {
        while (head < tail && *head <= partition)
            ++head;
        while (tail > head && *tail > partition)
            --tail;
        if (head < tail)
        {
            double temp = *head;
            *head= *tail;
            *tail = temp;
        }
    } while (head < tail);
    return head - array;
}
Добавлено через 13 часов 5 минут
Самое забавное, это то,что практически все алгоритмы, которые предлагаются в качестве алгорита быстрой сортировки, легко опровергаются (то есть простенькие тестовые массивы не сортируются) путем замены индекса элемента массива, служащего раздеелителем исходного массива на два подассива.

Вообще складывается такое впечатление, что никто и никогда так и не написал этой быстрой сортировки, и существует она только в теории, а все остальное выдаетсяя за нее, но таковой на самом деле не является.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
16.11.2011, 06:26     Тонкости быстрой сортировки #2
Эта функция будет работать неправильно в случае если head или tail перескочат элемент с partition. В лучшем случае она выполнит лишнюю работу, в худшем не выполнит основную задачу.
thick_int
Заблокирован
16.11.2011, 07:00  [ТС]     Тонкости быстрой сортировки #3
Дело в том, что в сети предлагются только такие алгоритмы патишенизации массива.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
16.11.2011, 07:15     Тонкости быстрой сортировки #4
thick_int, А ты умеешь только готовыми алгоритмами пользоваться? тебе нужно что бы и все проверки за тебя сделали. Эту функцию нужно доработать и она будет делать что надо.
Например не давай элементам перепрыгнуть partition, как дошел, так останавливай его.
thick_int
Заблокирован
16.11.2011, 07:40  [ТС]     Тонкости быстрой сортировки #5
Нет, я пытаюсь написать этот алгоритм сам, но встречая трудности, смотрю то, что сделали люди и предложили в качестве образца. Ну так вот первое с чем я столкнулся, это то что эти образцы, описываеммые даже в книжках, ломаются очень легко.

Ну и второе совершенно непонятны Ваши утверждения насчет перескока. Ведь перескок означает необходимость произзвести обмен. Главное чтобы они обе одновременно череез один и тот же элемент не скакнули.
Ну а лишняя работа вообще непонятна, где она там может быть.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
16.11.2011, 07:55     Тонкости быстрой сортировки #6
thick_int, Очень просто. Так как движения хвоста и головы идет не равномерно может получиться так что один из них подойдет к partition. Что произойдет дальше?
1. Если это хвост то partition поменяется местами с головой. И твои указатели сдвинутся, голова вперед, хвост назад. И тут как раз ты увидишь что и хвост и голова оказались с одной стороны partition. Они начнут сортировать то что между ними. Если там все элементы больше partition то это будет пустая работа, так как результат уже получен, однако вернется из функции не номер элемента с partition, а вообще непонятно какой номер. Если там есть элементы меньше partition, то они как были справа от partition так справа и останутся, следовательно функция свою задачу не выполнит.
2. Если голова, то ситуация похожая.
Ты вручную попробуй нарисовать и сразу все понятно будет.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
16.11.2011, 07:58     Тонкости быстрой сортировки #7
Цитата Сообщение от thick_int Посмотреть сообщение
Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий.
Найдите изъяны данного алгоритма:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void QuickSort (int *a, int l, int r)
{
            int i, j;
            int x, buf;
            i = l;
            j = r;
            x = a[(l+r)/2];
            do
            {
                while (a[i] < x)
                   i++;
                while (x < a[j])
                   j--;
                if (i <= j)
                {
                    buf = a[i];
                    a[i] = a[j];
                    a[j] = buf;
                    i++;
                    j--;
                }
            } while( i <= j);
            if (l < j) QuickSort (a, l, j);
            if (r > i) QuickSort (a, i, r);
}
для массива int a[N] вызов QuickSort(a, 0, N-1)
thick_int
Заблокирован
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 минуты
А наконец допетрил, как ммне кажется и у меня получилось вот что.
Во всякомм случае не крешится как у Вас
Комментарии все достаточно поясняют

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void quick_sort_asc(double* array, int size) //Быстрая сортиировка массива в возрастающе порядке
{
    switch (size)
    {
        case 1: //Приммитивный случай
            return;
        case 2: //Приммитивный случай
            if (array[0] > array[1])
            {
                double temp = array[0];
                array[0] = array[1];
                array[1] = temp;
                return;
            }
        default: //Основная работа
            double* head = array;
            double* tail = array + size - 1;
            double partition = array[0];
            
            do 
            {
                while (head < tail && *head <= partition)
                    ++head;
                while (tail > head && *tail > partition)
                    --tail;
                if (head < tail)
                {
                    double temp = *head;
                    *head= *tail;
                    *tail = temp;
                }
            } while (head < tail);
 
            //Левый подмассив состоит из одного элемента, стоящего на своем  месте (Если)
            if (head == array + 1) 
            {
                quick_sort_asc(array + 1, size - 1);
                break;
            }
            //Левый подмассив включает все элементы массива, кроме может быть последнего (Если)
            //Ведь указатель tail не двигался
            if  (head == array + size - 1)
            {
                if (*head <= array[0]) //Левый подмассив включает все элементы массива, а его первый элемент максиальный (Если)
                                              //Значит надо поставить его на последнее место
                {   
                    double temp = array[0];
                    array[0] = *head;
                    *head = temp;
                }
                quick_sort_asc(array, size - 1);
                break; //Хорошо, что мы находимся внутри switch
            }
            //Если пришли сюда значит оба указателя head и tail находятся внутри массива
            quick_sort_asc(array, head - array);
            quick_sort_asc(tail, size - (head - array));
    }
}
Добавлено через 16 минут
Проверил работоспособность все отлично, во вском случае вот с такими даннымми креша нет и сортируется все отлично:

double a[ARRSIE] = {1000.2, 100.4, 8.2, 9.4, 100.4, 8.2, 2.1, 1.4, 5.5, -5.9};

C++
1
2
3
4
5
6
7
double a[ARRSIE] = {6.2, 5.4, 1.2, 9.4, 100.4, 9.5, 2.1, 1.4, 5.5, 5.9};
 
double a[ARRSIE] = {100, 99, 34, 9, 5.4, 4.2, 4.1, 3.4, 2.5, 2.5};
 
double a[ARRSIE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
double a[ARRSIE] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
Еще кстати выражение
C++
1
array[0]
в операторе
C++
1
double partition = array[0];
легко без каких-либо последствий может быть заменено на
C++
1
array[size - 1], array[size / 2]
и так далее, все равно креша нет и сортировка осуществляется.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
16.11.2011, 09:33     Тонкости быстрой сортировки #9
Цитата Сообщение от thick_int Посмотреть сообщение
Да с ходу. Я тоже пытался им воспользоваться, но в этом алгоритме сразу же легко усматривается выход за границы массива.

Кроме того, замените выражение в 7 строчке на a[0] и сразу же получите крэш.
Логика рекурсивных вызовов не такая тут примитивная, она должна проверять, каковы яявляются массива после патишинации.
Подождите, вы говорите если что-то заменить, а если ничего не менять, то корректно все работает?
thick_int
Заблокирован
16.11.2011, 10:01  [ТС]     Тонкости быстрой сортировки #10
Нет, конечно некорректно. Это просто означает, что Вы его слабенькое тестировали.
Немного повозившись, Вы самми сможете найти контрприер (состоящий из массива из трех элементов), на котором Ваш алгоритм ломается и без вской модификации.

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

Я уже сказал, что в Вашем алгоритме явно видно возможное нарушение, свзанное с выходомм за допустимые границы массива. (А в моей программе этого нет).
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
16.11.2011, 11:25     Тонкости быстрой сортировки #11
Цитата Сообщение от thick_int Посмотреть сообщение
Нет, конечно некорректно. Это просто означает, что Вы его слабенькое тестировали.
Немного повозившись, Вы самми сможете найти контрприер (состоящий из массива из трех элементов), на котором Ваш алгоритм ломается и без вской модификации.

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

Я уже сказал, что в Вашем алгоритме явно видно возможное нарушение, свзанное с выходомм за допустимые границы массива. (А в моей программе этого нет).
Пока не приведете контрпример, утверждение звучит голословно (даже чересчур). Это не моя сортировка, ее приводят во многих учебниках. Вроде я анализировал этот алгоритм и в любом случае он работает корректно.
thick_int
Заблокирован
16.11.2011, 12:38  [ТС]     Тонкости быстрой сортировки #12
Да, Вы знаете, я его тоже проанализировал вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
for (int count = 0; count < 32000; ++count)
    {
        int lo = count;
        for(int i = 0; i < ARRSIE; ++i)
            a[i] = arr[lo++];
        QuickSort (a, 0, ARRSIE - 1);
        for (int i = 0; i < ARRSIE; ++i)
        {
            cout << a[i] << '\t';
        }
    }
и оказалось, что он действительно работает корректно, но все же возражения, свзанные с хрупкостью и сильной зависимостью от правильного выбора partition, все равно остаются.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
16.11.2011, 12:42     Тонкости быстрой сортировки #13
Цитата Сообщение от thick_int Посмотреть сообщение
Да, Вы знаете, я его тоже проанализировал вот так:
я этот алгоритм аналитически проанализировал, алгоритм полностью корректный. Другое дело, что чуть что изменить в алгоритме и все полетит, но это уже другой вопрос
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
16.11.2011, 12:56     Тонкости быстрой сортировки #14
Проверь на вот этом тесте при partition равном 5
int a[10] = {10, 9, 8, 2, 5, 4, 3, 2, 1, 1};
thick_int
Заблокирован
16.11.2011, 13:21  [ТС]     Тонкости быстрой сортировки #15
А это разве хорошо, что реализаци такая хрупенькая?

Вообще этот алгоритм лучше всего прописывать в термиинах указателей, а не индексов.
Тогда, по крайней мере, становтся очевидными вопросы, такие как, а двигался ли хвост, где находится голова.
Ну и к тому же мо реализаци позволяет дальнейшее улучшение за счет оптимального выбора партиции. Ваша наверно тоже, но в Вашем случае нужно быть, крайне осторожным.

Добавлено через 22 минуты
Да, но у Вас тоже не все так плохо.
Кстати, проверка показывает, что Ваша программа может работать с массивом, по крайней мере в 100000 элементов, а моя крешится уже при 3200.
Есть куда копать.
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
16.11.2011, 13:29     Тонкости быстрой сортировки #16
thick_int, Вы спорите о размерности, когда обе программы на небольших тестах лажают. У обоих прог принцип одинаков, отличаются только детали, которые доводятся до ума чисто при отладке...
thick_int
Заблокирован
16.11.2011, 13:42  [ТС]     Тонкости быстрой сортировки #17
У обоих прог принцип одинаков, отличаются только детали
А у Вас есть какой-то особый принцип реализации быстрой сортиировки. Тогда может быть поделитесь великодушно.

Добавлено через 3 минуты
Мне, например, пока в голову лезут только такие способы улучшения:
1) Использовать быструю сортировку только для массивов, размеры которых не менее заданного (также подумать о верхней границе)
2) Если первый элемент массива меньше последнего, то обменть их мместами, и только затем приступать к сортировке, в противном случае, подумать, куда их поставить.

Кстати тест, который Вы предложили, спокойно проходится и моей программой и программмой от Thinker
solar_wind
 Аватар для solar_wind
740 / 731 / 39
Регистрация: 06.07.2009
Сообщений: 2,937
Завершенные тесты: 1
16.11.2011, 13:55     Тонкости быстрой сортировки #18
thick_int, Ты проверил на тесте, который я написал? Честно говоря ради интереса проверил на одной из ваших прог, думал вдруг ошибаюсь, оказалось действительно сортирует некорректно, почему я писал выше.
Раньше писал, сейчас нет особо времени писать прогу, так как мне пока без надобности.

Добавлено через 3 минуты
thick_int, Проходит то он проходит, но программа неверно сортирует!

Добавлено через 3 минуты
Сейчас еще раз проверю, может неправильно написал тебе тест
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.11.2011, 14:00     Тонкости быстрой сортировки
Еще ссылки по теме:

прогресс выполнения быстрой сортировки C++
C++ Алгоритмом быстрой сортировки строк
Алгоритм быстрой сортировки C++

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

Или воспользуйтесь поиском по форуму:
thick_int
Заблокирован
16.11.2011, 14:00  [ТС]     Тонкости быстрой сортировки #19
Нет я еще раз проверил и свою программу и программу от Thinker.
Все работает корректно и сортирует корректно.
Yandex
Объявления
16.11.2011, 14:00     Тонкости быстрой сортировки
Ответ Создать тему
Опции темы

Текущее время: 21:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru