4549

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

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

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

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

Русский

2012-11-22

112.5 KB

124 чел.

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

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

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

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


 

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

44804. Правило минимума Либиха. Закон оптимума. Закон толерантности Шелфорда 38 KB
  Закон оптимума. Закон толерантности Шелфорда. Закон минимума Либиха закон открытый. Либихом 1840 согласно которому относительное действие отдельного экологического фактора тем сильнее чем больше он находится по сравнению с другими факторами в минимуме; по данному закону от вещества концентрация которого лежит в минимуме зависят рост растений величина и устойчивость их урожайности.
44805. Понятие популяции. Структура и динамика популяций 41 KB
  Свободно скрещивающихся и дающих плодовитое потомство Основные характеристики популяций: 1 численность– общее количество особей на выделяемой территории; 2 плотность популяции – среднее число особей на единицу площади или объема занимаемого популяцией пространства; плотность популяции можно выражать также через массу членов популяции в единице пространства; 3 рождаемость– число новых особей появившихся за единицу времени в результате размножения; 4 смертность – показатель отражающий количество погибших в популяции особей за...
44806. Потоки вещества и энергии в биологических сообществах. Продуценты, консументы, редуценты. Трофические цепи и трофические сети. Пирамиды численности и биомассы в сообществах 37.5 KB
  Энергия основа работы экосистемы основной источник энергии Солнце. Поток солнечной энергии протекает через фототрофные экосистем при передаче в пищевых трофических цепях происходит рассеивание в виде тепла Пищевая цепь сеть – последовательность организмов где каждый предыдущий пища для последующего. Из всей поступающей солнечной энергии растениями усваивается только 2 остальное расходуется на транспирацию отражается листьями идет на нагревание воздуха воды и почвы.
44807. Продуктивность экосистем. Первичная и вторичная продукция 18.66 KB
  Пример экосистемы пруд с обитающими в нём растениями рыбами беспозвоночными животными микроорганизмами составляющими живую компоненту системы биоценоз. Все живые компоненты экосистемы – продуценты консументы редуценты составляют общую биомассу живой вес. Для экосистемы океана пирамида биомассы имеет перевернутый вид т. Знание энергетики экосистемы и количественных ее показателей позволяют точно учесть возможность изъятия из природной экосистемы того или иного количества растительной и животной биомассы без подрыва ее эффективности.
44809. Тhe purpose of grammar as a linguistic discipline 25 KB
  Lаnguаge is mens of forming nd storing ides s reflections of relity nd exchnging them in the process of humn intercourse. Lnguge is socil by nture; Lnguge incorportes the three constituent prts sides ech being inherent in it by virtue of its socil nture. Only the unity of these three elements forms lnguge; without ny one of them there is no humn lnguge in the bove sense. The phonologicl system is the subfoundtion of lnguge; it determines the mteril phoneticl ppernce of its significtive units.
44810. Предмет, содержание и задачи экономического анализа 38.5 KB
  ЭА осуществляемый на уровне отдельной фирмы предприятия называется обычно анализом хозяйственной деятельности. Предмет любой науки – это часть или сторона объективной действительности которая изучается только данной наукой; это хозяйственные процессы предприятий объединений ассоциаций социально-экономическая эффективность и конечные финансовые результаты их деятельности складывающиеся под воздействием объективных и субъективных факторов получающие отражение через систему экономической информации. Как видно из определения ЭА имеет...
44811. Анализ школьных учебников и методической литературы по химии 21.71 KB
  Анализ школьных учебников и методической литературы по химии. B сложной системе обучения химии учебник занимает важное место. В нем присутствуют все структурные элементы которые присущи обучению химии в целом: содержание предмета химии методы обучения средства обучении и организация учебной деятельности учащегося. Межпредметные связи в преподавании химии.
44812. Модель. Моделирование баз 41 KB
  При предметном моделировании строят физическую модель которая соответствующим образом отражает основные физические свойства и характеристики моделируемого объекта при этом модель и реальный объект мотуг иметь разную физическую природу. Если же модель и объект одной и той же физической природы то моделирование будет физическим. Абстрактное моделирование связана с построением абстрактной модели которая представляет собой математические диаграммы и т.