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


 

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

43691. Автоматизированная система управления деятельностью туристического агентства «Коми-тур» 8.92 MB
  Туристическое агентство «Коми-тур» оказывает услуги населению по подготовке и организации отдыха. Основные услуги – это услуги по подбору наиболее оптимальных для туриста туров (экскурсии, отдых на море, активный туризм, отдых с детьми, паломнический туризм), бронирование выбранного тура у туроператора, оформление документов, услуги по организации встречи и проводов туристов.
43692. Анализ индивидуальных трудовых споров и выявление проблем, возникающих при рассмотрении их в суде 174 KB
  Значительно возросло количество трудовых дел в судах. Появились новые очень сложные дела: о взыскании морального вреда, причиненного работнику незаконным увольнением, переводом на другую работу, невыплатой гарантированных законодательством выплат и льгот, отказом от заключения трудового договора и другие.
43693. Психологічні особливості соціального інтелекту та поведінки в конфлікті в юнацькому віці 197.84 KB
  Однакзведення інтелекту до миследіятельності вириває його з контексту соціалізації що припускає вироблення власних ціннісних орієнтацій свого стилю життя. У сучасній школіяка орієнтована на розвиток теоретичного інтелекту як відзначає М. Подальша розробка категорії соціального інтелекту визначається результатами досліджень Г. Холодної які виявили взаємозв'язок інтелекту людини і здатності реалістично оцінювати себе регулювати свою поведінку; дослідженнями К.
43694. Проектирование АСУ ОАО «ГСК «Югория» и разработка конкретных проектных решений по одной из подсистем АСУ 271.67 KB
  Процесс создания АСУ – это последовательное внедрение более совершенных, научно-обоснованных методов управления и средств вычислительной техники с целью увеличения эффективности производства и повышения производительности труда. Экономико-математические методы оптимального планирования и управления, средства автоматизированной обработки больших объемов информации становятся неотъемлемой частью структур управления, способом их функционирования.
43695. Разработка рекомендаций по совершенствованию конкурентоспособности ООО «НЗЖБИ имени Иванова Г.С.» на рынке 318.92 KB
  Организационно-экономическая характеристика предприятия Изучение конкурентоспособности предприятия представляет собой одну из важнейших составных частей рыночных исследований создающих основу для выработки стратегии и тактики деятельности на рынке выбора правильного пути повышения технического уровня и качеств. Именно по этой причине большую актуальность приобретают исследования в области конкурентоспособности предприятия поиск путей её повышения. разработать рекомендации по совершенствованию конкурентоспособности предприятия на...
43696. Таймер керування водяним насосом 233.02 KB
  Розрахунок ЗІП повинен проводитись по встановленим нормам.1 Логічний розрахунок JKтригера. Необхідно виконати розрахунок jk тригера.2Конструктивний розрахунок таймеру керування водяним насосом 5.
43697. Внутрисхемное программирование 288.79 KB
  Программатор, использующий интерфейс SPI, необходимо подключить к объекту, используя как можно меньшее количество проводов. Для подключения программатора микроконтроллеров AVR непосредственно к печатной плате используется шестипроводной интерфейс.
43698. Разработка методических рекомендаций и практических предложений по совершенствованию направлений деятельности коммерческих банков с ценными бумагами 208.69 KB
  Возникают совершенно новые оригинальные виды банковских операций и услуг связанных с новыми типами финансовых инструментов выраженных в форме различных ценных бумаг. Активное участие коммерческих банков на рынке ценных бумаг во многом меняет содержание их операций придает их деятельности более выраженный рыночный характер. С помощью операций с ценными бумагами коммерческие банки могут направлять инвестиции в производство в торговый оборот а также финансировать государственные расходы. Во многих регионах России особенно депрессивных...
43699. Проектирование системы электроснабжения электрооборудования и электрохозяйства станкостроительного завода «Луч» 3.17 MB
  Здесь для реализации технологического процесса используется прежде всего оборудование связанное с обработкой металлов токарные фрезерные станки станки типа обрабатывающий центр шлифовальные станки печи плавки металла для литья и т. Потребителями электрической энергии в этом технологическом оборудовании являются прежде всего асинхронный двигатели с короткозамкнутым ротором малой и средней мощности двигатели постоянного тока малой мощности нагревательные элементы. В состав перечисленного оборудования входят асинхронные двигатели и...