ФОРМАЛИЗАЦИЯ языка танца Составитель: учитель информатики МБОУ « СОШ 4 «СОНО» Ефименко Л.Ю.

Сравните две фотографии ДО a[0 ] a[1 ] a[2 ] a[3 ] a[4 ] a[5 ] a[6 ] a[7 ] a[8 ] a[9 ]

ПОСЛЕ a[0 ] a[1 ] a[2 ] a[3 ] a[4 ] a[5 ] a[6 ] a[7 ] a[8 ] a[9 ]

Сортировка элементов одномерного массива.

Сортировка это расстановка элементов массива в заданном порядке ( по возрастанию, убыванию, последней цифре, сумме делителей, …).

С приемами сортировки вы встречались при работе в электронных таблицах, базах данных … Чтобы найти любую информацию : на почте, в библиотеке, в классном журнале, в прайс - листах прежде всего информация должна быть упорядочена

Механические сортировки вам тоже знакомы : построение учеников на уроке физкультуры по росту, солдат на плацу, раскладка денежных купюр в автомате для выдачи денег … имеют место в повседневной жизни и кажутся простыми. 7 из 6

Методы сортировки разделяются по принципу, лежащему в их основе, на сортировки : обменом (' пузырьковая сортировка '); выбором ( выделением ); вставкой ( включением ).

Постановка задачи Входные данные : Выходные данные : Получить конечный продукт : Создать алгоритм сортировки … Написать текст программы на языке Pascal Выполнить программу

Формализация языка танца Выберите алгоритм, который соответствует действиям описанным в Венгерском танце Блок_схема 1 Блок-схема 2

Блок-схема 3 Формализация языка танца

Формализация языка танца - фрагмент текста программы for j:= 0 to N-1 do { цикл по числу "проходов" } for i:= 0 to N-1 do { цикл сравнения элементов в оставшейся части массива } if A[i] > A[i+1] then { Сравнение пары рядом стоящих элементов} begin x:=A[i]; A[i]:=A[i+1]; { переставляем элементы } A[i+1]:=x; end;

Сортировка методом « пузырька » В пузырьковой сортировке последовательно просматриваются пары соседних элементов массива, и если левый элемент пары больше правого, то есть порядок нарушен, то они меняются местами ( отсюда происходит название « метод обмена »). В результате самый большой элемент массива оказывается на своем законном последнем месте. Он как бы « всплывает » наверх подобно пузырькам в стакане газировки, самые большие из которых проталкиваются к поверхности ( отсюда второе название метода - пузырьковая сортировка ). Для того, чтобы все элементы оказались на своих местах, надо проделать процедуру просмотра и обмена элементов несколько раз.

Текст программы

Результат работы программы