Лабораторная работа №1в. Сортировка методом прямого включения

Лабораторная работа №1 . Методи сортування.

Лабораторная работа №1 а . Сортировка методом простого выбора

Цель работы: Исследовать сортировку массива методом простого выбора и оценить эффективность этого алгоритма.

Общие сведения

Сортировка методом простого выбора сводится к следующим шагам:
1. Установить номер наибольшего элемента массива.
2. Поменять местами наибольший и последний элементы массива.
3. Оставив в покое последний элемент, выполнить пункты 1 и 2 над остатком массива (массивом без последнего элемента). Пункт 3 повторять, пока остаток массива не сократится до одного элемента.

Пример

Опишем процедуру сортировки на языке проектирования программ (псевдокоде).

For i := n downto 2 do

Begin

найти максимальный элемент из а[1], ..., a[i];

запомнить его индекс в переменной k;

если i<>k поменять местами a[i] и a[k];

End;

Вот как изменяется значение массива из пяти элементов (30,20,10,50,40)

30 20 10 50 40

30 20 10 40 50

10 20 30 40 50

Подчеркнута область поиска наибольшего элемента.

Контрольные вопросы

1. Что понимается под сортировкой массива?

2. Чем отличается сортировка по убыванию от сортировки по невозрастанию?

3. Сформулировать идею сортировки массива методом простого выбора.

4. Почему время выполнения одного шага прямо пропорционально размеру неупорядоченной части массива?

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

ВНИМАНИЕ!!! Входные данные (исходный массив) и выходные данные (отсортированный массив) формировать в виде текстового файла, содержащего целые числа!

1. Изменить процедуру сортировки так, чтобы сортировка производилась по убыванию элементов.

2. Проверить, является ли данная последовательность целых чисел упорядоченной по убыванию. Если нет, упорядочить ее.

3. Отсортировать данный массив и подсчитать количество уникальных чисел в массиве.

4. Изменить процедуру сортировки так, чтобы значение параметра k с каждым шагом увеличивалось.

5. Отсортировать четные элементы массива с помощью простого выбора.

6. Отсортировать с помощью простого выбора элементы массива, стоящие на нечетных местах.

7. В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить).

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

9. В матрице n*m отсортируйте столбцы в порядке возрастания элементов k строки.

10. Даны список футбольных команд высшей лиги России и количество очков, набранных каждой командой в чемпионате России. Известно, что нет команд с равным числом очков. Распечатать список призеров.

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

12. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный так же, как исходные массивы.

13. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный в обратную сторону.

14. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по убыванию элементов последней строки. Вычислить сумму элементов расположенных на диагоналях полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы.

Лабораторная работа №1б. Сортировка методом простого обмена

Цель работы:

Исследовать сортировку массива методом простого обмена и оценить эффективность этого алгоритма.

Общие сведения

Как и предыдущий, этот алгоритм состоит из отдельных шагов. На каждом шаге проходят массив от начала к концу, сравнивая пары соседних элементов. Если очередная пара нарушает требуемый порядок, ее элементы меняют местами. Шаги повторяют до тех пор, пока очередной проход не вызовет ни одного обмена.

Пример

Отсортируем по возрастанию методом простого обмена массив из 5 элементов: 5 1 8 4 9. Длина текущей части массива – n-k+i, где k – номер просмотра, i – номер проверяемой пары, п - k – номер последней пары. За вертикальной чертой располагаются отсортированные элементы.

Первый просмотр: рассматривается весь массив.

i = l5 4 8 2 9

> меняем

i = 24 5 8 2 9

< не меняем

i = 34 5 8 2 9

> меняем

i = 44 5 2 8 9

< не меняем

9 стоит на своем месте.

Второй просмотр: рассматриваем часть массива с первого до четвертого элемента.

i = 14 5 2 8 9

< не меняем

i = 24 5 2 8 9

> меняем

i = 34 2 5 8 9

< не меняем

8 стоит на своем месте.

Третий просмотр: рассматриваемая часть массива содержит первые три элемента.

i = 14 2 5 8 9

> меняем

i = 22 4 5 8 9

< не меняем

5 стоит на своем месте.

Четвертый просмотр: рассматриваем последнюю пару.

i = 12 4 5 8 9

< не меняем

4 стоит на своем месте.

Для самого маленького элемента (2) остается только одно место – первое.

Итак, наш массив отсортирован по возрастанию элементов методом простого обмена. Этот метод также называют методом «пузырька». Название это происходит от образной интерпретации, при которой в процессе выполнения сортировки более «легкие» элементы (элементы с заданным свойством) мало-помалу всплывают на «поверхность».

Контрольные вопросы

1. Как поменять местами два элемента массива?

2. Что такое вложенные циклы?

3. В чем сходство и отличие методов простого выбора и простого обмена?

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

1. Изменить процедуру сортировки так, чтобы сортировка производилась по убыванию элементов.

3. Отсортировать данный массив и подсчитать количество уникальных чисел в массиве.

4. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по убыванию элементов последней строки. Вычислить сумму элементов расположенных на диагоналях полученной матрицы. Сортировку произвести методом обмена. Вывести на экран исходный и полученный массивы в виде матрицы.

5. Отсортировать четные элементы массива с помощью простого обмена.

6. Отсортировать с помощью простого обмена элементы массива, стоящие на нечетных местах.

9. В матрице n*m отсортируйте столбцы в порядке возрастания элементов k строки.

14. Изменить процедуру сортировки так, чтобы значение параметра k с каждым шагом увеличивалось.

Лабораторная работа №1в. Сортировка методом прямого включения

Цель работы

Исследовать сортировку массива методом прямого включения и оценить эффективность этого алгоритма.

Общие сведения

Сортировка методом прямого включения, так же, как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов.

Сортировка этим методом производится последовательно шаг за шагом. На k-м шаге считается, что часть массива, содержащая первые k-1 элемент уже упорядочена, то есть . Далее необходимо взять k-й элемент и подобрать для него место в отсортированной части массива такое, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое что . Затем надо вставить элемент a[k] на найденное место.

С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг.

Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента х. Поступим следующим образом: будем просматривать элементы, расположенные левее х (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы а[j], j изменяется от k-l до 1. Такой просмотр закончится при выполнении одного из следующих условий:

• найден элемент а[j]<х, что говорит о необходимости вставки х между a[j-1] и a[j];

• достигнут левый конец упорядоченной части массива, следовательно, нужно вставить х на первое место.

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

Пример

Коротко опишем фрагмент алгоритма сортировки с помощью прямого включения:

For k := 2 to n do

begin

x := a[k]; j := k-1;

{ вставить х на подходящее место в a[1], …, a[k] }

{ для этого организуем цикл, которые выполняется, пока }

{ j > 0 и x <= a[j] }

{в цикле смещаем элементы массива на 1 позицию вправо }

{по выходу из цикла вставляем х в позицию j+1массива }

end;

Контрольное задание

Написать программу вставки последнего элемента массива после первого отрицательного элемента этого же массива.

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

ВНИМАНИЕ!!! Если явно не указано иное, входные данные (исходный массив) и выходные данные (отсортированный массив) формировать в виде текстового файла, содержащего целые числа!

Для всех заданий предварительно написать процедуру сортировки массива методом прямого включения.

1. Дан ряд, содержащий n элементов. Отсортировать их в порядке возрастания, отбрасывая при этом все повторяющиеся элементы.

2. Определить моду данного ряда – значение, встречающееся среди его элементов чаще всего.

3. Исходный набор данных представляет собой последовательность записей, состоящих из фамилии, возраста и стажа работы. Распечатать этот список: 1) в алфавитном порядке; 2) в порядке увеличения возраста; 3) в порядке увеличения стажа работы.

4. Написать процедуру сортировки по убыванию.

5. Дан ряд целых чисел. Получить в порядке возрастания все различные числа, входящие в этот ряд.

6. Дан ряд из n различных целых чисел. Получить различные целые числа такие, что

7. Даны целые Найти наибольшее значение в этой последовательности после выбрасывания из нее всех членов со значением

8. Даны натуральные Числа – это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 м. Составить команду из четырех лучших бегунов для участия в эстафете 4х100, т. е. указать одну из четверок натуральных чисел i, j, k, l такую, что сумма имеет наименьшее значение.

9. Дано n независимых случайных точек, с координатами (xi; yi), равномерно распределенных в круге радиуса 1 с центром в начале координат. Напишите программу, располагающую точки в порядке возрастания расстояния от центра.

10. Даны n целых положительных двузначных чисел. Трактуя каждое число как пару цифр из интервала 0–9, отсортировать их (цифры) по возрастанию.

11. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся замкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Подсказка. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи снизу вверх, а точки на одном луче упорядочим по расстоянию от начала луча (это делается для всех лучей, кроме нижнего и верхнего). Ломаная выходит из выбранной (самой левой) точки по нижнему лучу, затем по всем остальным лучам (в описанном порядке) и возвращается по верхнему лучу.

12. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на вбитые в доску гвозди - их выпуклая оболочка.) Указание. Упорядочим точки. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек.

Дата добавления: 2021-01-21; просмотров: 168; Мы поможем в написании вашей работы!

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

Мы поможем в написании ваших работ!