Название: Алгоритмы сортировки
Вид работы: доклад
Рубрика: Математика
Размер файла: 14.04 Kb
Скачать файл: referat.me-216726.docx
Краткое описание работы: Проблема упорядочивания данных с практической точки зрения: достоинства и недостатки пяти различных методов сортировки.
Алгоритмы сортировки
Проблема упорядочивания данных с практической точки зрения: достоинства и недостатки пяти различных методов сортировки.
Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы.
Практически каждый алгоритм сортировки можно разбить на три части:
- сравнение, определяющее упорядоченность пары элементов;
- перестановку, меняющую местами пару элементов;
- собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены.
Подобными свойствами обладают и те пять алгоритмов сортировки, которые
рассмотрены ниже. Они отобраны из множества алгоритмов, потому что,
во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь.
Метод пузырька.
( метод назван также обменной сортировкой с выбором) .
Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Алгоритмически это можно реализовать следующим образом. Мы будем просматривать весь массив "снизу вверх" и менять стоящие рядом элементы в там случае, если "нижний" элемент меньше, чем "верхний". Таким образом, мы вытолкнем наверх самый "легкий” элемент всего массива. Теперь повторим всю оперно для оставшихся неотсортироваными N-1 элементов (т.е. для тех, которые лежат "ниже" первого. Как видно, алгоритм достаточно прост, но, как иногда замечают, он является непревзойденным в своей неэффективности. Немного более эффективным, но таким наглядным является второй метод.
Сортировка выбором
На этот раз при просмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.
Метод Шелла
Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).
Метод Хoopа
Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).
Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.
Похожие работы
-
Принципы построения систем сбора и передачи информации для объектов электроэнгергетики
Рассмотрены вопросы проектирования современных систем сбора и передачи информации, используемых в электроэнергетике. Предложена трехуровневая архитектура этих систем.
-
Методы распознавания, идентификации и измерения расстояния до объектов в СТЗ ПР
Распознавание – процесс разметки сцены, представляющей собой проекцию трёхмерного рабочего пространства ПР на плоскость объектива, регистрирующего устройства – цифровую камеру (ЦК) или ультразвуковой модуль (УЗМ).
-
Развитие графоаналитического подхода «узел-функция-объект» как способа представления знаний
В последнее время наиболее развитыми странами считаются те страны, в которых наиболее развиты экономические отношения, как внутренние, так и внешние. Давно понятно, что успешное развитие государства невозможно без непрерывного развития экономического сектора, который в свою очередь состоит из хозяйствующих субъектов и отношений между ними.
-
Избранные главы дискретной математики
Содержание §1. Системы счисления……………………………….………………..……3 §2. Счетность и несчетность множеств………………………………6 §3. Трансфинитные числа и множества……………………………….10
-
по Информационной системе в экономике
Всероссийский заочный финансово-экономический институт Филиал в г.Волгограде Кафедра автоматизированной обработки экономической информации Контрольная работа по дисциплине
-
Поиск кратчайшего пути передвижения слона по шахматному полю
Министерство образования и науки Российской Федерации Агентство по образованию Тихоокеанский Государственный Экономический Университет Экономический институт
-
Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости
Аннотация Тема данной курсовой работы – " Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости". Для сравнения взяты четыре алгоритма: обход методом Грэхема, быстрый метод, метод “разделяй и властвуй” и динамический метод. Задача этой работы – раскрыть эти алгоритмы и провести исследования эффективности их.
-
Общее представление о математическом моделировании экономических задач
1. Общее представление о математическом моделировании экономических задач 1.1. Определение экономико-математической модели Математические модели экономических задач – это совокупность средств: уравнений, комплексов математических зависимостей, знаковые логические выражения, отображающие выделенные для изучения характеристики объекта, реальные взаимосвязи и зависимости экономических показателей.
-
по Экономико-математическому моделированию
На основе данных выданных преподавателем необходимо: 1. Определить параметры следующих уравнений регрессии: а) линейного; б) гиперболического; в) степенного;
-
Линеаризация без метода наименьших квадратов
Метод наименьших квадратов настолько прочно вошел в жизнь экспериментатора, что альтернативные методы линеаризации почти не рассматриваются.