для j от 1 до N-1выбрать среди M[j],.., M[N] наименьший элемент и поменять его местами с M[j] кц

Лабораторная работа № 7.

Тема: «Алгоритми сортування, злиття та пошуку»

Теоретические сведения. Наиболее широко известная структура данных - массив. Массив состоит из компонент одного типа, называемого базовым. Поэтому структура массивов однородна. Кроме того, массивы относят к так называемым структурам с прямым доступом. Для того чтобы обозначить отдельную компоненту, к имени всего массива добавляется индекс. Индекс - это значение специального типа, определенного как тип индекса массива. Количество индексов называется размерностью массива. Отметим, что в памяти ПЭВМ каждой компоненте массива отводится отдельное поле равных размеров, при этом, все элементы массива расположены подряд.

Если х является переменной-массивом размерности n, то отдельная компонента обозначается с помощью имени массива, за которым следует индекс требуемой компоненты – х_i. Иногда компоненты массивов называют переменными с индексами.

Обычный прием работы с массивами, в особенности с большими массивами – выборочное изменение отдельных его компонент, а не конструирование полностью нового составного значения. При этом переменная-массив рассматривается как массив составляющих переменных, и возможно присваивание значений отдельным компонентам, например, х_i ← 0.456.

Поиск. Для определенности примем, что множество, в котором осуществляется поиск, задано как массив: a:array[0..n] of item;

Линейный поиск. Процедура заключается в простом последовательном просмотре всех элементов массива и сравнения их с эталоном x.

Поиск делением пополам (бинарный поиск). В большинстве случаев процедура поиска применяется к упорядоченным данным (телефонный справочник, библиотечные каталоги и пр.). В подобных ситуациях эффективным алгоритмом является поиск делением пополам. В этом методе сравнение эталона X осуществляется с элементом, расположенным в середине массива и в зависимости от результата сравнения (больше или меньше) дальнейший поиск проводится в левой или в правой половине массива.

Пример 1. Составить блок-схему нахождения в одномерном массиве из п элементов порядковых номеров максимального и минимального элементов. Значение элементов и их порядковые номера вывести на экран (рис. 1).

Рис. 1. Блок-схема примера 1.

 

 

Сортировка массивов. В общем случае сортировку следует понимать как перегруппировку заданного множества объектов (массива, файла и т.д.) в некотором порядке. Цель сортировки - облегчить последующий поиск элементов в таком отсортированном множестве. Выбор алгоритма сортировки зависит от структуры обрабатываемых данных. Рассмотрим основные методы сортировки применительно к одномерным массивам.

 

Дан одномерный массив размерности n: a₀, a₁,…, a_n-1. Сортировка данного массива есть перестановка его элементов в массив где при некоторой упорядочивающей функции f

выполняются отношения

 

Обычно упорядочивающая функция не вычисляется, а хранится как явная компонента каждого элемента. Ее значение называется ключом элемента. Основное условие при выборе метода сортировки массивов - выбранный метод должен экономно использовать доступную память. Это предполагает, что перестановки, приводящие элементы в порядок, должны выполняться на том же месте («in site»). Методы сортировки «in site» можно разбить в соответствии с определяющими их принципами на три основные типа - сортировка с помощью прямого включения; сортировка с помощью прямого выбора; сортировка с помощью прямого обмена.

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

Псевдокод сортировки методом вставок представлен ниже под названием I n- sertion__sort. На его вход подается массив А [1.. п ], содержащий последователь­ность из п сортируемых чисел (количество элементов массива А обозначено в этом коде как length [A].) Входные числа сортируются без использования дополни­тельной памяти: их перестановка производится в пределах массива, и объем используемой при этом дополнительной памяти не превышает некоторую посто­янную величину. По окончании работы алгоритма inserti0n_s0rt входной массив содержит отсортированную последовательность:

 

 

Сортировка с помощью прямого выбора. Метод основан на следующих принципах. Выбирается элемент с наименьшим значением. Он меняется с первым элементом x₁. Затем этот процесс повторяется с оставшимися n -1 элементами, n - 2 элементами и т.д. до тех пор, пока не останется один, самый больший элемент.

Сказанное можно описать следующим образом:

для j от 1 до N-1выбрать среди M[j],..., M[N] наименьший элемент и поменять его местами с M[j] кц

 

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

Каждый из изложенных выше методов сортировки допускает оптимизацию, основанную на анализе массива (отсортирован или нет), полученного на каждом шаге алгоритма.

Псевдокод сортировки методом пузырька представлен ниже под названием Bubblesort. На его вход подается массив А [1.. п ], содержащий последователь­ность из п сортируемых чисел (количество элементов массива А обозначено в этом коде как length [A].)

 

 

Пример 2. Составить блок-схему сортировки по неубыванию одномерного целочисленного массива размерности n методом «пузырька» (рис. 2).

Рис. 2. Блок-схема примера 2.

 

СОДЕРЖАНИЕ ОТЧЕТА

 

1. Тема, краткие теоретические сведения.

2. Задание согласно варианту.

3. Блок-схема.

4. Текст рограммы.

5. Результат работы программы (скриншоты).

6. Выводы.

 

Варианты заданий.

1. В одномерном массиве из п элементов найти порядковые номера первого отрицательного и последнего положительного элементов (если таковые имеются). Значение элементов и их порядковые номера вывести на экран или выдать соответствующее сообщение.

2. Ввести одномерный массив из п элементов. Вычислить сумму всех отрицательных чисел, их количество и сумму всех положительных чисел.

3. Превратить массив Х по следующему правилу: все отрицательные элементы массива перенести в начало, а все другие - в конец, храня исходное взаимное расположение, как среди негативных, так и среди других элементов.

4. В зависимости от того, образуют элементы заданного массива целых чисел из п элементов строго убывающую, не возрастающую, строго возрастающую, неубывающую последовательность, выдать соответствующее сообщение.

5. Ввести одномерный массив из п элементов. Сформировать на его месте новый массив, в котором первым элементом будет последний элемент старого, вторым - предпоследний и т.д.

6. Таблица выигрышей денежной лотереи подается в виде массива номеров, которые выиграли a₁,...,a_n и массивом выигрышей в гривнях p₁,...,p_n (p_i- это выигрыш, который выпадает на номер a_i (i=1,...,n)). Определить суммарный выигрыш, который выпадает на билет с номерами b₁,...,b_m. Для решения задачи использовать алгоритм деления пополам.

7. Элемент называется локальным минимумом (максимумом), если у него нет соседа, меньшего (большего), чем он сам. Найти все локальные минимумы и максимумы в заданном массиве из п элементов.

8. В неубывающей последовательности из п элементов найти количество элементов, меньших заданного числа и напечатать их.

9. Выполнить попарное суммирование произвольного конечного ряда чисел следующим образом. На первом этапе суммировать попарно рядом стоящие числа, на втором - результаты первого этапа аналогичным образом, и т.д., пока не останется одно число.

10. Даны два вектора размерности п. Вычислить их скалярное произведение.

11. В массиве из п элементов выбрать без повторений все элементы, встречающиеся более одного раза.

12. Ввести одномерный массив из п элементов. Определить число различных элементов в нем.

13. Ввести одномерный массив из п элементов. Отсортировать массив по неубыванию (невозрастанию) методом прямого включения.

14. Ввести одномерный массив из п элементов. Отсортировать массив по неубыванию (невозрастанию) методом прямого выбора.

15. Получить упорядоченный по возрастанию массив С(n + m) путем слияния массивов А(n) и В(m); массивы А(n) и В(m) предварительно упорядочить по возрастанию.

16. Рассмотрим массив целых или действительных чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Использовать алгоритм вставки.

17. Рассмотрим массив целых или действительных чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: последовательным пересмотром чисел а₁,...,a_n найти наименьшее такое, что a_i>a_i+1. а₁,...,a_n Поменять местами a_i и a_i+1, дальше опять начать пересмотр с элемента a_i+1 и т.д. Следующие пересмотры начинать опять, уменьшая количество элементов, которые пересматриваются.

18. Рассмотрим массив целых или действительных чисел а₁,...,a_n. Переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию а₁<=а₂<=...<=a_n. Для решения этой задачи можно использовать следующий алгоритм: пересмотреть последовательность а₂,...,a_n и каждый новый элемент a_i включить на то место, которое входит в уже упорядоченную последовательность а₁,...,a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами а₁,...,a_i-1.

19. Нехай задано впорядкований по не спаданню масив цілих або дійсних чисел a₁<=a₂<=...<=a_n та деяке число b (відповідно ціле або дійсне), для якого потрібно знайти таке місце серед чисел a₁,...,a_n, щоб після вставки числа b на це місце впорядкованість не зруйнувалась. Якщо внаслідок рівності між собою деяких елементів масиву число b можна включити на різні місця, то потрібно визначити місце, яке є найближчим до початку масиву.

20. Дано масив з k символів. Вивести на екран спочатку всі цифри, що входять у нього, а потім всі інші символи, зберігаючи при цьому взаємне розташування символів у кожній з цих двох груп.