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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
thick_int
Заблокирован
#1

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

16.11.2011, 05:50. Просмотров 1306. Ответов 18
Метки нет (Все метки)

Излазил кучу мест в сети. Нашел массу этих алгоритмов, но на поверку практически каждый не совсем работающий.
Представляется, что в этой сортировке есть какая-то тонкость, но какая вот?

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

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 минут
Самое забавное, это то,что практически все алгоритмы, которые предлагаются в качестве алгорита быстрой сортировки, легко опровергаются (то есть простенькие тестовые массивы не сортируются) путем замены индекса элемента массива, служащего раздеелителем исходного массива на два подассива.

Вообще складывается такое впечатление, что никто и никогда так и не написал этой быстрой сортировки, и существует она только в теории, а все остальное выдаетсяя за нее, но таковой на самом деле не является.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2011, 05:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Тонкости быстрой сортировки (C++):

Пример быстрой сортировки массива строк и сортировки методом выбора - C++
Добрый вечер. Скиньте пожалуйста пример быстрой сортировки массива строк и сортировки массива строк методом выбора. Очень срочно надо,...

Метод быстрой сортировки - C++
Доброго времени суток, форумчане. Вчера проходили метод быстрой сортировки. Во входном файле в первой строчке указывается кол-во...

Визуализатор быстрой сортировки - C++
Добрый день! Нужно написать программу, которая иллюстрирует работу быстрой сортировки. В частности должно присутствовать: *вывод...

Иллюстрация быстрой сортировки - C++
Ребят,необходимо написать программу похожую на ту,которая тут http://www.cyberforum.ru/csharp-beginners/thread874724.html Помогите...

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

Алгорим быстрой сортировки - C++
В одной из тем выложен алгоритм быстрой сортировки. Возник вопрос: если индексы i и j указывают на один элемент зачем нужен обмен? ...

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

Ну и второе совершенно непонятны Ваши утверждения насчет перескока. Ведь перескок означает необходимость произзвести обмен. Главное чтобы они обе одновременно череез один и тот же элемент не скакнули.
Ну а лишняя работа вообще непонятна, где она там может быть.
0
solar_wind
756 / 747 / 42
Регистрация: 06.07.2009
Сообщений: 2,969
Завершенные тесты: 1
16.11.2011, 07:55 #6
thick_int, Очень просто. Так как движения хвоста и головы идет не равномерно может получиться так что один из них подойдет к partition. Что произойдет дальше?
1. Если это хвост то partition поменяется местами с головой. И твои указатели сдвинутся, голова вперед, хвост назад. И тут как раз ты увидишь что и хвост и голова оказались с одной стороны partition. Они начнут сортировать то что между ними. Если там все элементы больше partition то это будет пустая работа, так как результат уже получен, однако вернется из функции не номер элемента с partition, а вообще непонятно какой номер. Если там есть элементы меньше partition, то они как были справа от partition так справа и останутся, следовательно функция свою задачу не выполнит.
2. Если голова, то ситуация похожая.
Ты вручную попробуй нарисовать и сразу все понятно будет.
0
Thinker
Эксперт С++
4226 / 2200 / 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)
0
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]
и так далее, все равно креша нет и сортировка осуществляется.
0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
16.11.2011, 09:33 #9
Цитата Сообщение от thick_int Посмотреть сообщение
Да с ходу. Я тоже пытался им воспользоваться, но в этом алгоритме сразу же легко усматривается выход за границы массива.

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

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

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

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

Я уже сказал, что в Вашем алгоритме явно видно возможное нарушение, свзанное с выходомм за допустимые границы массива. (А в моей программе этого нет).
Пока не приведете контрпример, утверждение звучит голословно (даже чересчур). Это не моя сортировка, ее приводят во многих учебниках. Вроде я анализировал этот алгоритм и в любом случае он работает корректно.
0
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, все равно остаются.
0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
16.11.2011, 12:42 #13
Цитата Сообщение от thick_int Посмотреть сообщение
Да, Вы знаете, я его тоже проанализировал вот так:
я этот алгоритм аналитически проанализировал, алгоритм полностью корректный. Другое дело, что чуть что изменить в алгоритме и все полетит, но это уже другой вопрос
0
solar_wind
756 / 747 / 42
Регистрация: 06.07.2009
Сообщений: 2,969
Завершенные тесты: 1
16.11.2011, 12:56 #14
Проверь на вот этом тесте при partition равном 5
int a[10] = {10, 9, 8, 2, 5, 4, 3, 2, 1, 1};
0
thick_int
Заблокирован
16.11.2011, 13:21  [ТС] #15
А это разве хорошо, что реализаци такая хрупенькая?

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

Добавлено через 22 минуты
Да, но у Вас тоже не все так плохо.
Кстати, проверка показывает, что Ваша программа может работать с массивом, по крайней мере в 100000 элементов, а моя крешится уже при 3200.
Есть куда копать.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.11.2011, 13:21
Привет! Вот еще темы с ответами:

Алгоритм быстрой сортировки - C++
Написать программу, реализующую алгоритм быстрой сортировки(рекурсивный) для массива целых чисел.

Не алгоритм быстрой сортировки - C++
Просто как подключить эту функцию Не работаеееет #include&lt;iostream&gt; #include&lt;iomanip&gt; #include &lt;algorithm&gt; using namespace std; ...

Алгоритмом быстрой сортировки строк - C++
Необходимо отсортировать дату,она же char, по возрастанию. void q_sort(Medicament m, int f, int l){ int i = f, j = l; char...

Алгоритм быстрой сортировки по убыванию - C++
Я нашёл алгоритм быстрой сортировки по возрастанию: int n, a; //n - количество элементов void qs(int* s_arr, int first, int last) ...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
16.11.2011, 13:21
Ответ Создать тему
Опции темы

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