§21 Создание собственных функций для работы с контейнером. Алгоритмы сортировки и поиска

Функции и контейнеры

Вынос функций для работы с контейнерами за пределы main.cpp

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

  • Инициализация массива
  • Ввод элементов
  • Вывод элементов
Дабы не повторять в каждой программе разработанные ранее алгоритмы, мы вынесем часто используемые функции в другие файлы проекта. Объявление функций и шаблоны функций мы поместим в заголовочный файл с именем inf-w.h, а остальные функции (в том числе перегруженные) мы поместим в файл inf-w.cpp. В последствии, мы будем давать лишь ссылку на эти файлы, без публикации их содержимого (или только тело функции, а всю остальную работу по их внедрению вы проведете самостоятельно). Это упростит чтение и изучение материала последующих занятий. Итак, какие функции мы для этих целей создадим?
  • int Rnd(int a, int b) и double Rnd(double a, double b) – перегруженная функция, создает случайное число в промежутке [a, b]
  • void ini_ar(size_t s, T a, T b, Arg& arg) – шаблонная функция для ввода элементов массива Arg&, размер которого s
  • void print_ar(bool flag, Arg& arg) – шаблонная функция для вывода элементов массива Arg&
Здесь T – это либо тип int, либо тип double, a Arg – тип контейнера vector (для других контейнеров потребуется внести изменения). Реализации этих функций (определения) Rnd, сортировок и поиска должны быть записаны в файле inf-w.cpp, содержимое этого файла можно посмотреть под спойлером ниже:

Код файла inf-w.cpp cpp-21.1
inf-w.cpp
#include "inf-w.h"
#include <vector>
#include <chrono>
#include <random>

using namespace std;
using namespace chrono;

// Генерация случайного числа, перегруженная функция Rnd
int Rnd (int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> d(a, b);
    return d(rnd);
}
double Rnd (double a, double b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_real_distribution<double> d(a, b);
    return d(rnd);
}

// Пузырьковая сортировка (или сортировка методом "Пузырька")
void mySortBubble(vector<int> &mas, int &r) {
    for (size_t i = 0; i < mas.size() - 2; i++)
        for (size_t j = 0; j < mas.size() - i - 1; j++) {
            r++;
            if (mas[j] > mas[j + 1]) {
                int buf = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = buf;
            }
        }
}

void mySortBubble(vector<double> &mas, int &r) {
    for (size_t i = 0; i < mas.size() - 2; i++)
        for (size_t j = 0; j < mas.size() - i - 1; j++) {
            r++;
            if (mas[j] > mas[j + 1]) {
                double buf = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = buf;
            }
        }
}
Шаблоны функций очень удобны, если необходимо писать версии одной и той же функции несколько раз для разных типов данных (как, например, для функций Rnd и mySortBubble). Но реализация шаблона должна помещаться в заголовочном файле. Причину этого мы обсуждаем ниже.
Заголовочный файл inf-w.h должен быть включен с помощью директивы #include во все файлы проекта. В нем должны быть объявлены и функции определенные в файле inf-w.cpp. Его содержание под спойлером ниже:

Код файла inf-w.h cpp-21.2
inf-w.h
// Дата создания 16.06.2020
#ifndef INFW_H
#define INFW_H

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

// Случайное число
int Rnd (int, int);
double Rnd (double, double);

// Сортировка пузырьком
void mySortBubble(std::vector<int>&, int&);
void mySortBubble(std::vector<double>&, int&);

// Инициализация массива. Обратите внимание!
// Все шаблонные функции должны находиться в этом файле!
template <typename T, typename Arg>
void ini_ar(size_t s, T a, T b, Arg& arg) {
    if (!arg.empty()) arg.clear();
    arg.reserve(s);
    for (size_t i = 0; i < s; i++) {
        arg.push_back(Rnd(a, b));
    }
}

// Вывод массива
template <typename Arg>
void print_ar(bool flag, Arg& arg) {
    if (flag) {
        cout.precision(2);
        for (auto r : arg)
            cout << r << setw(4);
        cout << endl;
    } else {
        for (auto r : arg)
            cout << r << setw(3);
        cout << endl;
    }
}

#endif // INFW_H
Исходный код файла с главной функцией (mail.cpp) смотрите ниже (cpp-21.5.2).

Проект в Qt Creator

Создайте новый проект в IDE Qt Creator (проект без Qt, приложение на языке C++). Перейдите в меню: Файл > Создать файл или проект. Появится окно:

Выберите в разделе “Файлы и классы” > С++ > Файл исходных текстов C++. Перенесите исходный текст и сохраните под именем inf-w.cpp (или любым другим). Аналогичным образом создайте файл inf-w.h (пункт Заголовочный файл C++). Обратите внимание, что в файле проекта *.pro сохраняются сведения о включении данных файлов в проект, а также на опцию CONFIG с помощью которой компилятору указывается на используемый стандарт языка (по умолчанию C++11):

TEMPLATE = app
CONFIG += console c++17
CONFIG -= app_bundle
CONFIG -= qt

SOURCES += \
        inf-w.cpp \
        main.cpp \

HEADERS += \
    inf-w.h
Проект в Code::Blocks

Создайте новый проект в IDE Code::Blocks: Create a new project > Console application. Далее File > New > File (New from template). Появится окно:

Создайте файлы: C/C++ source и C/C++ header. Укажите полный путь к файлам inf-w.h и inf-w.cpp. Установите цель сборки. Это может быть Release или Debug (либо и то, и другое).

Таргет Debug предназначен для использования на этапе разработки и отладки программы, а таргет Release – применяется для финальной сборки программы и последующего её использования
Не забудьте в Code::Blocks установить поддержку C++17: меню программы Settings > Compiler… > Global compiler settings > Have g++ follow the coming C++1z (aka C+17) ISO (установить флажок).
Глобальный и локальный массив

Мы объявили два массива для целых и действительных элементов: iv и dv. Насколько это хорошая идея? Если в продолжении работы программы производятся манипуляции с одним и тем же массивом, то идея правильная. Поскольку здесь мы использовали подход в процедурном стиле. Однако, если массив будет создаваться временно, для каких-либо целей, то он не должен объявляться глобально, даже в функции main(). Этот массив должен объявляться локально, внутри функции, с последующим удалением по выходу из функции. Это равно относится и к контейнерам. ООП-подход, с использованием классов, позволяет по другому посмотреть на решение этой задач. В этом случае, массив должен быть инкапсулирован (скрыт) в каком-то базовом классе. Об этом речь пойдет в дальнейшем, но пока мы остановимся на реализации файлов проекта в процедурном стиле. В этом случае, массив будет объявлен, по крайней мере, в файле main.cpp.

Функции и контейнеры

Итак, разберем подробнее как отправить контейнер в функцию. Собственно, большой разницы, по сравнению с отправкой в функцию C-массива, нет. Так функция print_ar вполне может быть использована и для C-массива. Нужно уяснить следующие моменты. Во-первых, контейнеры – это часть стандартной библиотеки и определены они в пространстве имен STD. Во-вторых, тип массива включает шаблонный параметр – тип элементов контейнера. В-третьих, контейнеры, необходимо передавать по ссылке, а не копированием (равно как и возвращать из функции). Об этом уже ранее упоминали, когда говорили о структурах. Рассмотрим простой пример:

Программа cpp-21.3
#include <iostream>
#include <vector>

using namespace std;
bool vecComp(vector<int>&, vector<int>&);
vector<int>& vecMult(vector<int>&, vector<int>&);
void vecPrint(vector<int>&);

int main() {
    vector<int> v1 {1, 2, 3, 4 ,5};
    vector<int> v2 {2, 3, 4, 5, 6};

    cout << boolalpha << vecComp(v1, v2) << endl;
    vecPrint(vecMult(v1, v2));

    return 0;
}

bool vecComp(vector<int> &ar1, vector<int> &ar2) {
    return ar1 > ar2;
}
vector<int>& vecMult(vector<int> &ar1, vector<int> &ar2) {
    for (size_t i = 0; i < ar1.size(); ++i) {
        ar1[i] *= ar2[i];
    }
    return ar1;
}
void vecPrint(vector<int> &ar) {
    for (auto r : ar) {
        cout << r << " ";
    }
    cout << endl;
}

Вывод

false
2 6 12 20 30 

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

Контейнер как параметр шаблона функции

Работа с шаблоном несколько сложнее. Дело в том, что vector – абстрактный тип, который может хранить значения различного типа, в том числе абстрактного. И синтаксис vector<int> – является абстрактным типом, что не даст возможности обобщить для разных типов контейнеров. Как здесь быть?
Рассмотрим задачу. Пусть даны два массива – один целых чисел, а второй действительных. Необходимо увеличить каждый элемент в два раза, в не зависимости от того, какого типа массив передан в функцию (мы имеем в виду vector).

Программа cpp-21.4
#include <iostream>
#include <vector>

using namespace std;

template <typename Arg>
void vecMult2(Arg& arg) {
    for (auto &a : arg) {
        a *= 2;
    }
}

template <typename T>
void vecPrint(vector<T>& v) {
    for (auto &a : v) {
        cout << a << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v1 {1, 2, 3, 4 ,5};
    vector<double> v2 {0.1, 3.6, 2.4, 5.3, 5.0, 1.1};

    vecMult2(v1);
    vecMult2(v2);
    vecPrint(v1);
    vecPrint(v2);

    return 0;
}

Обратите внимание, что здесь использовались два разных подхода. В первом варианте шаблонный параметр Arg – обеспечивает ссылку на неизвестный тип. Однако он станет известным после передачи объекта, а значит можно будет работать с любым методом класса vector. Например, такая инструкция (внутри шаблона) будет возможна:

cout << arg.size() << endl;

Второй вариант требует включения заголовочного файла vector в том месте, где объявлена шаблонная функция, поскольку шаблонный параметр становится шаблонным параметром самого вектора.
В этой программе шаблоны объявлены в файле main.cpp, но в больших проектах, состоящих из нескольких файлов, шаблоны выносятся в заголовочный файл. Если вы попробуете сохранить шаблоны в файле *.cpp, то это приведет к ошибке во время компиляции с сообщением "undefined reference...". В чем же дело? Дело в том, что C++ компилирует файлы по отдельности. Если не будет известно как инстанцировать шаблоны (иначе говоря, сопоставить или подменить шаблонный тип T - реальным типом), то файлы будут откомпилированы, но код будет иметь ссылки на неизвестные внешние определения. Ошибка появляется при линковке и процесс сборки завершается аварийно.

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

Сортировка. Квадратичные сортировки

Для упорядочивания элементов массива необходимо использовать алгоритмы сортировки. Важность сортировки для массивов заключается в том, что нужный элемент в упорядоченном массиве можно найти гораздо быстрее, нежели в неупорядоченном.
Различают два вида сортировки: по возрастанию (от меньшего к большему) или по убыванию (от большего к меньшему). Если в массиве имеются равные элементы, то сортировка в направлении от меньшего к большему называется сортировкой по не убыванию, а от большего к меньшему - сортировкой по не возрастанию.
Все сортировки характеризуются сложностью или времнем работы. Сортировки, сложность которых оценивается как O(n2) в среднем и худшем времени работы, называются квадратичными. Здесь n - это размер массива, который нужно упорядочить, а n * n означает количество операций, которые выполнит алгоритм. К квадратичным сортировкам относятся Пузырьковая сортировка (Bubble Sort) и Сортировка вставками (Insertion Sort). Квадратичные сортировки уступают в скорости сортировкам, имеющими сложность O(n*log(n)). К таким сортировкам относятся Быстрая сортировка (Quick Sort) и Сортировка слиянием (Merge Sort). Квадратичные сортировки используются для обучения программированию и только. В реальных проектах их использовать не следует! Ниже мы сравним две реализации сортировок Пузырьковая и Быстрая.

Пузырьковая сортировка (сортировка обменами)

Название сортировки произошло от аналогии с известным физическим явлением: всплытия пузырька воздуха на поверхность в жидкости. Идея алгоритма состоит в следующем. Во внешнем цикле определяется граница области сравнения, а во вложенном цикле сравниваются рядом стоящие элементы: на первом шаге 1-й и 2-й, затем 2-й и 3-й и т. д. Производится обмен, откуда и название. Более "легкий" элемент постепенно перемещается ("всплывает") в начало массива. С каждым шагом внешнего цикла интервал перебора элементов будет сужаться, а в области, которая находится вне просматриваемой, будут уже находиться упорядоченные элементы.
Реализуем программу с помощью контейнера vector. Приведем фрагмент файла в котором реализована перегруженная функция mySortBubble(). В функцию добавлена переменная-счетчик для определения количества итераций для сравнения.

Программа cpp-21.5.1 (фрагмент файла inf-w.cpp)
void mySortBubble(vector<int> &mas, int &r) {
    for (size_t i = 0; i < mas.size() - 2; i++)
        for (size_t j = 0; j < mas.size() - i - 1; j++) {
            r++;
            if (mas[j] > mas[j + 1]) {
                int buf = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = buf;
            }
        }
}

Файл main.cpp, с включением в проект файлов inf-w.cpp и inf-w.h, может быть реализован следующим образом:

Программа cpp-21.5.2 (Файл main.cpp)
#include <iostream>
#include "inf-w.h"
#include <vector>
#include <chrono>

using namespace std;
using namespace chrono;

int main() {
    //========================================================//
    // Эта часть программы предназначена для формирования     //
    // и вывода элементов массива                             //
    //========================================================//
    vector<int> iv; // Создадим массивы для тестирования
    vector<double> dv;
    size_t n_ar; // Размер массива
    bool t_ar;   // Его тип (int или double?)
    cout << "Какой массив создать?\n"
            "0 - int\n"
            "1 - double" << endl;
    cout << " => ";
    cin >> t_ar;
    cout << "Введите длину массива: ";
    cin >> n_ar;
    cout << "Введите интервал случайных чисел [x, y]:" << endl;
    if (!t_ar) {
        int x, y;
        cout << "x => "; cin >> x;
        cout << "y => "; cin >> y;
        ini_ar(n_ar, x, y, iv);
        print_ar(t_ar, iv);
    } else {
        double x, y;
        cout << "x => "; cin >> x;
        cout << "y => "; cin >> y;
        ini_ar(n_ar, x, y, dv);
        print_ar(t_ar, dv);
    }
    //========================================================//
    // Пузырьковая сортировка                                 //
    //========================================================//
    int cnt {}; // Счетчик итераций
    if (!t_ar) {
        auto start = system_clock::now();
        mySortBubble(iv, cnt);
        auto end = system_clock::now();
        cout << "Количество итераций: "
             << cnt << endl;
        print_ar(t_ar, iv);
        auto elapsed = end - start;
        cout << "Скорость выполнения: "
             << duration_cast<microseconds>(elapsed).count()
             << " мкс"
             << endl;
    } else {
        mySortBubble(dv, cnt);
        cout << "Количество итераций: "
             << cnt << endl;
        print_ar(t_ar, dv);
    }
    //========================================================//
    return 0;
}

Возможный вывод

Какой массив создать?
0 - int
1 - double
 => 0
Введите длину массива: 50
Введите интервал случайных чисел [x, y]:
x => 10
y => 99
62 89 19 51 50 82 36 71 94 57 26 11 13 57 41 56 47 80 43 11 65 54 29 50 80 11 67 32 47 85 96 48 12 82 54 89 92 85 58 18 32 35 55 53 70 18 74 64 87 41
Количество итераций: 1224
11 11 11 12 13 18 18 19 26 29 32 32 35 36 41 41 43 47 47 48 50 50 51 53 54 54 55 56 57 57 58 62 64 65 67 70 71 74 80 80 82 82 85 85 87 89 89 92 94 96
Скорость выполнения: 8 мкс

В этот файл мы добавили измерение времени выполнения процедуры сортировки с помощью библиотеки chrono (которая используется в проекте и для генерации случайного числа).
Если есть необходимость поменять направление сортировки, то для этого всего лишь требуется поменять знак сравнения в инструкции if на противоположный.

Быстрая сортировка

Быстрая сортировка или сортировка Хоара (quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Идея алгоритма заключается в следующем. В массиве выбирается опорный элмент. Это может быть любой из элементов массива. (От выбора опорного элемента, в отдельных случаях, может зависеть эффективность алгоритма). Далее сравниваются все остальные элементы с опорным и переставляются в массиве так, чтобы разбить массив на два непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного» и «большие». Для отрезков «меньших» и «больших» значений выполняются рекурсивные вызовы. Существует и нерекурсивная реализация с использованием стека.
Функция myQsort может выглядеть следующим образом:

Программа cpp-21.5.2 (фрагмент файла inf-w.cpp)
void myQsort(vector<int> &mas, size_t l, size_t r, int &k) {
    size_t L = l, R = r;
    int M = mas[(l + r) / 2]; // опорный эл-т
    do {
        k++; // счетчик итераций
        while (mas[l] < M) l++;
        while (mas[r] > M) r--;
        if (l <= r) {
            int buff = mas[l]; // обмен
            mas[l]   = mas[r];
            mas[r]   = buff;
            l++; // двигаемся дальше
            r--;
        }
    } while (l < r); // рекурсивные вызовы
    if (L < r) myQsort(mas, L, r, k);
    if (l < R) myQsort(mas, l, R, k);
}
Возможный вывод
Какой массив создать?
0 - int
1 - double
 => 0
Введите длину массива: 500 
Введите интервал случайных чисел [x, y]:
x => 10
y => 99
Исходный массив:
72 16 23 81 55 35 53 35 22 95 57 19 62 93 30 97 68 76 96 57 76 37 48 99 28 87 95 94 53 64 79 88 25 42 98 63 29 25 47 15 96 10 90 19 79 93 77 47 86 68 12 45 65 76 72 71 99 19 17 92 51 96 21 72 85 74 56 72 33 93 66 23 36 59 97 87 51 38 61 21 91 97 65 41 66 84 24 67 81 86 21 82 71 27 54 48 79 92 76 88 91 36 40 95 26 87 19 25 66 88 62 11 40 90 67 27 87 41 20 14 35 12 89 44 75 64 38 28 97 81 60 97 66 99 65 13 68 11 13 41 51 96 52 78 80 14 58 93 20 37 82 49 61 70 80 74 16 93 56 81 30 66 14 68 47 80 38 95 19 68 11 82 67 63 34 69 95 51 67 91 75 37 72 95 48 17 62 82 25 80 98 51 21 81 15 40 89 66 27 47 33 17 25 43 33 67 97 13 23 28 16 74 22 57 76 32 61 57 37 21 74 41 52 23 89 93 91 81 61 40 97 57 42 66 16 30 58 56 37 21 27 14 76 45 14 96 75 18 40 54 50 61 63 78 92 56 15 61 30 88 79 51 81 32 84 70 96 27 87 37 49 86 18 88 94 29 68 69 36 18 52 75 10 84 30 33 50 82 57 14 82 84 22 29 18 37 50 32 34 67 52 76 87 15 60 65 81 13 18 85 70 34 83 20 79 12 86 53 21 28 21 36 36 40 85 89 19 49 87 77 51 55 55 89 48 81 60 41 59 52 67 95 56 41 17 40 69 58 25 44 16 88 69 97 75 54 87 83 82 19 40 34 75 17 23 69 10 64 43 45 32 22 30 71 59 28 13 31 10 78 11 42 62 65 31 55 80 51 70 64 29 57 24 79 57 41 38 79 28 88 95 95 44 99 54 29 87 44 53 73 77 52 59 43 63 30 77 94 79 50 27 67 83 74 60 86 21 11 63 92 40 55 79 39 84 49 60 85 90 51 85 47 45 30 58 31 18 47 55 78 83 27 88 76 39 13 98 25 10 47 52 87 54 34 38 72 49 21 37 48 25 82 84 83 61 47 36 43 30 42 82 95 68 21 32 74 39 50 98 18 23 21 32 84 61 33 99 45 37 48
Пузырьковая сортировка.
Количество итераций: 124749
10 10 10 10 10 11 11 11 11 11 12 12 12 13 13 13 13 13 13 14 14 14 14 14 14 15 15 15 15 16 16 16 16 16 17 17 17 17 17 18 18 18 18 18 18 18 19 19 19 19 19 19 19 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 23 23 23 23 23 23 24 24 25 25 25 25 25 25 25 25 26 27 27 27 27 27 27 27 28 28 28 28 28 28 29 29 29 29 29 30 30 30 30 30 30 30 30 30 31 31 31 32 32 32 32 32 32 33 33 33 33 33 34 34 34 34 34 35 35 35 36 36 36 36 36 36 37 37 37 37 37 37 37 37 37 38 38 38 38 38 39 39 39 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 42 42 42 42 43 43 43 43 44 44 44 44 45 45 45 45 45 47 47 47 47 47 47 47 47 48 48 48 48 48 48 49 49 49 49 49 50 50 50 50 50 51 51 51 51 51 51 51 51 51 52 52 52 52 52 52 52 53 53 53 53 54 54 54 54 54 55 55 55 55 55 55 56 56 56 56 56 57 57 57 57 57 57 57 57 58 58 58 58 59 59 59 59 60 60 60 60 60 61 61 61 61 61 61 61 61 62 62 62 62 63 63 63 63 63 64 64 64 64 65 65 65 65 65 66 66 66 66 66 66 66 67 67 67 67 67 67 67 67 68 68 68 68 68 68 68 69 69 69 69 69 70 70 70 70 71 71 71 72 72 72 72 72 72 73 74 74 74 74 74 74 75 75 75 75 75 75 76 76 76 76 76 76 76 76 77 77 77 77 78 78 78 78 79 79 79 79 79 79 79 79 79 80 80 80 80 80 81 81 81 81 81 81 81 81 81 82 82 82 82 82 82 82 82 82 83 83 83 83 83 84 84 84 84 84 84 84 85 85 85 85 85 86 86 86 86 86 87 87 87 87 87 87 87 87 87 87 88 88 88 88 88 88 88 88 89 89 89 89 89 90 90 90 91 91 91 91 92 92 92 92 93 93 93 93 93 93 94 94 94 95 95 95 95 95 95 95 95 95 95 96 96 96 96 96 96 97 97 97 97 97 97 97 97 98 98 98 98 99 99 99 99 99
Скорость выполнения: 557 мкс
x => 10
y => 99
Исходный массив: 
42 56 15 20 60 31 55 18 12 26 22 37 10 43 74 52 95 67 43 95 88 70 56 14 25 23 86 83 68 40 62 96 49 75 21 22 95 47 44 99 66 24 17 52 82 30 47 84 58 76 52 63 77 40 66 41 79 26 81 52 54 54 63 23 44 91 89 84 15 12 95 34 98 71 61 32 39 21 66 51 46 91 48 38 34 48 73 53 36 98 46 72 84 77 91 43 63 32 87 63 94 26 61 40 47 37 65 42 76 61 52 46 32 58 81 30 56 47 32 31 42 39 40 70 20 58 10 75 80 60 36 18 33 38 30 24 28 50 95 90 70 31 86 48 20 96 40 60 84 91 18 34 44 45 43 35 51 94 51 87 21 87 95 31 42 29 45 94 86 34 43 86 88 35 28 31 94 55 11 19 47 28 15 64 87 77 66 54 16 36 69 37 12 13 22 78 46 72 39 40 55 74 37 20 64 37 70 48 86 11 64 13 69 94 84 11 71 81 25 17 12 54 26 77 64 41 40 28 54 96 35 24 62 92 15 12 86 12 97 14 88 20 67 98 20 39 12 90 69 23 14 69 51 84 91 53 31 32 42 54 16 90 93 73 89 68 97 18 74 33 63 70 81 96 89 34 29 44 46 17 46 70 60 57 81 84 89 45 40 58 60 97 25 77 41 97 57 68 40 97 70 21 13 66 20 87 30 19 57 21 59 62 61 41 86 56 26 16 91 37 83 44 69 30 42 17 60 46 78 72 89 14 32 74 66 96 58 26 67 50 66 95 13 55 74 74 50 68 27 59 30 20 80 74 18 89 82 55 91 93 51 63 92 81 73 75 76 79 73 30 66 43 22 73 55 60 34 22 12 34 79 35 64 81 59 70 34 87 23 66 56 82 26 44 34 39 14 22 75 97 81 63 19 10 89 80 82 26 79 44 70 29 38 48 46 74 28 53 32 36 46 85 26 64 32 51 29 77 24 30 27 81 59 68 24 38 96 32 23 79 25 50 41 92 40 73 75 67 25 38 63 48 39 79 73 89 35 74 13 24 13 99 65 96 29 49 26 34 93 22 61 23 21 73 48 63 67 13 86 24 85 75 85 35 90 41 14 41 55 51 74 72 92 27 83 22 66 69 80 92
Быстрая сортировка.
Количество итераций: 1554
10 10 10 11 11 11 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 14 14 14 14 14 14 15 15 15 15 16 16 16 17 17 17 17 18 18 18 18 18 19 19 19 20 20 20 20 20 20 20 20 21 21 21 21 21 21 22 22 22 22 22 22 22 22 23 23 23 23 23 23 24 24 24 24 24 24 24 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 27 27 27 28 28 28 28 28 29 29 29 29 29 30 30 30 30 30 30 30 30 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 33 33 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 35 36 36 36 36 37 37 37 37 37 37 38 38 38 38 38 39 39 39 39 39 39 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 42 42 42 42 42 42 43 43 43 43 43 43 44 44 44 44 44 44 44 45 45 45 46 46 46 46 46 46 46 46 46 47 47 47 47 47 48 48 48 48 48 48 48 49 49 50 50 50 50 51 51 51 51 51 51 51 52 52 52 52 52 53 53 53 54 54 54 54 54 54 55 55 55 55 55 55 55 56 56 56 56 56 57 57 57 58 58 58 58 58 59 59 59 59 60 60 60 60 60 60 60 61 61 61 61 61 62 62 62 63 63 63 63 63 63 63 63 63 64 64 64 64 64 64 65 65 66 66 66 66 66 66 66 66 66 66 67 67 67 67 67 68 68 68 68 68 69 69 69 69 69 69 70 70 70 70 70 70 70 70 70 71 71 72 72 72 72 73 73 73 73 73 73 73 73 74 74 74 74 74 74 74 74 74 74 75 75 75 75 75 75 76 76 76 77 77 77 77 77 77 78 78 79 79 79 79 79 79 80 80 80 80 81 81 81 81 81 81 81 81 81 82 82 82 82 83 83 83 84 84 84 84 84 84 84 85 85 85 86 86 86 86 86 86 86 86 87 87 87 87 87 87 88 88 88 89 89 89 89 89 89 89 89 90 90 90 90 91 91 91 91 91 91 91 92 92 92 92 92 93 93 93 94 94 94 94 94 95 95 95 95 95 95 95 96 96 96 96 96 96 96 97 97 97 97 97 97 98 98 98 99 99
Скорость выполнения: 56 мкс
Замер скорости работы алгоритмов mySortBubble и myQsort и подсчет количества итераций дал следующие результаты:

Производительность сортировок
mySortBubble myQsort
Количество итераций Время, мкс Количество итераций Время, мкс
500 элементов
124749 557 1554 56
1000 элементов
499499 2193 3584 77

Из приведенной таблицы видно, что эффективность "Пузырьковой" сортировки значительно уступает Быстрой сортирове с увеличением количества элементов.

Быстрый поиск в массиве

Как уже было сказано, эффективный алгоритм поиска можно реализовать только в упорядоченном массиве. Один из самых простых алгоритмов - это алгоритм бинарного (двоичного) поиска. Идея алгоритма заключается в следующем. Вместо того, чтобы перебирать все элементы массива, сравнивая каждый элемент с исходным числом, массив делится пополам и "средний" элемент сравнивается с искомым. Отсюда делается вывод в какой половине массива нужно продолжать поиск. Код функции возвращающий позицию элемента. Если в массиве несколько элементов с таким значением, то функция вернет позицию последнего такого элемента.

Программа cpp-21.5.3 (фрагмент файла inf-w.cpp)
size_t myBinSearch(vector<int> &mas, int &r, int x) {
    size_t L = 0, R = mas.size(), q;
    do {
        q = (R + L) / 2; // середина массива
        if (mas[q] > x)
            R = q; // "курсор" справа
        else
            L = q; // "курсор" слева
        r++; // счетчик итераций
    } while (L < R - 1);
    return L;
}
Исходники урока
Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Print Friendly, PDF & Email

Обсуждение закрыто.