Лабораторная работа №2 По дисциплине: Структуры и алгоритмы обработки данных



Скачать 117,5 Kb.
страница1/3
Дата27.05.2022
Размер117,5 Kb.
#184880
ТипЛабораторная работа
  1   2   3
Связанные:
ЛР2-Отчет
ЛР1-Отчет

Федеральное агентство связи

Сибирский Государственный Университет Телекоммуникаций и Информатики




Межрегиональный центр переподготовки специалистов

Лабораторная работа №2



По дисциплине: Структуры и алгоритмы обработки данных


Выполнил:


Группа:


Проверил: Мачикина Е.П.

Новосибирск, 2017 г


Лабораторная работа № 2
Быстрые методы сортировки массивов.
Цель работы: Освоить быстрые методы сортировки массивов.
Порядок выполнения работы:

  1. Разработать подпрограммы сортировки массива целых чисел методом Шелла и методом пирамидальной сортировки (или методом Хоара). Проверить правильность сортировки.

  2. Исследовать трудоемкость метода Шелла для n =10, 100, …, 500, n – количество элементов в массиве. Определить последовательность шагов для предварительных сортировок по формуле Кнута. Построить таблицу и проанализировать полученные результаты:

Длина массива

Количество шагов по формуле Кнута

Последовательность шагов по формуле Кнута

Мфф
Метод Шелла















  1. Составить таблицу следующего вида (данные получить экспериментально) для n=100, 200, 300, 400, 500. (n – количество элементов в массиве)

    Размер массива

    Мфф м. Шелла

    Мфф пирам. (м. Хоара)

    Убыв.

    Случ.

    Возр.

    Убыв.

    Случ.

    Возр.

    100



















    200



















    300



















    400



















    500



















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

Описание основных методов используемых в лабораторной работе:

  1. Метод Шелла разработан на базе метода прямого включения. Он обеспечивает значительную производительность сортировки. В методе прямого включения, чем больше упорядочен массив, тем меньше операций требуется для его сортировки. При сортировке уже упорядоченного массива трудоемкость имеет линейный порядок. Поэтому имеет смысл попытаться предварительно несколько улучшить порядок элементов в массиве, а затем отсортировать массив методом прямого включения. Предварительное упорядочивание будем проводить с помощью k – сортировок. Суть k – сортировки заключается в следующем. Массив разбивается на последовательности с шагом k (ai, ak+i, a2k+i, …,a[n/k]k+i, i = 1, 2,…,k) и сортировка происходит только внутри этих последовательностей. Обозначим через H последовательность из m возрастающих шагов H=(h1, h2, … hm), где h1=1, h1 < h2 < h3 < … < hm. Метод Шелла состоит в последовательном проведении hi-сортировки, i=m, m-1,…, 1, причем h1=1 гарантирует, что массив будет полностью отсортирован, поскольку 1-сортировка является методом прямого включения

Алгоритм на псевдокоде:
DO (k=hm, hm-1, … 1)
DO (i=k+1, k+2, … n)
t: = ai, j: =i-k
DO (j>0 и t < aj)
aj+k: = aj
j: = j-k
OD
aj+k: = t
OD
OD
Эффективность метода зависит от выбора значений шагов. Последовательность значений шагов, которая дает наилучшую трудоемкость, пока неизвестна, метод продолжает исследоваться, но существует и часто используется следующая последовательность шагов, предложенная Кнутом. h1=1, hi=2hi-1+1, i=2,… m, m=⌊log2n⌋-1

  1. Метод Хоара или метод быстрой сортировки заключается в следующем. Возьмём произвольный элемент массива х. Просматривая массив слева, найдём элемент aix. Просматривая массив справа, найдём ajx. Поменяем местами ai и aj . Будем продолжать процесс просмотра и обмена, до тех пор пока i не станет больше j. Тогда массив можно разбить на две части: в левой части все элементы не больше х, в правой части массива не меньше х. Затем к каждой части массива применяется тот же алгоритм.

Алгоритм на псевдокоде:
Сортировка части массива с границами (L, R).
Обозначим:

  • L - левая граница рабочей части массива

  • R - правая граница рабочей части массива

х:=аL, i:=L, j:=R


DО (i≤j)
DО (ai DО (aj>x) j:=j-1 OD
IF (i<=j)
ai↔ aj,, i:=i+1, j:=j-1
FI
OD
IF (L<Сортировка части массива с границами (L,j)>
FI
IF (i<Сортировка части массива с границами (i,R)>
FI

Скачать 117,5 Kb.

Поделитесь с Вашими друзьями:
  1   2   3




База данных защищена авторским правом ©psihdocs.ru 2022
обратиться к администрации

    Главная страница