cout Значение а[3] равно а[3] endl;

4,, return 0;

void modifyArray(int b[], int sizeOfArray)

for (int j = 0; j < SizeOfArray; j++) i b[j] *= 2;

T void modifyElement(int e)

cout << Значение в modifyElement равно (e *= 2) endl; -. I }

Рис. 4.14. Передача функциям массивов и отдельных элементов массива (часть 2 из 3)

Результаты передачи всего массива по ссылке:

1кж Значения исходного массива: 0 12 3 4

а Значения модифицированного массива 0 2 4 6 8

Результаты передачи элемента массива по значению:

Значение а[3] равно 6 Значение в modifyElement равно 12 Значение а[3] равно 6

-lij.- cout Результаты передачи всего массива по ссылке

**> endl endl

<< Значения исходного массива: << endl; for (int i = 0; i < arraySize; i++) cout setw(3) a[ i ];

%\ cout endl;

modifyArray (a, arraySize); массив, передается по ссылке

cout << Значения модифицированного массива: << endl;

for (i =0; i < arraySize; i++) cout << setw(3) a[ i ];

cout endl << endl endl

<< Результаты передачи элемента массива по значению:

endl << endl Значение а[3] равно

Ч а[3] endl;

modifyElement(а[3]);

void tryToModifyArray(conct int b[ ]; {

b[0] /= 2

b[l] /= 2

b[2] /= 2

ошибка ошибка ошибка

Compiling FIG4 15.CPP:

Error FIG4 15.CPP 16: Cannot modify a cost object Error FIG4 15.CPP 17:Cannot modify a cost object Error FIG4 15.CPP 18: Cannot modify a cost object Warning FIG4 15.CPP 19: Parametr b is never used

Рис. 4.15. Демонарация спецификации типа const

4.6. Сортировка массивов

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

Совет по повышению эффективности 4.3

Часто простейшие алгоритмы обеспечивают низкую производительность. Их досто-инаво лишь в том, что их легко писать, проверять и отлаживать. Однако, часто для получения максимальной производительности необходимы более сложные алгоритмы.

Программа на рис. 4.16 сортирует значения массива а из 10 элементов в возрастающем порядке. Используемая при этом техника получила название пузырьковая сортировка или сортировка погружением, потому что наимень-

Демонстрация спецификации типа const tinclude <iostream.h>

void tryToModifуАггау(conct int b[]) {

int a[ ] = {10, 20, 30};

cout a[0] a[l] a[2] endl; return 0;

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

Сначала программа сравнивает а[0] и а[1], затем а[1] и а[2], потом а[2] и а[3] и т.д. до тех пор, пока проход не закончится сравнением а[8] и а[9]. Хотя элементов 10, производится только девять сравнений. При выбранном способе последовательных сравнений большое значение может перемещаться в массиве вниз на много позиций за один проход, но малое значение может быть передвинуто вверх только на одну позицию. При первом проходе наибольшее значение гарантированно опустится на место нижнего элемента массива а[9]. При втором проходе второе наибольшее значение гарантированно опустится на место а[8]. При девятом проходе девятое наибольшее значение опустится на место а[1]. Это оставляет наименьшему значению место а[0], так что для сортировки массива из 10 элементов нужно только девять проходов.

Сортировка выполняется с помощью вложенного цикла for. Если необходима перестановка, она выполняется тремя присваиваниями

hold = а[i] ; a[i] = a[i + 1]; a[i + 1] = hold;

где дополнительная переменная hold временно хранит одно из двух переставляемых значений. Перестановку нельзя выполнить двумя присваиваниями

a[i] = a[i + 1]; a[i + 1] = a[i];

Если, например, a[i] равно 7, а a[i + 1] равно 5, то после первого присваивания оба значения будут 5, а значение 7 будет потеряно. Следовательно, необходима дополнительная переменная hold.

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

Эта программа сортирует значения массива в возрастающем порядке iinclude <iostream.h> iinclude <iomanip.h>

main() {

const int arraySize = 10;

int a[arraySize] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37); int hold;

cout << Элементы данных в исходном порядке endl; Рис. 4.16. Пузырьковая сортировка массива (часть 1 из 2)