Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм УлПир


Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

Пример результата просеивания

 

Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).

 

Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):

 

7 5

4 9 8 12

11 2 10 3 6

 

 

После первых трех просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):

 

7 5

4 9 8 12

11 2 10 3 6

 

 

7 5

11 10 9 8 12

11 2 9 10 3 6

 

 

7 5

11 4 10 8 12

4 11 2 9 3 6

 

 

Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов - для каждого из них будет достаточно только одного шага:

7 12 5

11 10 8 5 12

4 2 9 3 6

 

 

11 7 5

7 11 10 8 12

4 2 9 3 6

 

 

А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:

12 1

11 1 12

7 1 10 8 5

4 2 9 3 6

 

 

11 8 1

7 10 1 8 5

4 2 9 3 6

 

 

11 8

7 10 6 1 5

4 2 9 3 1 6

 

 

Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".

 

 

Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:

 

0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).

 

1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:

поменять местами очередной "рабочий" элемент с первым;

просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).

 

<== предыдущая лекция | следующая лекция ==>
Просеивание | Реализация алгоритма УлПир

Дата добавления: 2013-12-13; Просмотров: 160; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.017 сек.