Программа 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, которая будет вызывать сама себя, чтобы напечатать все старшие цифры, а затем печатает последнюю младшую цифру.