Программа 16. Сортировка массива

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

В программе надо выполнить действия:

1) заполнить массив значениями;

2) распечатать исходный массив;

3) отсортировать массив;

4) распечатать упорядоченный массив.

Заполнение, печать и сортировку массива реализуем в виде отдельных функций.

Массив для сортировки и его максимальный размер объявляются в начале программы как внешние переменные, а определяются в ее конце. Размер массива задается константой SIZEARR достаточно большого размера, чтобы выделенной под массив памяти хватило в большинстве случаев использования программы. Конкретный размер массива вводится пользователем и проверяется на допустимость. При вводе недопустимого размера массива вызывается функция

void exit(int k),

которая завершает работу программы и возвращает в вызывающую программу значение своего аргумента. Эта функция объявлена в stdlib.h.

Для заполнения массива числами в программе предусмотрена функция

void get_array(int x[], int n);

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

int rand(),

объявленной в stdlib.h. Функция rand возвращает псевдослучайное число в диапазоне от 0 до RAND_MAX. Величина RAND_MAX определяется в файле stdlib.h. Обычно это 32767.

Чтобы обеспечить получение при каждом запуске программы новой последовательности случайных чисел, вызывается функция:

void randomize(void);

которая инициализирует генератор случайных чисел, связывая первое случайное число с показаниями системных часов. Эта функция объявлена также в stdlib.h.

Для сортировки массива по возрастанию написана функция:

void bubble_sort(int x[], int n);

использующая алгоритм «пузырька», состоящий в следующем. Организуется проход по массиву, в котором сравниваются соседние элементы и, если предшествующий элемент оказывается больше следующего, они меняются местами. В результате первого прохода наибольший элемент оказывается на своем, последнем месте («всплывает»). Затем проход по массиву повторяется до предпоследнего элемента, затем до третьего с конца массива и т.д. В последнем проходе по массиву сравниваются только первый и второй элементы.

// Файл SortArr.cpp

// Сортировка массива

#include <iostream.h>

#include <conio.h>

// Объявление внешних переменных

extern int x[]; // Объявление массива

extern const int SIZEARR; // Объявление размера массива

// Объявления функций

void get_array(int[], int n); // Заполнение массива из n элементов

void bubble_sort(int[], int n); // Сортировка массива методом пузырька

void prn_array(int[], int n); // Вывод массива

#include <stdlib.h> // Для exit, rand и randomize

int main()

{

int n; // Размер массива

cout << "\nВведите размер массива < " << SIZEARR << ": ";

cin >> n;

if(n > SIZEARR || n<=0){ // Проверка размера

cout << "Размер массива " << n << "не подходит \n";

exit(1); // Завершение программы

}

get_array(x, n); // Заполнение массива

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

prn_array(x, n); // Вывод исходного массива

bubble_sort(x, n); // Сортировка

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

prn_array(x, n); // Вывод упорядоченного массива

getch();

return 0;

}

// Определение функций

// get_array: заполняет массив x случайными числами

void get_array(int x[], int n)

{

int i; // Локальная переменная

randomize(); // Инициализация генератора случайных чисел

for(i = 0; i < n; i++)

x[i] = rand(); // rand генерирует целое случайное число

}

// prn_array: вывод массива

void prn_array(int x[], int n)

{

int i;

for(i = 0; i < n; i++)

cout << x[i] << ", ";

}

// bubble_sort: сортировка массива x методом пузырька

void bubble_sort(int x[], int n)

{

int i, j, tmp;

for(i = n - 1; i > 0; i--) // i задает верхнюю границу

for(j = 0; j < i; j++) // Цикл сравнений соседних элементов

if(x[j] > x[j + 1]){ // Если нет порядка,

tmp = x[j]; // перестановка местами

x[j] = x[j + 1]; // соседних

x[j + 1] = tmp; // элементов

}

}

// Определение внешних переменных

const int SIZEARR = 100; // Размер массива

int x[SIZEARR]; // Массив

Далее приведен пример работы программы.

Введите размер массива < 100: 10

Исходный массив:

346, 130, 10982, 1090, 11656, 7117, 17595, 6415, 22948, 31126

Отсортированный массив:

130, 346, 1090, 6415, 7117, 10982, 11656, 17595, 22948, 31126

Обратим внимание на то, как меняются значения двух элементов массива. Для этого используется специальная промежуточная переменная tmp.

Рекурсия

В языке C++ функции могут быть рекурсивными, то есть вызывать сами себя.

Рассмотрим печать целого числа как последовательности цифр. Цифры числа легко получать, начиная с конца числа как остатки от деления на 10, но печатать их нужно в правильной последовательности. Напишем рекурсивную функцию printd, которая будет вызывать сама себя, чтобы напечатать все старшие цифры, а затем печатает последнюю младшую цифру.