аварийно. Это связано с тем, что если в массиве нет ни одного отрицательного элемента, переменной ineg значение не присваивается. Поэтому в операторе for (оператор 4) будет использовано значение i neg, ниспосланное Богом. Обычно всевышний таких ошибок не прощает, и программа незамедлительно вылетает . Поэтому в программу необходимо внести проверку, есть ли в массиве хотя бы один отрицательный элемент. Для этого переменной ineg присваивается начальное значение, не входящее в множество допустимых индексов массива (например, -1). После цикла поиска номера отрицательного элемента выполняется проверка, сохранилось ли начальное значение i neg неизменным. Если это так, это означает, что условие a[i ] < О в операторе 3 не выполнилось ни разу, и отрицательных элементов в массиве нет:

finclude <iostream.h>

int main(){ int n:

cout Введите количество элементов : cin n:

float sum. *a - new float [n]: 1

int i:

cout Введите элементы массива: : for (i - 0: i < n: i++) cin a[i]: int ineg = -1:

for (i - 0: i < n: i++) if (a[i] < 0) ineg - i: 3

if (ineg != -1){

for (sum = 0. i = ineg + 1: i < n: i-н-) sum + а[1]:

cout \пСумма sum endl:

else cout \пОтрицательных элементов нет endl: return 0:

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

finclude <iostream.h> int main(){ int n:

cout Введите количество элементов: : cin n: float *a = new float [n]; int i:

cout Введите элементы массива: : for (i = 0: i < n: cin a[i]: bool flag neg = false: float sum = 0:

for (i = n - 1: i >= 0: i--) { if (a[i] < 0) { flag neg = true: break: } sum += a[i]:

if (flag neg) cout \пСумма sum:

else cout \пОтрицательных элементов нет :

return 0:

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

Для исчерпывающего тестирования этой программы необходимо ввести по крайней мере три варианта исходных данных - когда массив содержит один, несколько или ни одного отрицательного элемента.

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

Мы рассмотрели примеры задач поиска и вычисления в массиве. Другой распространенной задачей является сортировка массива, то есть упорядочивание его элементов в соответствии с каким-либо критерием - чаще всего по возрастанию или убыванию элементов. Существует множество методов сортировки, различающихся по поведению, быстродействию, требуемому объему памяти, а также ограничениям, накладываемым на исходные данные. В Учебнике (см. с. 59) рассмотрен один из наиболее простых методов - сортировка выбором. Он характеризуется квадратичной зависимостью времени сортировки t от количества элементов:

t-a-N + b-N-lgN,

тдеаиЬ - константы, зависящие от программной реализации алгоритма. Иными словами, для сортировки массив требуется просмотреть порядка раз. Существуют алгоритмы и с лучшими характеристиками самый известный из которых предложен Ч. Э. Р. Хоаром и называется быстрая сортировка . Для него зависимость имеет вид:

t-a-NlgN + b-N.

Давайте ради любопытства посмотрим, за счет чего достигается экономия.

Задача 3.3. Быстрая сортировка массива

Написать программу, которая упорядочивает вещественный массив методом быстрой сортировки.

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

Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие, чем элемент, выбранный в качестве среднего, а в правой - ббльшие. Это

Думать иногда оказывается полезным.

Впрочем, если в процессоре поддерживается опережающее считывание данных, этот вариант окажется медленнее.

Кстати, наихудшим по характеристикам является любимый студентами метод пузырька. LMD.

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

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

ПРИМЕЧАНИЕ ---

Существует более простая реализация метода быстрой сортировки, основанная на рекурсии. Мы рассмотрим ее на седьмом семинаре.

В приведенной ниже программе стек реализуется в виде двух массивов stack г и stack 1 и одной переменной sp, используемой как указатель на вершину стека (она хранит номер последнего заполненного элемента массива). Для этого алгоритма количество элементов в стеке не может превышать п, поэтому размер массивов задан равным именно этой величине. При занесении в стек переменная sp увеличивается на единицу, а при выборке - уменьшается. Про данный способ реализации стека рассказывается в Учебнике на с. 126. Ниже приведена программа, реализующая этот алгоритм.

finclude <iostream.h> finclude <n)ath.h> int main(){

const int n = 20:

float агг[п]. middle, temp:

int *stackl = new int [n]. *stackr = new int [n]. sp = 0; int i, j, left, right: cout Введите элементы массива: : for (i = 0: i < n; i++) cin arr[i]; Сортировка

sp = 1: stackUl] = 0: stackr[l] = n - 1: 1

while (sp > 0) { Выборка из стека последнего запроса left = stacklCsp]; right - stackrCsp]: sp-:

while (left < right) { Разделение {arr[left] .. arr[right]} i = left: j = right: middle = arr[(left + right) / 2]: while (i < j) { while (arr[i] < middle) i++: while (middle < arr[j]) j--: if (i <= j) { temp = arr[i]: arr[i] = arr[j]: arr[j]

temp;

i++: j-:

if (i < right) { Запись в стек запроса из правой части sp++;

StacklCsp] i: StackrCsp] = right:

right = j:

Теперь left и right ограничивают левую часть

2

7 8 9 10 11

12

13

Вывод результата

for (i = 0: i < n: i++) cout arrCi] : cout endl;

return 0:

Ha каждом шаге сортируется один фрагмент массива. Левая граница фрагмента хранится в переменной left, правая - в переменной right. Сначала фрагмент устанавливается размером с массив целиком (строка 1). В операторе 8 выбирается сред-, НИИ элемент фрагмента.

Для продвижения по массиву слева направо в цикле 10 используется переменная i. справа налево - переменная j (в цикле 11). Их начальные значения устанавливаются в операторе 7, После того, как оба счетчика сойдутся где-то в средней части массива, происходит выход из цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые границы левой части для сортировки на следующем шаге.

Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла б, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3,4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.

3 Зах.784

Добавьте в программу подсчет количества итераций основного цикла. Прогоните программу несколько раз для массивов с большим количеством элементов и сравните с аналогичной программой, реализующей метод выбора. Сделайте выводы. Метод быстрой сортировки был предложен Ч. Хоаром. Впоследствии дотошный исследователь этого и других методов сортировки Д. Кнут (D. Knuth) установил, что размер стека может быть уменьшен до величины logjR, если после каждого появления двух частей, подлежащих дальнейшей обработке, более длинную часть откладывать на потом (помещать в стек), а более короткую обрабатывать немедленно. В качестве дополнительного упражнения напишите улучшенную версию программы, в которой реализована эта идея и размер стека уменьшен до logjH. Быстрая сортировка является одним из лучших методов упорядочивания, однако существует целый ряд алгоритмов, которые предпочтительнее применять для данных, отвечающих определенным критериям. Советуем вам на досуге ознакомиться с этими алгоритмами. Выбор наиболее подходящего для каждого случая метода сортировки данных - показатель класса программиста. Давайте повторим основные моменты этого семинара.

1. Размерность не-динамического массива может быть только константой или константным выражением. Рекомендуется задавать размерность с помощью именованной константы.

2. Элементы массивов нумеруются с нуля, поэтому максимальный номер элемента всегда на единицу меньше размерности.

3. Автоматический контроль выхода индекса за границы массива не производится, поэтому программист должен следить за этим самостоятельно.

4. Указатель - это переменная, в которой хранится адрес области памяти.

5. Имя массива является указателем на его нулевой элемент.

6. Обнуления динамической памяти при ее выделении не происходит. Инициализировать динамический массив нельзя.

7. Освобождение памяти, выделенной посредством new[ ], выполняется с помощью операции del ete[ ].

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

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

10. Алгоритмы сортировки массивов различаются по быстродействию, занимаемой памяти и области применения.

Для удобства можно заменить ввод с клавиатуры на генерацию случайной последовательности с помощью функций srand и rand (см. Учебник, с. 433.435).

Задания

Задания этого семинара соответствуют приведенным в Учебнике на с. 136. При написании программ можно использовать как динамические, так и нединамические массивы. Размерность последних задается именованной константой.

Вариант 1

в одномерном массиве, состоящем из п вещественных элементов, вычислить:

1) сумму отрицательных элементов массива;

2) произведение алементов массива, расположенных между максимальным и минимальным элементами.

Упорядочеть элементы массива по возрастанию.

Вариант 2

в одномерном массиве, состоящем из п вещественных элементов, вычислить:

1) сумму положительных элементов массива;

2) произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами.

Упорядочить элементы массива по убыванию.

Вариант 3

в одномерном массиве, состоящем из п целых элементов, вычислить:

1) произведение элементов массива с четными номерами;

2) сумму элементов массива, расположенных между первым и последним нулевыми элементами.

Преобразовать массив таким образом, чтобы сначала располагались все положительные элементы, а потом - все отрицательные (элементы, равные О, считать положительными).

Вариант 4

в одномерном массиве, состоящем из п вещественных элементов, вычислить:

1) сумму элементов массива с нечетными номерами;

2) сумму элементов массива, расположенных между первым и последним отрицательными элементами.

Сжать массив, удалив из него все элементы, модуль которых не превышает 1. Освободившиеся в конце массива элементы заполнить нулями.

Вариант 5

в одномерном массиве, состоящем из п вещественных элементов, вычислить: 1) максимальный элемент массива;