Имя пользователя:

Пароль:



С С++ - Вопросы программирования

Подписчиков: Kordan

С С++ - Вопросы программирования

Номер сообщения:#41  Непрочитанное сообщение Kordan » 03 фев 2018, 10:48

Цитата:
Валера, сортировка методом пузырька убогая, применяй метод Хоара:....

Да, я в курсе. Как раз эту тему проштудировал. Пытался применить различные реализации метода Хоара в моей програмке, почему-то не работают, причем с одинаковым результатом - выдает первые два числа, а дальше мусор. Причем отдельно, с нуля реализации проверял - рабочие. Сейчас продолжу изыскания.
Аватар пользователя
Kordan
.
.
      Автор темы
Сообщений: 2447
Возраст: 50
Зарегистрирован: 74 месяцев и 2 дня
Откуда: Саратов
Национальный флаг:
Russia
Благодарил (а): 669 раз.
Поблагодарили: 1223 раз.
Имя: Валерий
Пункты репутации: 25
Молодой трейдерМолодой трейдерМолодой трейдер

С С++ - Вопросы программирования

Номер сообщения:#42  Непрочитанное сообщение Kordan » 03 фев 2018, 20:34

Нашел ошибку - передавал в функцию значения мин и макс элементов вместо размерности массива.
Программа заполнения массива случайными числами и его сортировка методом Хоара.
https://pastebin.com/EK39AyN7
Код: выделить все · Развернуть
/*
* Kordan C++ ************************************************************
* Программа заполнения массива определенного размера случайными числами *
*  и его сортировка по возрастанию методом Хоара                        *
* ***********************************************************************
*/
#include <iostream>
#include <cstdlib> // содержит srand() и rand()
#include <ctime>   // содержит time()
using namespace std;

int FillArray (int *arr, const int size, const int min_range, const int max_range);
void quickSort (int *arr, int begin, int end);
void print (int *arr, int size);

int main () {
    setlocale (LC_ALL, "RUS");
    // Количество чисел в массиве
    const int SIZE = 13;
    // Минимальное число в массиве
    const int MIN_RANGE = 13;
    // Максимальное число в массиве
    const int MAX_RANGE = 81;

    int list[SIZE];

    if (FillArray (list, SIZE, MIN_RANGE, MAX_RANGE) != 1) {
        // Выводим значения исходного массива
        print (list, SIZE);
        // Сортируем массив по возрастанию
        quickSort (list, 0, SIZE - 1);
        // Выводим значения отсортированного массива
        print (list, SIZE);
    }

    cout << endl << endl;
    //system ("pause");
    return 0;
}

// -- Kordan С++ -----------------------------------------
// Функция заполнения массива случайными целочисленными  -
// значениями в диапазоне чисел                          -
//                                                       -
// Необходимо подключить:                                -
// #include <cstdlib> (содержит srand() и rand())        -
// #include <ctime>   (содержит time())                  -
//                                                       -
// Аргументы функции:                                    -
// *arr      - Имя массива                               -
// size      - Размер массива                            -
// min_range - Минимальное значение диапазона            -
// max_range - Максимальное значение массива             -
// -- begin ----------------------------------------------
int FillArray (int *arr, const int size, const int min_range, const int max_range) {
    // Автоматическая рандомизация
    srand (time (0));
    for (int i = 0; i < size; i++) {
        if (min_range <= max_range) arr[i] = min_range + rand () % (max_range + 1 - min_range);
        else {
            cout << "Ошибка!nМаксимальное значение диапазона чисел должно быть больше минимального!n";
            return 1;
        }
    }
}
// -- end --

// -- Kordan C ++ ---------------------------------------
// Функция вывода на консоль значений элементов массива -
//                                                      -
// Аргументы функции:                                   -
// *arr - Имя массива                                   -
// size - Размер массива                                -
// -- begin ---------------------------------------------
void print (int *arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl << endl;
}
// -- end --

// -- Kordan C ++ -----------------------------------
// Функция сортировки массива определенного размера - 
// методом Хоара                                    -
//                                                  -
// Аргументы функции:                               -
// *arr  - Имя массива                              -
// begin - Начало массива                           -
// end   - Конец массива                            -
//                                                  -
// Пример использования:                            -
// quickSort (list, 0, SIZE - 1);                   -
// -- begin -----------------------------------------
void quickSort (int *arr, int begin, int end) {
    int first = begin, last = end;
    int piv = arr[(first + last) / 2];
    while (first <= last) {
        while (arr[first] < piv) first++;
        while (arr[last] > piv) last--;
        if (first <= last) swap (arr[first++], arr[last--]);
    }
    if (begin < last) quickSort (arr, begin, last);
    if (end > first) quickSort (arr, first, end);
}
// -- end --


Сообщение добавлено... спустя 2 минуты 1 секунду:
Пока до векторов не дошел и конструкция
Код: выделить все · Развернуть
template< class T >
не знакома.
Аватар пользователя
Kordan
.
.
      Автор темы
Сообщений: 2447
Возраст: 50
Зарегистрирован: 74 месяцев и 2 дня
Откуда: Саратов
Национальный флаг:
Russia
Благодарил (а): 669 раз.
Поблагодарили: 1223 раз.
Имя: Валерий
Пункты репутации: 25
Молодой трейдерМолодой трейдерМолодой трейдер

С С++ - Вопросы программирования

Номер сообщения:#43  Непрочитанное сообщение Kordan » 04 фев 2018, 01:13

Усовершенствовал функцию до двух аргументов вместо трех. Также применил автоматическое определение длины массива.
https://pastebin.com/yhNepuJY
Код: выделить все · Развернуть
/*
* Kordan C++ **************************************
* Программа заполнения массива случайными числами *
* и его сортировка по возрастанию методом Хоара c *
* автоматическим определением длины массива       *
* *************************************************
*/
#include <iostream>
#include <cstdlib> // содержит srand() и rand()
#include <ctime>   // содержит time()
#include <malloc.h>// содержит _msize()
using namespace std;

int FillArray (int *arr, const int size, const int min_range, const int max_range);
void sortHoare (int *arr, int end);
void print (int *arr, int size);


int main () {
    setlocale (LC_ALL, "RUS");
    // Количество чисел в массиве
    const int SIZE = 25;
    // Минимальное число в массиве
    const int MIN_RANGE = 1;
    // Максимальное число в массиве
    const int MAX_RANGE = 100;
    int *list = new int[SIZE];

    if (FillArray (list, SIZE, MIN_RANGE, MAX_RANGE) != 1) {
        // Выводим значения исходного массива
        print (list, SIZE);
        // Сортируем массив по возрастанию
        // С помощью выражения "_msize (list) / sizeof (list[0])" получаем размер массива
        sortHoare (list, _msize (list) / sizeof (list[0]) - 1);
        // Выводим значения отсортированного массива
        print (list, SIZE);
    }
    delete[] list;
    cout << endl << endl;
    //system ("pause");
    return 0;
}

// -- Kordan C ++ -----------------------------------
// Функция сортировки массива методом Хоара         -
//                                                  -
// Аргументы функции:                               -
// *arr  - Имя массива                              -
// size  - Конец массива                            -
//                                                  -
// Пример использования:                            -
// quickSort (list, SIZE - 1);                      -
// -- begin -----------------------------------------
void sortHoare (int *arr, int size) {
    int first = 0, last = size;
    int pivot = arr[size >> 1];
    do {
        while (arr[first] < pivot) first++;
        while (arr[last] > pivot) last--;
        if (first <= last) swap (arr[first++], arr[last--]);
    } while (first <= last);
    if (last > 0) sortHoare (arr, last);
    if (size > first) sortHoare (arr + first, size - first);
}
// -- end --

// -- Kordan С++ -----------------------------------------
// Функция заполнения массива случайными целочисленными  -
// значениями в диапазоне чисел                          -
//                                                       -
// Необходимо подключить:                                -
// #include <cstdlib> (содержит srand() и rand())        -
// #include <ctime>   (содержит time())                  -
//                                                       -
// Аргументы функции:                                    -
// *arr      - Имя массива                               -
// size      - Размер массива                            -
// min_range - Минимальное значение диапазона            -
// max_range - Максимальное значение массива             -
// -- begin ----------------------------------------------
int FillArray (int *arr, const int size, const int min_range, const int max_range) {
    // Автоматическая рандомизация
    srand (time (0));
    for (int i = 0; i < size; i++) {
        if (min_range <= max_range) arr[i] = min_range + rand () % (max_range + 1 - min_range);
        else {
            cout << "Ошибка!nМаксимальное значение диапазона чисел должно быть больше минимального!n";
            return 1;
        }
    }
}
// -- end --

// -- Kordan C ++ ---------------------------------------
// Функция вывода на консоль значений элементов массива -
//                                                      -
// Аргументы функции:                                   -
// *arr - Имя массива                                   -
// size - Размер массива                                -
// -- begin ---------------------------------------------
void print (int *arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl << endl;
}
// -- end --



Сообщение добавлено... спустя 22 минуты 25 секунд:
Не понял, что за конструкция в определении среднего.
Код: выделить все · Развернуть
arr[size >> 1]
Дает одинаковый результат с более понятным.
Код: выделить все · Развернуть
arr[size / 2]
Аватар пользователя
Kordan
.
.
      Автор темы
Сообщений: 2447
Возраст: 50
Зарегистрирован: 74 месяцев и 2 дня
Откуда: Саратов
Национальный флаг:
Russia
Благодарил (а): 669 раз.
Поблагодарили: 1223 раз.
Имя: Валерий
Пункты репутации: 25
Молодой трейдерМолодой трейдерМолодой трейдер

С С++ - Вопросы программирования

Номер сообщения:#44  Непрочитанное сообщение coder-ex » 04 фев 2018, 08:22

Kordan писал(а):

Нашел ошибку - передавал в функцию значения мин и макс элементов вместо размерности массива.
Программа заполнения массива случайными числами и его сортировка методом Хоара.
https://pastebin.com/EK39AyN7
Код: выделить все · Развернуть
/*
* Kordan C++ ************************************************************
* Программа заполнения массива определенного размера случайными числами *
*  и его сортировка по возрастанию методом Хоара                        *
* ***********************************************************************
*/
#include <iostream>
#include <cstdlib> // содержит srand() и rand()
#include <ctime>   // содержит time()
using namespace std;

int FillArray (int *arr, const int size, const int min_range, const int max_range);
void quickSort (int *arr, int begin, int end);
void print (int *arr, int size);

int main () {
    setlocale (LC_ALL, "RUS");
    // Количество чисел в массиве
    const int SIZE = 13;
    // Минимальное число в массиве
    const int MIN_RANGE = 13;
    // Максимальное число в массиве
    const int MAX_RANGE = 81;

    int list[SIZE];

    if (FillArray (list, SIZE, MIN_RANGE, MAX_RANGE) != 1) {
        // Выводим значения исходного массива
        print (list, SIZE);
        // Сортируем массив по возрастанию
        quickSort (list, 0, SIZE - 1);
        // Выводим значения отсортированного массива
        print (list, SIZE);
    }

    cout << endl << endl;
    //system ("pause");
    return 0;
}

// -- Kordan С++ -----------------------------------------
// Функция заполнения массива случайными целочисленными  -
// значениями в диапазоне чисел                          -
//                                                       -
// Необходимо подключить:                                -
// #include <cstdlib> (содержит srand() и rand())        -
// #include <ctime>   (содержит time())                  -
//                                                       -
// Аргументы функции:                                    -
// *arr      - Имя массива                               -
// size      - Размер массива                            -
// min_range - Минимальное значение диапазона            -
// max_range - Максимальное значение массива             -
// -- begin ----------------------------------------------
int FillArray (int *arr, const int size, const int min_range, const int max_range) {
    // Автоматическая рандомизация
    srand (time (0));
    for (int i = 0; i < size; i++) {
        if (min_range <= max_range) arr[i] = min_range + rand () % (max_range + 1 - min_range);
        else {
            cout << "Ошибка!nМаксимальное значение диапазона чисел должно быть больше минимального!n";
            return 1;
        }
    }
}
// -- end --

// -- Kordan C ++ ---------------------------------------
// Функция вывода на консоль значений элементов массива -
//                                                      -
// Аргументы функции:                                   -
// *arr - Имя массива                                   -
// size - Размер массива                                -
// -- begin ---------------------------------------------
void print (int *arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl << endl;
}
// -- end --

// -- Kordan C ++ -----------------------------------
// Функция сортировки массива определенного размера - 
// методом Хоара                                    -
//                                                  -
// Аргументы функции:                               -
// *arr  - Имя массива                              -
// begin - Начало массива                           -
// end   - Конец массива                            -
//                                                  -
// Пример использования:                            -
// quickSort (list, 0, SIZE - 1);                   -
// -- begin -----------------------------------------
void quickSort (int *arr, int begin, int end) {
    int first = begin, last = end;
    int piv = arr[(first + last) / 2];
    while (first <= last) {
        while (arr[first] < piv) first++;
        while (arr[last] > piv) last--;
        if (first <= last) swap (arr[first++], arr[last--]);
    }
    if (begin < last) quickSort (arr, begin, last);
    if (end > first) quickSort (arr, first, end);
}
// -- end --


Сообщение добавлено... спустя 2 минуты 1 секунду:
Пока до векторов не дошел и конструкция
Код: выделить все · Развернуть
template< class T >
не знакома.

это шаблоны, без них в с++ ни куда, т.е. в данном случае объект класса любого типа

Сообщение добавлено... спустя 9 минут 3 секунды:
Kordan писал(а):

Усовершенствовал функцию до двух аргументов вместо трех. Также применил автоматическое определение длины массива.
https://pastebin.com/yhNepuJY
Код: выделить все · Развернуть
/*
* Kordan C++ **************************************
* Программа заполнения массива случайными числами *
* и его сортировка по возрастанию методом Хоара c *
* автоматическим определением длины массива       *
* *************************************************
*/
#include <iostream>
#include <cstdlib> // содержит srand() и rand()
#include <ctime>   // содержит time()
#include <malloc.h>// содержит _msize()
using namespace std;

int FillArray (int *arr, const int size, const int min_range, const int max_range);
void sortHoare (int *arr, int end);
void print (int *arr, int size);


int main () {
    setlocale (LC_ALL, "RUS");
    // Количество чисел в массиве
    const int SIZE = 25;
    // Минимальное число в массиве
    const int MIN_RANGE = 1;
    // Максимальное число в массиве
    const int MAX_RANGE = 100;
    int *list = new int[SIZE];

    if (FillArray (list, SIZE, MIN_RANGE, MAX_RANGE) != 1) {
        // Выводим значения исходного массива
        print (list, SIZE);
        // Сортируем массив по возрастанию
        // С помощью выражения "_msize (list) / sizeof (list[0])" получаем размер массива
        sortHoare (list, _msize (list) / sizeof (list[0]) - 1);
        // Выводим значения отсортированного массива
        print (list, SIZE);
    }
    delete[] list;
    cout << endl << endl;
    //system ("pause");
    return 0;
}

// -- Kordan C ++ -----------------------------------
// Функция сортировки массива методом Хоара         -
//                                                  -
// Аргументы функции:                               -
// *arr  - Имя массива                              -
// size  - Конец массива                            -
//                                                  -
// Пример использования:                            -
// quickSort (list, SIZE - 1);                      -
// -- begin -----------------------------------------
void sortHoare (int *arr, int size) {
    int first = 0, last = size;
    int pivot = arr[size >> 1];
    do {
        while (arr[first] < pivot) first++;
        while (arr[last] > pivot) last--;
        if (first <= last) swap (arr[first++], arr[last--]);
    } while (first <= last);
    if (last > 0) sortHoare (arr, last);
    if (size > first) sortHoare (arr + first, size - first);
}
// -- end --

// -- Kordan С++ -----------------------------------------
// Функция заполнения массива случайными целочисленными  -
// значениями в диапазоне чисел                          -
//                                                       -
// Необходимо подключить:                                -
// #include <cstdlib> (содержит srand() и rand())        -
// #include <ctime>   (содержит time())                  -
//                                                       -
// Аргументы функции:                                    -
// *arr      - Имя массива                               -
// size      - Размер массива                            -
// min_range - Минимальное значение диапазона            -
// max_range - Максимальное значение массива             -
// -- begin ----------------------------------------------
int FillArray (int *arr, const int size, const int min_range, const int max_range) {
    // Автоматическая рандомизация
    srand (time (0));
    for (int i = 0; i < size; i++) {
        if (min_range <= max_range) arr[i] = min_range + rand () % (max_range + 1 - min_range);
        else {
            cout << "Ошибка!nМаксимальное значение диапазона чисел должно быть больше минимального!n";
            return 1;
        }
    }
}
// -- end --

// -- Kordan C ++ ---------------------------------------
// Функция вывода на консоль значений элементов массива -
//                                                      -
// Аргументы функции:                                   -
// *arr - Имя массива                                   -
// size - Размер массива                                -
// -- begin ---------------------------------------------
void print (int *arr, int size) {
    for (int i = 0; i < size; i++) {
        cout << *(arr + i) << " ";
    }
    cout << endl << endl;
}
// -- end --



Сообщение добавлено... спустя 22 минуты 25 секунд:
Не понял, что за конструкция в определении среднего.
Код: выделить все · Развернуть
arr[size >> 1]
Дает одинаковый результат с более понятным.
Код: выделить все · Развернуть
arr[size / 2]

твой вариант иногда будет давать не корректный результат, это поразрядный сдвиг, например было число в двоичном виде 0011, после >> 1 ты получишь 0001, в десятичном виде это было 3, а стало 1, а теперь представь что произошло у тебя при 3 / 2, получилось по сути 1.5, и потом выполнилось неявное приведение к типу int, в одних компиляторах это будет 1 в других 2, если к примеру число получилось не 1.5 а 1.500000001 ))
ну и как бы с STL все эти алгоритмы уже реализованы, а значит размер кода будет значительно меньше, я говорю про алгоритмы макс/мин
создай например вектор с размером 1.000.000 элементов, заполни его случайными значениями или значениями из тайм-серий, например цена закрытия на минутках, и затем примени алгоритм из STL получения мин/макс, тут хорошая справка http://ru.cppreference.com/w/cpp/algorithm

ps. а лучше все это на Python реализовать ))
Си — это причудливый, несовершенный, но невероятно успешный язык.
— Dennis M. Ritchie.
Аватар пользователя
coder-ex
.
.
Сообщений: 859
Возраст: 48
Зарегистрирован: 25 месяцев и 2 дня
Откуда: Томск
Национальный флаг:
Russia
Благодарил (а): 10 раз.
Поблагодарили: 22 раз.
Имя: Константин
Пункты репутации: 3
Ученик трейдера

Пред.

Вернуться в Программное обеспечение



Кто сейчас на форуме

Пользователь просматривает форум: нет зарегистрированных пользователей

  • Объявления
cron