Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Сортировки слиянием

Читайте также:
  1. Алгоритм сортировки по возрастанию одномерного массива
  2. Анализ данных на основе их сортировки.
  3. Задачи сортировки. Сортировка методом парных перестановок
  4. Простые сортировки
  5. Сетевой маркетинг - это бизнес сортировки
  6. сортировки пораженных (больных) в условиях чрезвычайной ситуации
  7. сортировки элементов массива методом выбора
  8. Социальные институты и их трансформация под слиянием глобализации.
  9. Условия сортировки

Лекция 15

 

 

Эта группа сортировок не подвержена вырождению. Скорость работы практически такая же, как у сортировки Хоара. Есть некоторый недостаток: для хранения сортируемых массивов требуется вдвое больше памяти, чем у сортировки Хоара.

Элементы, требующие упорядочения (по возрастанию) занимают в массиве A, как и прежде, места с 1-е по nMax-е. Следующие nMax мест зарезервированы под временное хранение данных.

 


Сортировка простым слиянием

 

Идея сортировки состоит в следующем.

Сортируемый массив из элементов делится пополам (ясно, что это имеет смысл при ). Каждая из его половин сортируется, затем две отсортированные половины «сливаются», образуя отсортированное целое.

Фрагмент процедуры, выполняющей такую сортировку, может выглядеть так:

 

i:=1; // Место, с которого начинается левая половина

q:= (n+1) div 2;

j:=q+1; // Место, с которого начинается правая половина

k:= nCurr; // Место, после которого временно помещается «слитый массив»

 

СортировкаЛевойПоловины;

СортировкаПравойПоловины;

 

 

while (i<=q) and (j<=n) do

// Цикл выполняется, пока обе половины ещё не иссякли

Begin

Inc(k);




Дата добавления: 2015-04-26; просмотров: 11 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Сase X of| IfA[i]<A[j] then

lektsii.net - Лекции.Нет - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав