Составление алгоритмов решения задач с использованием методов внутренней сортировки

[stalin765]

ребята помогите
ТЕМА:

«Составление алгоритмов решения задач с использованием методов внутренней сортировки»

Контрольная работа
Тема:
«Составление алгоритмов решения задач с использованием методов внутренней сортировки»


Цель контрольной работы: изучить правила составления алгоритмов решения задач, составить алгоритмы решения аналитических и логических задач с использованием методов внутренней сортировки.


Методические рекомендации по контрольной работе:


1. СОРТИРОВКА МЕТОДОМ ВКЛЮЧЕНИЯ

Имеется последовательность элементов а0, а1, а2, ...,аn-1. Эта последовательность мысленно делится на две последовательнос*ти: упорядоченную последовательность а0, а1, ..., аi-1 и исход*ную, неупорядоченную аi, аi+1,..., аn-1. Очевидно, что первона*чально упорядоченная последовательность состоит из единствен*ного элемента а0. При каждом шаге, начиная с i = 1 и увеличивая i каждый раз на единицу, из исходной последовательности из*влекается i-й элемент аi, и вставляется в готовую последователь*ность в нужное место, при необходимости сдвигая элементы готовой последовательности на одну позицию вправо вплоть до i-й позиции. Поиск подходящего места осуществляется сравнени*ем аi, с элементами aj =i-1,i-2, ..., 0, и одновременным обме*ном местами аi, и аj, если , аi<aj, т.е. сдвигом aj на одну позицию вправо. Процесс поиска заканчивается при выполнении одного из условий:
аi> = aj;
достигнут левый конец готовой последовательности.
Этот метод обеспечивает устойчивую сортировку.

2. СОРТИРОВКА МЕТОДОМ ВЫБОРА

Алгоритм сортировки заключается в следующем:
В исходной последовательности из п элементов отыскива*ется элемент с наименьшим ключом.
Он меняется местами с первым элементом.
В оставшейся последовательности из (п - 1) элементов отыс*кивается минимальный элемент и меняется местами со вторым элементом и т.д., пока не останется один, самый большой эле*мент.
Отсюда алгоритм с прямым выбором несколько предпочти*тельней алгоритма прямого включения. Однако если ключи вна*чале почти упорядочены, то прямое включение будет несколько быстрее.

3. СОРТИРОВКА МЕТОДОМ ОБМЕНА (МЕТОДОМ ПУЗЫРЬКА)

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

Шейкерная сортировка.

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



Практическая часть

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


№ вар Число 1 Число 2 Число 3 Число 4 Число 5 Число 6 Число 7 Число 8
1 37 25 111 4 16 85 32 9
2 56 74 3 19 2 45 54 76
3 24 46 100 41 37 85 83 38
4 15 18 81 94 38 47 86 90
5 46 75 98 12 15 53 87 78
6 47 76 85 98 58 32 14 7
7 47 78 95 78 47 74 79 69
8 76 92 3 67 84 65 58 46
9 37 87 95 60 63 69 4 6
10 4 8 3 2 7 5 6 1
11 12 21 13 31 15 51 16 61
12 21 31 12 13 67 76 87 86
13 34 12 36 48 85 92 32 1
14 16 27 73 82 15 17 51 50