4549

Быстрые методы сортировки массивов

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

Информатика, кибернетика и программирование

Быстрые методы сортировки массивов. Цель работы: Освоить быстрые методы сортировки массивов Порядок выполнения работы: Разработать процедуры сортировки массива целых чисел методом Шелла, методом пирамидальной сортировки и методом Хоара (язык п...

Русский

2012-11-22

112.5 KB

129 чел.

Быстрые методы сортировки массивов.

Цель работы: Освоить быстрые методы сортировки массивов

Порядок выполнения работы:

  1.  Разработать процедуры сортировки массива целых чисел методом Шелла, методом пирамидальной сортировки и методом Хоара (язык программирования Паскаль или Си).
  2.  Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве.
  3.  Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
  4.  Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)

  1.  Проанализировать полученные результаты. (Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?)
  2.  Сравните трудоемкости методов быстрой сортировки и трудоемкости методов с квадратичной трудоемкости (использовать результаты лабораторной работы 1)

В данном задании были использованы следующие методы:

Метод Шелла

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

Пирамидальная сортировка

Пирамидальная сортировка производится в два этапа. Сначала строится пирамида из элементов массива. По свойству (3) правая часть массива является (n/2+1, n)-пирамидой. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в неё не войдут все элементы массива. Тогда по свойству (2) первый элемент последовательности – минимальный.

Метод Хоара

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

Результат выполнения программы:

При сортировке методом шелла:

При n = 100, Mmin=2*(100-1)=198, Mmax=(1002-100)/2+2*100-2=5148, Cmin=99, Cmax=(3*(1002-100))/2=14580, Cср = 1002=10000;

При n = 200, Mmin=2*(200-1)=398, Mmax=(2002-200)/2+2*200-2=20298, Cmin=199, Cmax=(3*(2002-200))/2=59700, Cср = 2002=40000;

При n = 300, Mmin=2*(300-1)=598, Mmax=(3002-300)/2+2*300-2=45448, Cmin=299, Cmax=(3*(3002-300))/2=134550, Cср = 3002=90000;

При n = 400, Mmin=2*(400-1)=798, Mmax=(4002-400)/2+2*400-2=80598 Cmin=399, Cmax=(3*(4002-400))/2=239400, Cср = 4002=40000;

При n = 500,  Mmin=2*(500-1)=998, Mmax=(5002-500)/2-2*500-2=125748,  Cmin=499,  Cmax = 3*(5002-500)/2=125748, Cср = 5002=250000;

При сортировке методом пирамиды:

При n = 100, C = 100 log(100) = 664 , M=100 log(100) = 664;

При n = 200, C = 200 log(200) = 1528 , M=200 log(200) = 1528;

При n = 300, C = 300 log(300) = 2468 , M=300 log(300) = 2468;

При n = 400, C = 400 log(400) = 3457 , M=400 log(400) = 3457;

При n = 500, C = 500 log(500) = 4482 , M=500 log(500) = 4482;

При методе Шейкерной сортировки:

При n = 100, C = 100 log(100) = 664 , M=100 log(100) = 664;

При n = 200, C = 200 log(200) = 1528 , M=200 log(200) = 1528;

При n = 300, C = 300 log(300) = 2468 , M=300 log(300) = 2468;

При n = 400, C = 400 log(400) = 3457 , M=400 log(400) = 3457;

При n = 500, C = 500 log(500) = 4482 , M=500 log(500) = 4482;

n=100

Метод

М для упор

С для упор

М для случ.

С для случ..

Шелла

0

503

593

1095

Пирамиды

738

1576

683

1466

Хоара

0

810

159

1028

n=200

Метод

М для упор

С для упор

М для случ.

С для случ..

Шелла

0

1203

1891

3092

Пирамиды

1684

3568

1568

3336

Хоара

0

1889

349

2707

n=300

Метод

М для упор

С для упор

М для случ.

С для случ..

Шелла

0

2104

600

3486

Пирамиды

2700

5700

2513

5326

Хоара

0

2816

3392

5495

n=400

Метод

М для упор

С для упор

М для случ.

С для случ..

Шелла

0 

2803

8245

11044

Пирамиды

3780

7960

3498

7396

Хоара

0

15394

841

11653

n=500

Метод

М для упор

С для упор

М для случ.

С для случ..

Шелла

0

3506

1074

14576

Пирамиды

4844

10188

4579

9658

Хоара

0

19474

1119

12168

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


 

А также другие работы, которые могут Вас заинтересовать

36820. Определение уровня качества технических средств защиты информации 146.5 KB
  Цель работы Изучение методов определения показателей качества технических средств защиты информации и практическое определение их уровня качества с использованием комплексных показателей. Основные понятия термины и определения теории качества Технические средства защиты информации ТСЗИ в большинстве случаев представляют собой радиоэлектронные устройства РЭУ предназначенные для обнаружения и подавления прослушивающих устройств шифрования и кодирования информации защиты информации в возможных каналах утечки. Поэтому знание методов...
36821. ИЗУЧЕНИЕ РАВНОУСКОРЕННОГО ДВИЖЕНИЯ НА МАШИНЕ АТВУДА 101 KB
  ОТЧЁТ ПО ЛАБОРАТОРНОЙ РАБОТЕ № 1 ИЗУЧЕНИЕ РАВНОУСКОРЕННОГО ДВИЖЕНИЯ НА МАШИНЕ АТВУДА. В первом случае используя формулу пути при равноускоренном движении h=1t2 2 получим 1=2h t2 1 где пройденный грузами путь h и время движения t измеряются непосредственно. При втором способе формулу для определения ускорения на этом участке движения h получим из рассмотрения изменения энергии системы Ek= Где v линейная...
36822. Сведения о некоторых командах ОС UNIX. Сведения к лабораторной работе 115 KB
  ls поданная без параметров команда выводит список файлов и каталогов содержащихся в текущем каталоге. Например чтобы получить список файлов в каталоге usr sbin необходимо использовать команду ls usr sbin У команды ls есть множество ключей которые нужны главным образом для того чтобы выводить дополнительную информацию о файлах в каталоге или выводить указанный список файлов вместо указания имен файлов можно использовать шаблоны. ll выводит список всех имен файлов каталога включая скрытые А lmostll выводит список всех...
36823. Запуск Word. Выход из Word. Настройка пользовательского интерфейса. Открытие и сохранение документа 294 KB
  Выход из Word. Существует несколько способов запустить Microsoft Word для Windows 95. Если вы запускаете Word с помощью кнопки Пуск Windows 95 Word создает пустой незаполненный документ.
36825. Мировые информационные ресурсы 444 KB
  Задание №1 Сформируйте электронный глоссарий по тематике Мировые информационные ресурсы: Блог Веб страница Интернет ресурс Информационная культура Информационное общество Информационные взаимодействия Информационные ресурсы Информационные сети Информационные системы Информационный портал Информационный потенциал общества Информация Мировые информационные ресурсы Национальные информационные ресурсы Сайт Сервис Средства массовой информации Телеконференция Файловый сервер Чат Электронная база...
36826. Получить навыки работы с электронной таблицей Microsoft Excel 170 KB
  Откройте меню настройки панелей управления Вид Панели инструментов и убедитесь в том что включено отображение только двух панелей: Стандартная и Форматирование. Чтобы настроить масштаб отображения войдите в меню Вид Масштаб. Войдите в меню Сервис Параметры. Для этого достаточно воспользоваться командой меню Правка Отменить.
36827. МОДЕЛИРОВАНИЕ реакции с диффузией в трубчатом реакторе 862.5 KB
  Поэтому математическое описание процессов протекающих в этих реакторах имеет большое значение. Рассмотрим математическое описание трубчатого реактора для проведение реакции с диффузией. Этот поток входит в реактор где одновременно с диффузией осуществляется реакция первого порядка Длина реактора L площадь его поперечного сечения 1 м2. При условии что скорость питания w м3 ч концентрация М равна с0 а коэффициент диффузии М принимается постоянный со значением D м2 ч определить концентрацию М как функцию длины реактора.
36828. ПОВЕРКА МИКРОМЕТРА 227.5 KB
  Лабораторная работа № 2 ПОВЕРКА МИКРОМЕТРА Цель работы: изучить устройство и принцип действия микрометра; получить первичные практические навыки в выполнении поверки СИ осуществить поверку микрометра определить пригодность микрометра к использованию. Устройство и принцип действия микрометра Микрометр относится к классу микрометрических измерительных инструментов принцип действия которых основан на использовании винтовой пары винт гайка позволяющей преобразовать вращательное движение микровинта в поступательное. Устройство...