C++: базовый курс

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

Алгоритм сортировки пузырьковым методом получил свое название от способа, используемого для упорядочивания элементов массива. Здесь выполняются повторяющиеся операции сравнения и при необходимости меняются местами смежные элементы. При этом элементы с меньшими значениями постепенно перемещаются к одному концу массива, а элементы с большими значениями — к другому. Этот процесс напоминает поведение пузырьков воздуха в резервуаре с водой. Пузырьковая сортировка выполняется путем нескольких проходов по массиву, во время которых при необходимости осуществляется перестановка элементов, оказавшихся "не на своем месте". Количество проходов, гарантирующих получение отсортированного массива, равно количеству элементов в массиве, уменьшенному на единицу.

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

// Использование метода пузырьковой сортировки

// для упорядочения массива.

#include

#include

using namespace std;

int main()

{

　int nums[10];

　int a, b, t;

　int size;

　size = 10; // Количество элементов, подлежащих сортировке.

　// Помещаем в массив случайные числа.

　for(t=0; t

　// Отображаем исходный массив.

　cout << "Исходный массив: ";

　for(t=0; t

　cout << '\n';

　// Реализация метода пузырьковой сортировки.

　for(a=1; a

　　for(b=size-1; b>=a; b--) {

　　　if(nums[b-1] > nums[b]) {     // Элементы неупорядочены.

　　　　// Меняем элементы местами.

　　　　t = nums[b-1];

　　　　nums[b-1] = nums[b];

　　　　nums[b] = t;

　　　}

　　}

　}

　// Конец пузырьковой сортировки.

　// Отображаем отсортированный массив.

　cout << "Отсортированный массив: ";

　for(t=0; t

　　cout << nums[t] << ' ';

　return 0;

}

Хотя алгоритм пузырьковой сортировки пригоден для небольших массивов, для массивов большого размера он становится неэффективным. Более универсальным считается алгоритм Quicksort. В стандартную библиотеку C++ включена функция qsort(), которая реализует одну из версий этого алгоритма. Но, прежде чем использовать ее, вам необходимо изучить больше средств C++. (Подробно функция qsort() рассмотрена в главе 20.)

Строки

Чаще всего одномерные массивы используются для создания символьных строк. В C++ строка определяется как символьный массив, который завершается нулевым символом ('\0'). При определении длины символьного массива необходимо учитывать признак ее завершения и задавать его длину на единицу больше длины самой большой строки из тех, которые предполагается хранить в этом массиве.

Строка — это символьный массив, который завершается нулевым символом.

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

char str [11];

Заданный здесь размер (11) позволяет зарезервировать место для нулевого символа в конце строки.

Как упоминалось выше в этой книге, C++ позволяет определять строковые литералы. Вспомним, что строковый литерал — это список символов, заключенный в двойные кавычки. Вот несколько примеров.

"Привет"

"Мне нравится C++"

"#$%@@#$"

""

Строка, приведенная последней (""), называется нулевой. Она состоит только из одного нулевого символа (признака завершения строки). Нулевые строки используются для представления пустых строк.

Вам не нужно вручную добавлять в конец строковых констант нулевые символы. С++-компилятор делает это автоматически. Следовательно, строка "ПРИВЕТ" в памяти размещается так, как показано на этом рисунке:

Считывание строк с клавиатуры