Сортировка простыми вставками.




Практическая работа № 2. Реализация сортировки в массиве.

 

Объём учебного времени – 2ч

 

Методические рекомендации

1. Цель работы: Научиться применять алгоритмы сортировки массивов

2. Перечень необходимых средств обучения:

 

2.1 Технические средства обучения:

Компьютер Core i3 3.0, 2 Gb оперативной памяти, винчестер 250 Gb, DVD

2.2 Программное обеспечение:

- Программа ОС Windows XP/7;

- Антивирусные программы: Kaspersky AntiVirus;

- Браузер Internet Explorer;

- Интегрированная среда программирования MS Visual Studio 2010.

3. Основные теоретические положения:

Методы простой сортировки

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

Сортировка простым выбором.

Рассмотрим идею на примере. Пусть исходный массив А состоит из 10 элементов: 5 13 7 9 1 8 16 4 10 2. После сортировки массив должен выглядеть так: 1 2 4 5 7 8 9 10 13 16.

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

Количество сравнений. При первом просмотре N-1, при втором – N-2, при последнем – 1. Общее количество С=N-1+N-2+1= N* (N-1)/2 (сумма элементов арифметической прогрессии) или C=O (N2).

Сортировка простым обменом.

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

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

 

I=1 5 4 8 2 9

> меняем

I=2 4 5 8 2 9

< не меняем

I=3 4 5 8 2 9

> меняем

I=4 4 5 2 8 9

< не меняем

9 находится на своем месте.

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

I=1 4 5 2 8 9

< не меняем

I=2 4 5 2 8 9

> меняем

I=3 4 2 5 8 9

< не меняем

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

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

I=1 4 2 5 8 9

> меняем

I=2 2 4 5 8 9

< не меняем

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

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

I=1 2 4 5 8 9

< не меняем

4 – на своем месте. Наименьший элемент – 2 оказывается на первом месте. Количество просмотров элементов массива равно N-1.

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

При сортировке методом «пузырька» выполняется N-1 просмотров, на каждом i-просмотре производится N-I сравнений. Общее количество С равно N* (N-1)/2, или O (N2).

Сортировка простыми вставками.

Сортировка этим методом производится последовательно шаг за шагом. На i-ом шаге считается, что часть массива, содержащая первые i-1 элементов, уже упорядочена, то есть A[1]≤A[2]≤…≤A[i-1]. Далее берется i-й элемент, и для него подбирается место в отсортированной части массива, такое, что после его вставки упорядоченность не нарушается, то есть требуется найти такое j (0≤j≤i-1), что A[j]≤A[i]<A[j+1] (при j=0 происходит только одно сравнение, если не использовать «барьерную» технику). Затем выполняется вставка элемента A[i] на место j. На каждом шаге отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить N-1 шаг.

Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию.

 

1-й шаг.     2-й шаг.     3-й шаг.     4-й шаг.     5-й шаг.     6-й шаг.   7-й шаг.   8-й шаг.   9-й шаг. 13 6 8 11 3 1 5 9 15 7     6 13 8 11 3 1 5 9 15 7     6 8 13 11 3 1 5 9 15 7     6 8 11 13 3 1 5 9 15 7     3 6 8 11 13 1 5 9 15 7     1 3 6 8 11 13 5 9 15 7   1 3 5 6 8 11 13 9 15 7   1 3 5 6 8 9 11 13 15 7   1 3 5 6 8 9 11 13 15 7     1 3 5 6 7 8 9 11 13 15 Рассматриваем часть массива из одного элемента 13. Вставляем второй элемент массива 6 так, чтобы упорядоченность сохранилась. Так как 6<13, записываем 6 на первое место. Отсортированная часть массива содержит два элемента (6 13).   Возьмем третий элемент массива 8 и подберем для него место в упорядоченной части массива. 8>6 и 8<13, следовательно, его место второе.   Следующий элемент – 11. Он записывается в упорядоченную часть массива на третье место, так как 11>8, но 11<13.   Далее, действуя аналогичным образом, определяем, что 3 необходимо записать на первое место. По той же причине 1 записываем на первое место.   Так как 5>3, но 5<6, то место 5 в упорядоченной части – третье.   Место числа 9 – шестое.   Определяем место для предпоследнего элемента 15. оказывается, что этот элемент массива уже находится на своем месте.   Осталось подобрать подходящее место для последнего элемента 7.   Массив отсортирован полностью.

 

Оценим эффективность метода. Для массива, например, 1 2 3 4 5 6 7 8 потребуется N-1 сравнение (напомним, что мы сортируем в порядке возрастания), а для массива 8 7 6 5 4 3 2 1 – N*(N-1)/2 или C=O (N2).

Сортировка подсчетом. Пусть дан массив (А) из 10 элементов: 10, 5, 11, -5, 1, -4, 13, 12, -4, 13. Возьмем первый элемент, он больше пяти элементов. Запишем 5 в дополнительный массив счетчиков (Count). Выполним эту операцию для всех элементов массива А. В массиве Count имеем: 5, 4, 6, 0, 3, 1, 8, 7, 2, 9. Если разрешается использовать дополнительный массив для хранения отсортированных данных, то остается переписать каждый элемент исходного массива на соответствующее место в результирующем массиве (В).



Поделиться:




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

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2018-12-19 Нарушение авторских прав и Нарушение персональных данных


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