Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1327


2.8. алгоритмы сортировки одномерных массивов

 

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

НАЧАЛО

 

K=1;  М=1

 

Ввод N и А( 1.. N)

 

 

A [K]>A[M] [M]

+

M:=K

 

 

K:=K+1

 

+

K<=N

 

Вывод А[M]

 

КОНЕЦ

 

Рис. 18. Алгоритм поиска максимального значения в массиве

 

Сортировка модифицированным методом  простого выбора

 

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

Рассмотрим  алгоритмическое  решение  задачи  на  примере сортировки некоторого массива значений по возрастанию. В соответствии с  вышеописанным методом  необходимо  несколько  раз  выполнить операции поиска минимального элемента и его перестановку с другим элементом, то есть потребуется несколько раз просматривать элементы массива   с   этой   целью.   Количество   просмотров   элементов   массива, согласно описанию модифицированного метода простого выбора, равно

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

Обозначим через i счетчик (номер) просмотров элементов массива и изобразим обобщенный алгоритм сортировки на рис. 19.

Отметим,  что  для  перестановки  элементов  местами  необходимо знать их порядковые номера. Алгоритмы ввода исходного массива изображен на рис. 16. Алгоритм поиска в массиве минимального элемента и  его  номера  будет  аналогичен алгоритму примера 10,  который представлен на рис. 18.

Однако, в этом алгоритме будут внесены изменения. Для того, чтобы определить какие изменения следует внести, рассмотрим выполнение сортировки данным методом с акцентом на поиск минимального элемента на конкретном примере. Пусть исходный массив содержит 5 элементов (2,  8,  1,  3,  7).  Количество  просмотров,  согласно  модифицированному методу простого выбора, будет равно 4. Покажем в таблице 4, как будет изменяться исходный массив на каждом просмотре.

 

 

 

Пример сортировки

Таблица 4

 

 

Номер просмотра массива i

 

Исходный массив

Минимальный элемент

Переставляемый элемент

 

Массив после перестановки

Номер

Значение

Номер

Значение

1

(2,8,1,3,7)

3

1

1

2

(1,8,2,3,7)

2

1,(8,2,3,7)

3

2

2

8

1,(2,8,3,7)

3

1,2,(8,3,7)

4

3

3

8

1,2,(3,8,7)

4

1,2,3,(8,7)

5

7

4

8

1,2,3,7,8

НАЧАЛО

 

ВВОД А(1..n)

 

i = 1

 

ПОИСК НОМЕРА МИНИМАЛЬНОГО ЭЛЕМЕНТА

 

i=i+1

ПЕРЕСТАНОВКА МИНИМАЛЬНОГО ЭЛЕМЕНТА С i-м ЭЛЕМЕНТОМ

 

 

 

 

i = n-1

+

ВЫВОД А(1..n)

ПОСЛЕ СОРТИРОВКИ

 

КОНЕЦ

 

 

Рис. 19. Обобщенный алгоритм сортировки массива модифицированным методом простого выбора

 

Из данных, приведенных в таблице 4, следует, что поиск мини- мального значения в массиве на каждом просмотре   осуществляется в сокращенном массиве, который сначала  начинается с первого элемента, а на последнем просмотре массив, в котором ищется минимальный элемент, начинается уже с четвертого (или n–1) элемента. При этом можно заметить, что номер первого элемента массива для каждого поиска и перестановки совпадает с номером просмотра i.

Введем следующие обозначения:

К – номер минимального элемента, J – номер элемента массива,

М и А(К) – одно и тоже значение минимального элемента массива, i – номер переставляемого с минимальным элемента,

А(i) – значение переставляемого элемента.

Тогда циклический алгоритм сортировки модифицированным мето-

дом простого выбора будет выглядеть, как показано на рис. 20.

НАЧАЛО

 

ВВОД N,

A(N)

 

I := 1

 

M := A(I)

 

К := I

 

 

J := K + 1

А(К):=А(I)

 

 

 

 

A(J) <М

A(I ) := M

 

I := I + 1

+

 

M := A(J)

+

 

I   N – 1

 

 

К := J

 

 

J := J + 1

ВЫВОД N A(N)

 

 

+

J  N

 

КОНЕЦ

 

 

Рис. 20. Алгоритм сотрировки массива модифицированным методом простого выбора

Сортировка методом  парных перестановок

 

Самый простой вариант этого метода сортировки массива основан на принципе сравнения и обмена пары соседних элементов.

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

Если при просмотре элементов массива значение счетчика перестановок осталось равным нулю, то это означает, что все элементы отсортированы (см. рис. 21).

 

НАЧАЛО

 

ВВОД  N, A(N)

 

B:= 0

 

 

K := 1

K = 0   ВЫВОД

А(1..n)

 

 

A(K)             +

 A(K+1)

 

 

КОНЕЦ

 

 

Q := A(K), A(K) := A(K+1),

 

B := B + 1

 

K := K + 1

 

+

K  N

 

Рис. 21. Алгоритм сортировки методом парных перестановок