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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ разница между произведениями http://www.cyberforum.ru/cpp-beginners/thread384451.html
найти разницу между произведениями чисел натурального ряда от 1 до 10,что стоят на парных и непарных местах. -входные данные вводятся из клавиатуры -результат вывести на экран
C++ В квадратной матрице вычислить сумму элементов, расположенных на одной горизонтали Память под хранение матричных данных должна выделяться динамически в 2 этапа: выделение памяти для хранения указателей на строки, выделение памяти для хранения элементов каждой строки. Освобождение – аналогично, но в обратном порядке. Работа с динамической памятью – new, delete. _____________________________________________________________________________________________ В квадратной матрице... http://www.cyberforum.ru/cpp-beginners/thread384439.html
C++ Вывести папку другого уровня.
С помощью SetCurrentDirectory установлена текущая директория : Корень:\\Папка1\\Папка2 Нужно установить текущей Папку1. То есть, сначала текущая Папка2, затем надо сделать текущей Папку1.
C++ Функции
Помогите пожалуйста я очень прошу!!!?)))))))))))))))очень надо (((но обязательно комментариии!)))))) если можно(((и вопрос а в Visual Studio можно проверить как работает????вот само задание: а)создать программу построения графика y=sinx (с выводом на экран) б)Составить программу вычисления y=sinx в 10 любых точках
C++ Заменить все положительные1|отрицательные2 элементы целочисленного массива http://www.cyberforum.ru/cpp-beginners/thread384413.html
помогите пожалуйста решить задачу на Array: Заменить все положительные1|отрицательные2 элементы целочисленного массива размера 10 на значение минимального3|максимального4.
C++ Дана целочисленная матрица размера M x N. помогите решить задачу на матрицу... Дана целочисленная матрица размера M x N. Найти количество ее строк1|столбцов2, все элементы которых различны. подробнее

Показать сообщение отдельно
thick_int
Заблокирован
16.11.2011, 08:56  [ТС]     Тонкости быстрой сортировки
Да с ходу. Я тоже пытался им воспользоваться, но в этом алгоритме сразу же легко усматривается выход за границы массива.

Кроме того, замените выражение в 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]
и так далее, все равно креша нет и сортировка осуществляется.
 
Текущее время: 16:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru