Стандартные алгоритмы работы с одномерными массивами

1.Ввод элементов массива с клавиатуры:

const int n=20;

int b[n];

int i;

for (i=0; i<n; i++) cin >> b[i];

2.Ввод элементов массива с помощью генератора случайных чисел:

const int n=20;

int b[n];

int i;

randomize();

for (i=0; i<n; i++) b[i]=random(100) - 50; // генерирование случайных

// чисел в диапазоне [-50; 50].

При использовании функций randomize() и random() подключается библиотека stdlib.h.

3.Вывод элементов массива на экран:

const int n=20;

int b[n];

int i;

for (i=0; i<n; i++) cout << b[i];

4. Поиск максимального элемента в массиве и запоминание позиции максимального элемента в массиве:

const int n=20;

int b[n];

int i, n_max;

max=b[0];

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

if (max >b[i])

{

max = b[i]; n_max=i;

}

cout <<”Максимальный элемент массива b[”<<n_ max<<”]=”<<max;

5. Поиск минимального элемента в массиве и запоминание позиции минимального элемента в массиве:

const int n=20;

int b[n];

int i, n_min;

min=b[0];

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

if (min >b[i])

{

min = b[i]; n_min=i;

}

cout <<”Минимальный элемент массива b[”<<n_ min<<”]=”<<min;

6. Сортировка целочисленного массива методом выбора

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

Алгоритм состо­ит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом, затем рассматриваются элементы, начиная со второго, и наи­меньший из них меняется местами со вторым элементом, и так далее n-1 раз (при последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива).

#include <iostream.h>

int main(){

const int n = 20; // количество элементов массива

int b[n]; // описание массива

int і;

for (і = 0; i<n; і++) сіn >> b[i]; // ввод массива

for (і = 0; і<n-1; і++)

{

// n-1 раз ищем наименьший элемент

// принимаем за наименьший первый из рассматриваемых элементов

int imin = i;

// поиск номера минимального элемента из неупорядоченных

for (int j = i + 1; j<n; j++)

// если нашли меньший элемент, запоминаем его номер:

if (b[j] < b[imin]) imin = j;

int a = b[i]; // обмен элементов

b[i] = b[imin]; // с номерами

b[imin] = a; // i и imin

}

// вывод упорядоченного массива:

for (i =0; i<n; i++) cout << b[i] << “ ”;

return 0;

}

Процесс обмена элементов массива с номерами і и іmin через буферную перемен­ную а на і-м проходе цикла проиллюстрирован на рис. 5.1. Цифры около стрелок обозначают порядок действий.

Рис. 5.1. Обмен значений двух переменных

7. Сортировка целочисленного массива методом пузырьковой сортировкой.

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

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

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

// Эта программа сортирует значения массива в возрастающем порядке

#include <iostream.h>

#include <iomanip.h>

main() {

const int arraySize = 10;

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

int hold;

cout << "Элементы данных в исходном порядке" << endl;

for (int і = 0; і < arraySize; і++)

cout << setw(4) << a[i];

for (int pass = 1; pass < arraySize; pass++) // проход

for (і = 0; і < arraySize - 1; і++) // один проход

if (a[i] > a[i + 1]) { // одно сравнение

hold = a[i]; // одна перестановка

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

а[і + 1] = hold;

}

cout <<endl << "Элементы данных в порядке возрастания " << endl;

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

cout << setw(4) << a[i];

cout << endl; return 0;

}

Идентификатор массива является константным указателем на его нулевой элемент. Например, для массива из предыдущего листинга имя b – это то же самое, что &b[0], а к 1-му элементу массива можно обратиться, используя выражение *(b+i). Можно описать указатель, присвоить ему адрес начала массива и работать с массивом через указатель. Следующий фрагмент программы копирует все элементы массива а в массив b:

int a[100], b[100];

int *pa = а; // или int *p = &a[0];

int *pb = b;

for (int i = 0; i<100; i++)

*pb++ = *pa++; // или pb[i] = pa[i];