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


 

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

28002. Радионуклиды в агроэкосистеме: перенос радионуклидов по с/х цепочкам и их миграция в агроценозах 2.32 KB
  Основными источниками техногенных радионуклидов в агросфере являются остаточные количества долгоживущих радв поступивших в нее в результате испытаний ядерного взрыва выбросов и сбросов радов при работе атомных электростанций и др предприятий полного ядерного топливного цикла. Рост химизации с х ведет к увеличению применения удобрений и мелиорантов с повышенным содержанием естественных радов. Почва обладает уникальной сорбционной способностью по отношению к поступающим в нее радов.
28003. Сравнительный анализ функционирования естественных экосистем и агроэкосистем. Устойчивость эко(агроэко)системы: толерантность, уязвимость, гетерогенность агроценозов 5.26 KB
  Экосистемы исторически сложившееся в биосфере и на той или иной территории открытые но целостные и устойчивые системы живых организмов. Агроэкосистемы вторичные измененные человеком биогеоценозы основу которых составляют искусственно созданные биотические сообщества объединяемые видами живых организмов. Особенность агросистем в отличии от экосистем их неусточивость то есть к способности саморегуляции.
28004. Формирование биогенной нагрузки в природных аграрных системах. Естественные потери биогенных веществ в земледелии, животноводстве и селитебных территорий 4.24 KB
  Естественные потери биогенных веществ в земледелии животноводстве и селитебных территорий. Интенсивно развивающееся сельское хозяйство это наиболее активный источник поступления биогенных элементов. Влияние с х как источника поступления биогенных веществ в природные ресурсы возрастает в связи с увеличением распаханности территорий трансформацию угодий мощной техникой развитием процессов химизации на основе минеральных и органических удобрений. Потери биогенных веществ в растениеводстве условно можно разделить на...
28005. Функционирование агроэкосистем в условиях техногенеза 4.85 KB
  Функционирование агроэкосистем в условиях техногенеза. Агроэкосистема АЭС совокупность биогенных и абиогенных компонентов участков суши преобразованных человеком используемых для производства сельхозпродукции. Основа АгроЭкоСистем почва с х угодия. Типы АгроЭкоСистем: Пропашное земледелие Многолетнее земледелие Многоурожайное земледелие МезоАЭС крупномасштабная МикроАЭС грядка Суша занимает площадь 149 млрд.
28006. Экологизация сельскохозяйственного производства 4.56 KB
  Природоразрушающий ресурсоемкий тип развития АПК требует пересмотра сложившейся теории и на практике техногенной концепции развития АПК. Главным принципом развития АПК должна стать экологизация с х производства всех мероприятий по развитию с х учет природных особенностей функционирования земельных ресурсов. для изменения приоритетов в распределении ресурсов капитальных вложений в АПК усилить природоохранную роль затрат. Для преодоления негативных тенденций в развитии АПК скорейшего решения...
28007. Экологическая биотехнология. Возможности увеличения производства экологически безопасной продукции на основе биопроизводства 2.52 KB
  Возможности увеличения производства экологически безопасной продукции на основе биопроизводства. Среди новых направлений биотехнологии способствующих получению экологически безопасной продукции следует отметить применение микробиологических удобрений промышленную переработку бытовых отходов индустриальную технологию компостирования отходов животноводства и др. микробиологические удобрения повышают продуктивность растений и кол во растительной продукции. Азотфиксирующие микроорганизмы служат прекрасной основой для...
28008. Экологически безопасные технологии и оптимизация обработки почвы 3.73 KB
  Поэтому нужна разработка таких сельскохозяйственных машин и орудий которые при общей эффективности должны оказывать минимальный вред окружающей среде а именно: Сократить выбросы от с х машин и орудий Уменьшить нагрузку на почву путем изменения конструктивной особенности техники Внедрение двигателей с высоким КПД но низким потреблением топлива.
28009. Экологические аспекты применения сточных вод при орошении. Ценность сточных вод в повышении плодородия почв. Контроль загрязнения почв 12.86 KB
  Ценность сточных вод в повышении плодородия почв. Сточные воды используются для орошения на специальных участках земледельческих полях орошения ЗПО. Под последними понимаются водохозяйственные объекты оборудованные для непрерывного приема определенного количества сточных вод в течение всего года с целью их очистки или доочистки и использования для орошения.
28010. Экологические особенности и значимость биогумуса. Препараты получаемые на основе биогумуса. Экологические аспекты подготовки и применения биогумуса 2.93 KB
  Препараты получаемые на основе биогумуса. Экологические аспекты подготовки и применения биогумуса. Установлена возможность биогумуса связывать радионуклиды находящиеся в почве органических удобрений резко уменьшать поступление тяжелых металлов в растения.