36546

Алгоритмы обработки одномерных массивов.Сортировка.Сравнить 2 метода

Доклад

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

Первый шаг сортировки методом пузырька 1Сравниваем первый и второй элементы массива. 2Сравниваем второй и третий элементы массива. 3Cравниваем предпоследний N1 и последний N элементы массива. Повторяем вышеуказанные действия для части массива начиная с 1 позиции до N1 шаг 2.

Русский

2013-09-22

30 KB

2 чел.

Алгоритмы обработки одномерных массивов.Сортировка.Сравнить 2 метода

Метод пызырька.

Основная идея сортировки (например, по возрастанию) методом пузырька очень простая. Предположим, что у нас N элементов в массиве и индекс каждого элемента лежит в промежутке от 1 до N.

Первый шаг сортировки методом пузырька

1)Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.

2)Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.

3)Cравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами.

В результате самым последним элементом в массиве у нас окажется самый большой элемент.

Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1 (шаг 2).

Второй шаг сортировки методом пузырька

1(Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.

2(Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местам

3)Cравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами.

В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.

Метод включения

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

Легко видеть, что в лучшем случае (когда массив уже упорядочен) для выполнения алгоритма с массивом из n элементов потребуется n-1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n?(n-1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n2).

Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием. Мы не будем описывать алгоритм в общем виде, а ограничимся случаем, когда число элементов в сортируемом массиве является степенью числа 2. Для массива с 2n элементами алгоритм работает следующим образом. На первой фазе производится сортировка включением всех пар элементов массива, расстояние между которыми есть 2(n-1). На второй фазе производится сортировка включением элементов полученного массива, расстояние между которыми есть 2(n-2). И так далее, пока мы не дойдем до фазы с расстоянием между элементами, равным единице, и не выполним завершающую сортировку с включениями. Применение метода Шелла к массиву, используемому в наших примерах, показано в таблице 2.2.

В общем случае алгоритм Шелла естественно переформулируется для заданной последовательности из t расстояний между элементами h1, h2, ..., ht, для которых выполняются условия h1 = 1 и h(i+1) < hi. Дональд Кнут показал, что при правильно подобранных t и h сложность алгоритма Шелла является O(n(1.2)), что существенно меньше сложности простых алгоритмов сортировки.


 

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

28195. Бихевиоризм и необихевиоризм (Дж.Уотсон, Э.Толмен, Б.Скиннер и др.) 38.5 KB
  Бихевиоризм и необихевиоризм Дж. Предметом психологии бихевиоризм считает не сознание а поведение. Бихевиоризм от англ. Манифестом бихевиоризма считается статья его основателя американского психолога Дж.
28196. Психоанализ (З.Фрейд, К.Юнг, А.Адлер, К.Хорни и др.) 49.5 KB
  Наиболее существенными для развития личности Фрейд считал сексуальные инстинкты. Вместо того чтобы изучать сны Адлер обратился к исследованию ранних воспоминаний которые считал ключом к пониманию поведения мотивации и личности. Стиль жизни формируется к 5ти годам под влиянием творческой силы личности и в связи с ним формируется тип личности: Управляющий активный антисоциальный; Берущий низко активный паразитирующий; Избегающий не активный нет социального интереса; Социальнополезный высокий соц. В качестве механизмов...
28197. Гештальтпсихология (М.Вертгеймер, В.Келер, К.Коффка, К.Левин и др.) 41 KB
  История гештальтпсихологии берет начало в Германии в 1912 когда М. В противовес представлениям ассоцианистов о том что образ создается через синтез отдельных элементов и свойства целого определяются свойствами частей гештальтпсихологи выдвинули идею целостности образа свойства которого не сводимы к сумме свойств элементов в связи с этим часто подчеркивается роль гештальтпсихологии в становлении системного подхода в науке. Согласно гештальтпсихологии для человека существуют два отличных друг от друга мира: мир физический лежащий за...
28198. Предмет психологии. Специфические особенности и классификация психических явлений 68.5 KB
  Психология наука о закономерностях развития и функционирования психики как особой формы жизнедеятельности. Практическая психология ее задачи и роль в общественной практике. Психология изучает психику в закономерностях ее развития. Современная психология представляет собой широко развернутую область знаний включающую ряд научных дисциплин и направлений.
28199. Классификация методов современной психологии 37.5 KB
  Ананьева методы психологического исследования являются системами операций с психологическими объектами и вместе с тем являются гносеологическими объектами самой психологической науки.Пирогова: Собственно методы. Вспомогательные методы А Математические статистические Б Графические В Биохимические физиологические и др. Методические методы А Генетические Б Психофизиологические.
28200. Возникновение и развитие психики в процессе эволюции. Стадии развития психики 61 KB
  Под инстинктами понимаются действия или более менее сложные акты поведения которые появляются сразу как бы готовыми не зависят от выучки и индивидуального опыта будучи наследственно закрепленным продуктом филогенетического развития. Индивидуальноизменчивые формы поведения. Уже на ранних ступенях развития наблюдая поведение животных мы встречаем индивидуальноизменчивые формы поведения которые могут быть охарактеризованы как навыки новые реакции или действия которые возникают на основе выучки или индивидуального опыта и функционируют...
28201. Вклад В.Вундта в оформление психологии как самостоятельной науки. Создание психофизики (Г.Фехнер) 33 KB
  Кризис психологии выявился в наибольшей своей остроте когда сформировалась поведенческая психология рефлексология в России и бихевиоризм в Америке потому что поведенческая психология выдвинув поведение как предмет психологии с особенной остротой выявила кризис центрального понятия всей современной психологии понятия сознания. Согласно Вундту предметом изучения психологии является сознание а именно состояния сознания связи и отношения между ними законы которым они подчиняются. Используя метроном Вундт выделил ряд основных...
28202. Влияние идей И.М.Сеченова и И.П.Павлова на становление отечественной психологии 40.5 KB
  Иван Петрович Павлов 18491936 создатель материалистического учения о высшей нервной деятельности животных и человека. Учение Павлова о высшей нервной деятельности сложилось под влиянием материалистических традиций русской философии и развивало идеи И. В начале своей научной деятельности Павлов занимался преимущественно изучением сердца и кровеносных сосудов. Так было заложено начало павловского учения о трофической нервной системе особых нервных волокнах регулирующих процессы питания в тканях обмен веществ в них и тем самым...
28203. Вклад В.М. Бехтерева в развитие российской психологии 35.5 KB
  Бехтерева в развитие российской психологии. Бехтерев Владимир Михайлович 18571927 русский невропатолог психиатр физиолог психолог. Психологическое творчество Бехтерева можно условно разделить на два этапа. Бехтерев говорил о равноправном существовании двух психологий: субъективной основным методом которой должна быть интроспекция и объективной.