4549

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

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

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

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

Русский

2012-11-22

112.5 KB

153 чел.

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

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

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

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


 

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

38516. Створення культурно розважального сайту міста Хмельницького 3.73 MB
  Виходячи з даних проблем у роботі даного вебсайту має бути розроблений сайт про культурно розважальне життя міста Хмельницького з усіма його подіями розважальними закладами та коротким описом. В ході дипломногопроетування було створено вебсай за допомогою якого користувачі можуть переглядати різні заклади для відпочинку а також різноманітні розважальні заходи що відбудуться у цих закладах чи інші події у місті Хмельницькому 1 Характеристика предметної області. Розглянемо похожі вебсайти на наявність переваг та недоліків.
38517. Раскрытие юридического механизма действия уголовно-правовой нормы об убийстве, совершенном при превышении пределов необходимой обороны 467 KB
  Равно как и тесно связанный с ним являющийся как бы его частью институт превышения пределов необходимой обороны.37 УК РФ не является преступлением причинение вреда посягающему лицу при защите личности и прав обороняющегося или других лиц интересов общества или государства от общественно опасного посягательства если при этом не допущено превышения пределов необходимой обороны. Стало быть превышение пределов необходимой обороны действие преступное.
38518. Общие сведения работы на предприятии, санитарно-технические требования и пошаговое приготовление блюд (Борщ и куриные котлеты на косточке) 845 KB
  Исторически борщ — это национальное блюдо Древнего Рима, где специально для него выращивали много капусты и свеклы. Из Рима этот прекрасный суп постепенно проник в кулинарии многих народов мира, в каждой из них приобретая свои особенные национальные черты.
38519. Разработка базы данных «Кредитование клиентов» 430 KB
  Одной из постоянных проблем персональных компьютеров является нехватка памяти. Как правило, персональный компьютер мы используем в ежедневной работе, учебе, отдыхе, играх. Поэтому очень важно, чтобы ваш ПК имел достаточное количество памяти для хранения различного рода информации
38520. Разработка дизайн-проекта актового зала ГБОУ СПО (ССУЗ) «Златоустовский Металлургический колледж» а с учетом эргономических требований 20.98 MB
  Сначала роль электрической лампочки выполняли обычные свечи рисунок 1 позже им на смену пришел керосин рисунок 2 потом появились газовые фонари рисунок 3. Рисунок 1 Свеча Рисунок 2 Керосиновая лампа Рисунок 3 Газовый фонарь Кованые фонари издавна использовались не только как средство освещения улицы или помещения но и как красивое украшение. Рисунок 4 Кованый фонарь Рисунок 5 Кованые фонари Рисунок 6 ...
38522. Технологічний процес виробництва НАД (нікотинамідаденіндинуклеотиду) 1.51 MB
  Складено аналітичний огляд літератури щодо властивостей сучасних лікарських форм та галузей застосування коферментів. завдяки сучасним біотехнологіям отримало надзвичайні можливості щодо вирішення соціальних проблем повязаних з харчуванням зростаючого населення планети підтримкою здоровя людини і навколишнього середовища поповненням джерел енергії та природних ресурсів [1]. Стан біотехнологічної галузі потребує великої уваги з боку держави тому що роль сучасної біотехнології є вирішальною для становлення економіки...
38523. РИСК И ПРИ ОПЕРАЦИЯХ С НЕДВИЖИМЫМ ИМУЩЕСТВОМ 128.5 KB
  1 РИСК И ПРИ ОПЕРАЦИЯХ С НЕДВИЖИМЫМ ИМУЩЕСТВОМ В операциях с недвижимостью риск может проявляться в более низкой чем планировалось ранее цене при продаже недвижимости; в более высоком чем предполагалось уровне операционных расходов при управлении недвижимости; в снижении фактической рентабельности инвестиционного проекта по сравнению с проектной и даже в утрате собственности как в связи с разрушением самого тела недвижимости так и по причине потери прав на недвижимость. Целесообразно рассмотреть общую классификацию рисков...
38524. Електропостачання виробничого цеху деревообробного комбінату ТОВАРИСТВА «ДНІПРОВУД» 1.77 MB
  Потужність двигунів коливається від 55 до 37 кВт. При напрузі розподільної мережі 10 кВ двигуни середньої потужності 3501000 кВт потрібно використовувати на напругу 6 кВ з використанням в необхідних випадках схеми блоку трансформатордвигун при невеликій кількості двигунів на 6 кВ.1 Відомість електричних приймачів цеху Номер на плані Найменування електроприймачів Кількість Рн кВт соsφ tgφ Кв 1 Верстат багатопильний 1 37 065 117 017 28 Лінія форматної обробки 2 55 05 17 014 3 Лінія для вирізання сучків 1 66 06 13 016 4...