Задания к данному параграфу. Задание 1. Задайте массив целых чисел a[1:n]

Задание 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. Алгоритм и программа на языке Ершол сортировки элементов массива методом простого обмена








Дата добавления: 2015-01-26; просмотров: 551; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2020 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.015 сек.