Содержание

Главная >> Информатика 9 класс. Босова

§ 2.2. Одномерные массивы целых чисел

Сортировка массива целых чисел

Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.

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

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

Цель сортировки — облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.

Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов¹ реализации механизма этой операции — сортировку выбором.

¹ С другими способами сортировки вы познакомитесь на уроках информатики в 10-11 классах.

Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:

1) в массиве выбирается максимальный элемент;
2) максимальный и первый элементы меняются местами (первый элемент считается отсортированным);
3) в неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива;
4) действия, описанные в п. 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).

Рассмотрим процесс сортировки выбором на примере массива а = {0, 1, 9, 2, 4, 3, 6, 5}.

В этом массиве из восьми элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из n элементов такая операция будет проводиться n-1 раз. Объясните почему.

Приведём фрагмент программы, реализующий описанный алгоритм:

for i:=l to n-1 do
begin
imax:=i;
for j:=i+1 to n do if a[j]>a[imax] then imax:=j;
x:=a[i];
a[i]:=a[imax];
a[imax]:=x
end;

Здесь мы использовали один цикл внутри другого. Такая конструкция называется вложенным циклом.

Запишите полный текст программы и выполните её на компьютере для рассмотренного в примере массива а.

На сайте «Интерактивные демонстрации по программированию» (http://informatika.kspu.ru/flashprog/demos.php) вы сможете поработать с интерактивными наглядными пособиями для того, чтобы более полно представить процесс сортировки выбором и другими способами.

САМОЕ ГЛАВНОЕ Массив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элементов в массиве. В языках программирования массивы используются для реализации таких структур данных, как последовательности и таблицы. Перед использованием в программе массив должен быть описан. Общий вид описания одномерного массива: var <имя_массива>: array [<мин_знач_индекса> .. <макс_знач_индекса>] of тип_элементов;

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

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