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


 

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

36717. Гидрологический режим реки Амазонки и ее устьевой области 1.61 MB
  Географическое положение бассейна реки (географическая зона, высотный пояс, удаленность от океанов, государственная принадлежность, координаты центра и крайних точек, основные морфометрические характеристики (площадь, длина, ширина бассейна, длина реки), основные притоки – карта-схема бассейна)
36718. Моделирование случайных величин 176 KB
  Три стрелка стреляют каждый по своей мишени делая независимо друг от друга по одному выстрелу. Рассматриваются три случайные величины: число попаданий первого стрелка; число попаданий второго стрелка; число попаданий третьего стрелка; Пусть случайная величина. Три стрелка стреляют каждый по своей мишени делая независимо друг от друга по одному выстрелу. Рассматриваются три случайные величины: число попаданий первого стрелка; число попаданий второго стрелка; число попаданий третьего стрелка; Пусть случайная величина.
36719. РАБОТА С ЗАПРОСАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ 243.5 KB
  Лабораторная работа № 3 Лабораторная работа № 3 РАБОТА С ЗАПРОСАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ Задание № 1 Создайте запрос на основе таблиц Административные районы и Административные центры выбирающий все районы центры которых являются городами. Технология работы Создайте запрос на основе связанных таблиц. Для этого в окне базы данных выберите объект 3апросы Создание запроса в режиме конструктора; В окне Добавление таблицы выделите в списке таблицу Административные районы и щелкните на кнопке Добавить; В...
36720. Заходи по розширенню долі аптечної мережі «Бажаємо здоров’я» на фармацевтичному ринку України 434 KB
  Кожна компанія зацікавлена тривалий час зберігати свій ринок і бути прибутковою. Для цього потрібне постійне вивчення ринку, розробка заходів по підвищенню конкурентоспроможності і збільшенню частки ринку. Збільшення частки ринку включає різноманітні заходи, сюди входять ребрендинг, комплекс просування, розширення існуючої мережі.
36722. РАБОТА С ФОРМАМИ И ОТЧЕТАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ 130.5 KB
  Лабораторная работа № 4 Лабораторная работа № 4 РАБОТА С ФОРМАМИ И ОТЧЕТАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ Задание 1 Создайте ленточную форму на основе таблицы Административные районы и добавьте вычисляемые поля в форму в режиме конструктора в которых будут выводиться итоговые суммы для полей число населенных пунктов площадь территории численность населения и среднее значение для поля плотность населения. Технология работы На основе таблицы Административные районы создайте форму ленточного вида используя Мастер по...
36724. Имитационное моделирование «производственных процессов» 46.5 KB
  На сборочный участок цеха предприятия через интервалы времени распределенные экспоненциально со средним значением 10 мин поступают партии каждая из которых состоит из трех деталей. Половина всех поступающих деталей перед сборкой должна пройти предварительную обработку в течение 7 мин. Процесс сборки занимает всего 6 мин. Затем изделие поступает на регулировку продолжающуюся в среднем 8 мин время выполнения ее распределено экспоненциально.
36725. Моделирование технологического процесса ремонта и замены оборудования 230.5 KB
  На предприятии имеется L станков которые работают 24 часа в сутки. Всего в системе M станков M LLсобственныеMLарендуемые для резерва. Любой из станков может выйти из строя в любое время. В мастерской есть три участка ремонта станков.