C++: реализации алгоритмов сортировки

Введение

Сегодня формирование программ для компьютерного оборудования является не только средством, правильное применение которого способствует производительной работе фактически в любой прикладной сфере, но также является и областью научных исследований. Очевидным является тот факт, что обладание алгоритмами имеет решающее значение при выработке решений о структурировании данных. Потоки самой разной информации непрерывно возрастают.

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

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

Специалисты подсчитали, что примерно четверть времени централизованной компьютерной обработки отводится под сортировку данных. Это обстоятельство объясняется тем фактом, что значительно легче отыскать нужное значение в массиве, если он был предварительно отсортирован. В противном случае процесс поиска будет похожим на обнаружение иголки в стоге сена. Пользователи занимаются поиском информации в базах данных практически постоянно. Это означает необходимость наличия поисковых алгоритмов. Но следует помнить, что поисковые алгоритмы способны работать намного быстрее с базами данных, которые уже прошли сортировку.

C++: реализации алгоритмов сортировки

Прежде всего, следует рассмотреть сортировку выбором (Selection sort). Для того чтобы выполнить сортировку массива в порядке возрастания, необходимо при каждой итерации обнаружить компонент, имеющий самое большое значение. Его следует поменять местами с последним компонентом. Следующий компонент с самым большим значением нужно поставить уже на предпоследнее место. Эту процедуру необходимо продолжать до тех пор, пока компоненты, которые находятся на первых местах в массиве, не будут расположены в необходимом порядке. Ниже приведена программная реализация данного алгоритма сортировки на языке C++:

Рисунок 1. Машинный код. Автор24 — интернет-биржа студенческих работ

Далее рассмотрим реализацию алгоритма пузырьковой сортировки (Bubble sort). При пузырьковой сортировке осуществляется сравнение соседних компонентов, и они меняются местами, когда последующий компонент меньше предыдущего. Необходимо выполнить несколько проходов по информационным данным. При первом проходе выполняется сравнение первых двух компонентов в массиве. Если они расположены не в нужном порядке, то их следует поменять местами и далее приступить к сравнению компонентов следующей пары. На тех же условиях они могут меняться местами. Таким образом, сортировка реализуется во всех циклах до тех пор, пока не будет достигнут конец массива. Ниже приведена программная реализация данного алгоритма сортировки на языке C++:

Рисунок 2. Машинный код. Автор24 — интернет-биржа студенческих работ

Далее рассмотрим реализацию алгоритма сортировки вставками (Insertion sort). При выполнении сортировки вставками массив должен быть разбит на две области, а именно:

1. Упорядоченная область.
2. Неупорядоченная область.

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

Главный цикл алгоритма должен работать в интервале от 1 до N-1. На j-й итерации компонент [ì] должен вставляться в правильное положение в упорядоченной области. Это реализуется путем сдвига всех компонентов упорядоченной области, больших, чем [i], на одну позицию вправо. [ì] должен быть вставлен в интервале между теми компонентами, которые меньше [ì], и теми, которые больше [ì]. Ниже приведена программная реализация данного алгоритма сортировки на языке C++:

Рисунок 3. Машинный код. Автор24 — интернет-биржа студенческих работ

Далее рассмотрим реализацию алгоритма сортировки слиянием (Merge sort). При реализации рекурсивной сортировки слиянием массив вначале следует разбить на мелкие составляющие. На первом этапе предполагается, что эта составляющая равна одному компоненту. Далее эти составляющие должны объединяться в более крупные компоненты. А именно, сравниваются два компонента, а в результате в новой составляющей меньший компонент занимает место слева, а больший компонент занимает место справа. Затем происходит слияние в ещё более крупные составляющие и так до завершения алгоритма.