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)), что существенно меньше сложности простых алгоритмов сортировки.


 

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

78907. Научные школы 22.5 KB
  Научные школы. Внутри науки существуют научные школы функционирующие как организованная и управляемая научная структура объединенная исследовательской программой единым стилем мышления и возглавляемая как правило личностью выдающегося ученого. В науковедении различают классические научные школы и современные. Классические научные школы возникли на базе университетов.
78908. Характеристики взаимодействия науки, экономики и власти 31.5 KB
  Характеристики взаимодействия науки экономики и власти Отношения науки и экономики всегда представляли собой большую проблему. Традиционное представление о том что технология является неотъемлемым приложением науки сталкивается с эмпирическими и практическими возражениями. Однако если прикладные науки обслуживая производство могут надеяться на долю в распределении его финансовых ресурсов то фундаментальные науки напрямую связаны с объемом бюджетного финансирования и наличием тех планов и программ которые утверждены государственными...
78909. Философия как интегральная форма научных знаний. Статус СГН 28.5 KB
  Статус СГН Первоначально философия выступала как интегральная форма научного знания поэтому знания об обществе культуре истории и человеке носили до конца XVIII в. С одной стороны они так же как законы естествознания носят объективный характер то есть появляются на исторической сцене функционируют на ней и сходят с нее независимо от воли и сознания людей будучи причинно обусловленными соответствующими объективными обстоятельствами. Это отличие отнюдь не отменяет тесной связи социальногуманитарного знания с практикой в особенности...
78910. Зависимость СГН от социокультурного контекста 28 KB
  в науке преобладала классическая рациональность которая реализовывалась по схеме: Субъект познания Способы познания Объект познания. ни способы которыми он пользуется не оказывают влияния на искомый результат познания и мы получаем образ объекта в чистом виде на схеме это обозначено скобками. Второй этап характеризующийся формированием неклассической рациональности начинается тогда когда науки переходят к исследованию объектов воздействие на которые способов познания является неустранимым и сказывается на результате...
78911. Сходства и отличия наук о природе и об обществе 28.5 KB
  Проблема разграничения наук о природе и социальногуманитарных наук и определение предмета гуманитарного знания которым посвящен первый вопрос является важнейшей методологической проблемой современного наукознания. Сложность ее решения связана с тем что относительно предмета социальногуманитарных наук не существует единства мнений. Чаще всего различные исследователи пытаются выделить среди этих наук какуюто ключевую дисциплину вокруг которой можно было бы объединить все другие науки о духе.
78912. Специфика объекта СГП 21.5 KB
  Вовторых в структуру и содержание объекта социальногуманитарного познания с необходимостью входит субъект познания. Объективация предмета познания оказывается в этом случае неполной и сопряжена с большими методологическим трудностями. Втретьих исследование объекта осуществляется в социальногуманитарном знании с ценностных позиций поскольку субъект познания будучи сам частью социальной системы оказывается нагруженным идеологическими предпосылками предрассудками некритически воспринятыми установками и т.
78913. Социокультурная обусловленность дисциплинарной структуры социально-гуманитарного знания 25 KB
  Прежде всего речь идет о различении социальных наук как наук об обществе и гуманитарных наук как наук в фокусе которых находится человек индивидуальная и социальная психология этика и т. Разделение наук по предмету о чем речь уже шла выше. Разделение наук по методу: в социальных науках используется метод объяснения тогда как в гуманитарных базовой методологической процедурой выступает понимание сразу же заметим что такое разделение грешит противопоставлением понимания объяснению. Разделение наук одновременно по предмету и методу...
78914. Конвергенция естественно-научного и СГН в современой науке 24 KB
  Логику развития методологии гуманитарного познания можно представить следующим образом: сначала проблематика методологии гуманитарных наук развивалась в направлении выявления и обоснования их специфики по сравнению с науками о природе. Главной на этом этапе является проблема идентификации социальногуманитарных наук и их демаркации от наук естественных. Обоснованию специфики социальногуманитарного познания посвящены работы Дильтея Описательная психология Гадамера Истина и метод Фуко Слова и вещи Рикера Герменевтика и...
78915. Специфика научной картины мира в СГН 31.5 KB
  Специфика научной картины мира в СГН Научная картина мира исторична она опирается на достижения науки конкретной эпохи в пределах тех знаний которыми располагает человечество. Научная картина мира представляет собой синтез научных знаний соответствующих конкретноисторическому периоду развития человечества. Поэтому она более строгое понятие чем образ мира или видение мира. В научную картину мира входят знания отвечающие критериям научности.