4549

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

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

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

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

Русский

2012-11-22

112.5 KB

127 чел.

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

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

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

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


 

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

34949. Полезность, предельная полезность и их функции 57 KB
  Полезность можно разделить на объективную и субъективную. Полезность блага тем выше чем большему числу потребителей оно служит чем настоятельнее и распространённее эти потребности и чем лучше и полнее оно их удовлетворяет. Полезность является необходимым условием для того чтобы какойнибудь предмет приобрёл меновую ценность.
34950. Понятие издержек производства, производственная функция 41.5 KB
  Естественно что минимальный объем совокупных затрат меняется в зависимости от объема производства Q. Однако составляющие совокупных затрат поразному реагируют на изменение объема производства.
34951. Понятие основных и оборотных средств на предприятии 44.5 KB
  Оборотными средствами называется постоянно находящаяся в непрерывном движении совокупность производственных оборотных фондов и фондов обращения. Следующая таблица отражает структуру основных и оборотных средств: Производственные фонды Фонды обращения Основные Оборотные Средства труда Предметы труда Рабочая сила Готовая продукция Денежные средства Дебиторская задолженность Пассивные Активные Сырье топливо энергия материалы Здания земля Машины оборудование Основные фонды Оборотные средства.
34952. Понятие предпринимательства и его этапы становления в России 39.5 KB
  Этапы предпринимательства: Зарождение предпринимательства В конце 9 века помимо товарообмена появились денежные отношения. С 16 века в Московской Руси начинается рассвет торговопромышленного предпринимательства. Эпоха Петра как стремительное развитие предпринимательства Эпоха Петра 1 в начале 18 века.
34953. Понятие собственности и ее формы 41 KB
  Собственность как экономическая категория есть отношение между людьми по поводу материальной основы хозяйственной деятельности т. В этом плане собственность тесно связана с экономической властью с управлением производством с повседневными отношениями между людьми. Формы: Индивидуальная собственность.
34954. Понятие эластичности. Прямая и перекрестная эластичности спроса 43 KB
  Прямая и перекрестная эластичности спроса. Эласти́чность численная характеристика изменения одного показателя например:спроса или предложения к другому показателю например: цене доходу и показывающая на сколько процентов изменится первый показатель при изменении второго на 1. Товары с эластичным спросом по цене: Предметы роскоши драгоценности деликатесы Товары стоимость которых ощутима для семейного бюджета мебель бытовая техника Легкозаменяемые товары мясо фрукты Товары с неэластичным спросом по цене: Предметы первой...
34955. Понятие эластичности. Эластичность спроса по доходу и прямая ценовая эластичность 44 KB
  Эластичность спроса по доходу и прямая ценовая эластичность. Эласти́чность численная характеристика изменения одного показателя например:спроса или предложения к другому показателю например: цене доходу и показывающая на сколько процентов изменится первый показатель при изменении второго на 1. Товары с эластичным спросом по цене: Предметы роскоши драгоценности деликатесы Товары стоимость которых ощутима для семейного бюджета мебель бытовая техника Легкозаменяемые товары мясо фрукты Товары с неэластичным спросом по цене:...
34956. Понятие, показатели и цели экономического роста 50 KB
  Краткосрочные колебания выпуска в научной литературе обычно относятся к теории деловых циклов и не являются предметом изучения для теории экономического роста. В отличие от экономического развития экономический рост количественный показатель. Изучение экономического роста проходит в рамках теорий экономического роста Общепринятой количественной мерой экономического роста являются показатели абсолютного прироста или темпов прироста реального объема выпуска в целом или на душу населения: где t индекс времени.
34957. Понятия и задачи экономической теории 31.5 KB
  Экономическая теория не стоит на месте и её развитием в исторической перспективе занимается история экономических учений. Экономическая теория состоит из ряда разделов: методологии экономической науки микроэкономики макроэкономики международной экономики эконометрики теории игр. Экономическая теория создана и развивается экономистами различных школ и направлений поэтому ее определения различны.