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

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

Сортировка с помощью прямого включения (МПВ)

Читайте также:
  1. A) Плавно или с помощью кнопок- строки заголовка.
  2. Lt;variant>возлагается. Эта обязанность состоит в том, что обвиняемому дозволяется обратиться за юридической помощью
  3. quot;Определение показателя преломления и концентрации растворов с помощью рефрактометра".
  4. А в это время в Китае остановили попытку распыления новой формы гриппа с помощью авиации.
  5. Алгоритм поиска с возвращением, их реализация с помощью рекурсий и динамических структур.
  6. Анализ простых категорических силлогизмов с помощью круговых схем
  7. Антикоагулянты непрямого действия
  8. Б 1)Техносфера-это (5-я об-ка биос-ы) нижняя часть биосф-ры преобр-я чел-ом с помощью тех-х средств в целях наилуч-го соотв-я соц-но-эконом-м потр-м общества.
  9. Быстрая сортировка Хоара
  10. Ввод данных с помощью списка

Элементы массива мысленно делятся на 2 последовательности: "готовую" - которая стоит в слева и все элементы которой упорядочены, и "исходную" - состоит из неупорядоченных элементов исходного массива. На каждом шаге i, начиная с i=2, из исходной последовательности извлекается i-ый элемент и перекладывается в нужное место готовой последовательности путем сравнения с ее элементами.

Максимальное число сравнений: C = n-1

Минимальное число сравнений: C = 1

Среднее число сравнений: C = i/2

Среднее число пересылок: M = C + 2

 

Пример:

 

Исх.послед. 55 44 12 42 94 18 06 67

i=2 44 55 12 42 94 18 06 67

i=3 12 44 55 42 94 18 06 67

i=4 12 42 44 55 94 18 06 67

i=5 12 42 44 55 94 18 06 67

i=6 12 18 42 44 55 94 06 67

i=7 06 12 18 42 44 55 94 67

i=8 06 12 18 42 44 55 67 94

Сортировка с помощью прямого выбора

Пусть имеется массив An, где n - количество элементов в массиве. Сначала выбирается элемент с наименьшим значением и меняется местами с элементом A1. Этот процесс затем осуществляется с отставшимися n-1 элементами, n-2 элементами и так до тех пор пока не останется один самый больший элемент.

 

Число сравнений: C = (n2 - n)/2

Число перестановок: Mmin = 3 * (n-1)

Mmax = n2/4 + 3 * (n-1)

 

Пример:

 

Исх.послед. 55 44 12 42 94 18 06 67

06 44 12 42 94 18 55 67

06 12 44 42 94 18 55 67

06 12 18 42 94 44 55 67

06 12 18 42 94 44 55 67

06 12 18 42 44 94 55 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 67 94

Сортировка с помощью прямого обмена (Пузырьковая сортировка)

Идея данной сортировки основана на парном сравнение соседних элементов в массиве и перестановке их в требуемом порядке: процесс продолжается до полного упорядочения всех элементов.

 

Пример:

 

Исх.послед. 19 13 05 27 01 26 31 16 02 09 11 21

i = 1 13 05 19 01 26 27 16 02 09 11 21 31

i = 2 05 13 01 19 26 16 02 09 11 21 27 31

i = 3 05 01 13 19 16 02 09 11 21 26 27 31

i = 4 01 05 13 16 02 09 11 19 21 26 27 31

i = 5 01 05 13 02 09 11 16 19 21 26 27 31

i = 6 01 05 02 09 11 13 16 19 21 26 27 31

i = 7 01 02 05 09 11 13 16 19 21 26 27 31

 

Как видно из примера, после 1-го прохода самый больной элемент перемещается в конец массива, соответственно при 2-ом проходе данный элемент можно исключить из просмотра, что существенно сократит время сортировки.

Шейкерная сортировка

Данный метод является видоизменением метода прямого обмена, при нем происходит чередование просмотров, то есть изменения их направления: сначала слева - направо, затем справа - налево и т.д. Этот способ дает уменьшение числа сравнений по сравнению с методом прямого обмена.

Сортировка методом Шелла

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

этом:

di = (di-1 + 1) / 2

 

При просмотре каждое значение сравнивается со значением, расположенным на d позиции дальше в векторе величин. Если верхнее значение больше нижнего значения, то делается перестановка и т.д.

 

Пример:

 

исх. массив Просмотры
       
d=6 d=3 d=2 d=1
    09 x 02 x 01 x
    01 x   02 x
  02 x   09 x 05 x
  09 x 19 x 05 x 09 x
    11 xx    
  21 x 05 x 13 xx  
    27 x 16 xx  
    13 xx 19 x  
  05 x 21 x 21 xxx  
    31 x 26 x  
    16 x 27 x  
  26 x   31 xx  

 

Обозначения: x - обмен, хх - двойной обмен, ххх - тройной обмен




Дата добавления: 2014-12-15; просмотров: 28 | Поможем написать вашу работу | Нарушение авторских прав




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