Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задания к данному параграфу
|
|
Задание 1. Задайте массив целых чисел a[1: n ]. Смоделируйте последовательность преобразований содержимого памяти при реализации сортировки элементов массива методами:
· методом простого выбора;
· методом простых включений, стр. 147, 149, 151;
· методом простого обмена, суть метода изложена ниже;
· улучшенным методом сортировки обменом, когда необходимо запомнить, производился ли на данном проходе массива обмен элементов, если нет, то сортировку массива закончить;
· улучшенным методом сортировки обменом, когда необходимо запомнить не только, производился ли на данном проходе массива обмен элементов, но и место последнего обмена, следующие проходы можно закончить на этом индексе, вместо того, чтобы сравнивать элементы до установленной границы i.
Задание 2. Составьте блок-схемы алгоритмов решения задач задания 1, напишите программы на языках программирования, отличных от Ершола.
Пояснение к выполнению задания
Идея метода сортировки массивов простым обменом
Идея сортировки простым обменом элементов массива a[1: n ] заключается в повторении n -1 раз попарных сравнений рядом стоящих элементов массивов A[1: n ], A[2: n ], A[3: n ], A[4: n ], …, A[ n -1: n ]. Каждый из этих массивов содержит на один элемент меньше, чем предыдущий. При сравнении элементы массива переставляются в заданном порядке, поэтому при каждом проходе элемент a[ i ], i изменяется от 1 до n -1, занимает своё место в отсортированной части массива. Последний элемент массива после попарных сравнений n -1 раз и обменов, если необходимо, стоит тоже на своём месте в отсортированном массиве. Элементы массивов просматриваются либо от конца к началу, либо от начала к концу. При сортировке будем просматривать элементы массивов A[1: n ], A[2: n ], A[3: n ], A[4: n ], …, A[ n -1: n ] от конца к началу, и массив отсортируем по возрастанию значений элементов массива. Алгоритм сортировки элементов массива методом простого обмена и программа на языке Ершол даны в таблице 10.
Программа сортировки массивов простым обменом и сущность
этого метода
| алг сортобмен нач 1шаг. Введи элементы массива в память компьютера. 2 шаг. Для i изменяющегося от 2 до n выполни следующие шаги. 2.1 шаг. Для j, изменяющегося от n до i с шагом -1, выполни следующие шаги. 2.1.1 шаг. Сравни элементы a[ j ] и a[ j -1]. Если a[ j ] < a[ j -1], то поменяй их местами. 2.1.2 шаг. Организуй вывод элементов массива, полученного при прохождении текущего цикла. кон | алг сортобмен (аргцел n) начцел i, j, b, целтаб a[1: n] │ input(n, a) │ print(n, a) │ нцдля i от 2 до n │ │ нцдля j от n до i ша г -1 │ │ │ есл и a[j] < a[j-1] │ │ │ │ то │ │ │ │ |обмен значениями a[j] и a[j-1] │ │ │ │ b: =a[j]; a[j]: =a[j-1]; a[j-1]: =b │ │ │ вс е │ │ кц │ │ print (n, a) │ кц кон Вспомогательные алгоритмы input и print смотри в таблице 9. |
| Таблица 10. Алгоритм и программа на языке Ершол сортировки элементов массива методом простого обмена |