Алгоритмизация и программирование
Ключевые слова:
До сих пор мы работали с простыми типами данных. При решении практических задач данные часто объединяются в различные структуры данных, например в массивы. В языках программирования массивы используются для реализации таких структур данных, как последовательности (одномерные массивы) и таблицы (двумерные массивы).
Упорядоченное множество однотипных переменных (элементов массива), которым можно присвоить общее имя, различающихся номерами (индексами), называют массивом.
Мы будем рассматривать одномерные массивы. Решение разнообразных задач, связанных с обработкой массивов, базируется на использовании таких типовых алгоритмов, как:
· суммирование значений элементов массива;
· поиск элемента с заданными свойствами;
· сортировка массива.
2.2.6. Сортировка массива
Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.
Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют неубывающим.
Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют невозрастающим.
Цель сортировки — облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.
Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов реализации механизма этой операции — сортировку выбором.
Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:
в массиве выбирается максимальный элемент; максимальный и первый элементы меняются местами (первый элемент считается отсортированным); в неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива; действия, описанные в п. 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).
var <имя_массива>: array [<мин_знач_индекса> .. <макс_знач_индекса>] of тип_элементов;
Заполнять массив можно либо вводя значение каждого элемента с клавиатуры, либо присваивая элементам некоторые значения в программе. При заполнении массива и его выводе на экран используется цикл с параметром.
При решении разнообразных задач, связанных с обработкой массивов, используются такие типовые алгоритмы, как: суммирование элементов массива; поиск элемента с заданными свойствами; сортировка массива.
Рассмотрим процесс сортировки выбором на примере массива а = {0, 1, 9, 2,4, 3, 6, 5}.
|
Индекс |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
Значение |
0 |
1 |
9 |
2 |
4 |
3 |
6 |
5 |
|
|
Шаги |
1 |
0 |
1 |
9 |
2 |
4 |
3 |
6 |
5 |
|
2 |
9 |
1 |
0 |
2 |
4 |
3 |
6 |
5 |
|
|
3 |
9 |
6 |
0 |
2 |
4 |
3 |
1 |
5 |
|
|
4 |
9 |
6 |
5 |
2 |
4 |
3 |
1 |
0 |
|
|
5 |
9 |
6 |
5 |
4 |
2 |
3 |
1 |
0 |
|
|
6 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
|
7 |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
|
Итог: |
9 |
6 |
5 |
4 |
3 |
2 |
1 |
|
|
В этом массиве из восьми элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из n элементов такая операция будет проводиться n-1 раз. Объясните почему.
Приведём фрагмент программы, реализующий описанный алгоритм:
for i:=l to n-1 do begin
imax:=i;
for j:=i+l 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/fiashprog/demos.php) вы сможете поработать с интерактивными наглядными пособиями для того, чтобы более полно представить процесс сортировки выбором и другими способами.
Вопросы и задания
1.Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику.Какими слайдами вы могли бы дополнить презентацию?
2.Что подразумевает понятие вложенный цикл?
3.Какими способами можно заполнить массив?
Самое главное
Так же как циклы позволяют компактно записывать большое количество действий, массивы позволяют компактно обозначить (дать имя) большой объем информации. Массив имеет одно имя и много элементов, занумерованных Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке. целыми числами. Цель сортировки заключается в том,чтобы облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.