Урок 23

 

---

Алгоритмизация и программирование

Ключевые слова:

• сортировка

• вложенный цикл

• сортировка выбором

До сих пор мы работали с простыми типами данных. При решении практических задач данные часто объединяются в различные струк­туры данных, например в массивы. В языках программирования массивы используются для реализации таких структур данных, как последовательности (одномерные массивы) и таблицы (двумерные массивы).

Упорядоченное множество однотипных переменных (элементов масси­ва), которым можно присвоить общее имя, различающихся номерами (индексами), называют массивом.

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

·         суммирование значений элементов массива;

·         поиск элемента с заданными свойствами;

·         сортировка массива.

​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.Какими способами можно заполнить массив?

---

Самое главное

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