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


 

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

33330. Телематические службы. Назначение, структура, назначение элементов 18.63 KB
  Первая телематическая служба Телетекст появилась в начале 80х годов. Телефакс факсимильная служба общего пользования предназначенная для передачи сообщений между абонентскими факсимильными аппаратами. Факсимильная служба группы 1 осуществляет аналоговую передачу без сжатия данных и передачу факсимильных сообщений по ОАКТС. Факсимильная служба группы 2 имеет ограниченные возможности сжатия данных страница текста передается по ОАКТС за 3 мин.
33331. Структура взаимоувязанной сети связи РФ. Общедоступные и корпоративные сети связи 64.78 KB
  Общедоступные и корпоративные сети связи. Вместе с тем сети общего пользования Министерства связи не справлялись с требуемыми объемами передачи сообщений требуемых для нормального экономического развития страны и поэтому ряд министерств и ведомств стали создавать свои сети для удовлетворения собственных нужд. В 70х годах было принято решение о создании Единой автоматизированной сети связи ЕАСС Союза ССР.
33332. Способы коммутации и их классификация 19.81 KB
  Методы коммутации в сетях электросвязи Для доставки сообщений в сетях электросвязи могут быть установлены соединения двух видов: долговременные и оперативные. Известны два основных принципа оперативной коммутации: а непосредственное соединение; б соединение с накоплением информации. При непосредственном соединении осуществляется физическое соединение входящих в узел коммутации УК каналов с соответствующими адресу исходящими каналами.
33333. Коммутация каналов. Достоинства и недостатки. Области применения 25.59 KB
  Коммутация каналов обеспечивает предоставление каждой паре абонентов последовательности каналов сети для монопольного использования. В классической схеме в коммутации каналов BC участвуют функциональные блоки физического уровня 11B1C и физические процессы ФП узлов коммутации каналов либо узлов смешанной коммутации рис 3. Структура коммутации каналов В результате происходит сквозная коммутация и между взаимодействующими абонентскими системами либо административными системами KE образуется последовательность логических каналов...
33334. Коммутация сообщений и пакетов. Достоинства и недостатки. Области применения 29.06 KB
  Коммутация пакетов обеспечивает передачу пакетов из одного канала в другой подключенный к этому узлу.3 выполняется на базе одного и того же оборудования коммуникационной сети но позволяет обеспечить как коммуникацию каналов при N=1 так и коммуникацию пакетов при N=3. Первая оказывается дороже но строго гарантирует адресатам время доставки пакетов.
33335. Профессиональные системы подвижной радиосвязи 27.42 KB
  Профессиональные частные системы подвижной радиосвязи PMR Professionl Mobile Rdio PMR Public ccess Mobile Rdio исторически появились первыми. Системы обеспечивающие взаимодействие с телефонными сетями общего пользования получили название частных PMR а не обеспечивающие такого взаимодействия профессиональных PMR т. Профессиональные частные системы подвижной радиосвязи В системе с общедоступным пучком каналов транкинговые системы Рис.
33336. Сотовые системы радиосвязи 23.81 KB
  Тогда требуемые для 01 жителей Москвы 250 каналов можно получить например разделением обслуживаемой территории радиусом в 50 км на 25 ячеек радиусом по 10 км с организацией в каждой ячейке только 10 радиоканалов с одним и тем же набором частот. Группа ячеек в зоне обслуживания с различными наборами частот называется кластером. Обычно ее развертывание начинается с небольшого числа крупных ячеек которые через некоторое время постепенно трансформируются в большее число более мелких ячеек. При этом пропускная способность сети на территории...
33337. Системы персонального радиовызова 15.32 KB
  Современный рынок услуг подвижной связи характеризуется высокими темпами развития систем персонального радиовызова СПРВ которые гармонично сопрягаются с системами радиосвязи и передачи данных. По назначению СПРВ можно разделить на частные ведомственные и общего пользования. Частные СПРВ обеспечивают передачу сообщений в локальных зонах или на ограниченной территории в интересах отдельных групп абонентов. Под СПРВ общего пользования понимается совокупность технических средств через которые через ТФОП происходит передача в радиоканале...
33338. Системы беспроводного доступа (телефония, блютус, wi-fi, wi-max) 41.82 KB
  В 1992 году ETSI принял стандарт ETS300 175 на общеевропейскую систему беспроводных телефонов DECT предназначенную для передачи речевых сообщений и данных в полосе частот 1880. По своему функциональному назначению PCS является близким аналогом стандарта DECT но ориентирована на использование в рамках принятого в США распределения спектра частот и концепции развития персональной связи отличающихся от европейских. Рассмотрим подробнее характеристики общеевропейской системы беспроводных телефонов DECT. Стандарт DECT Digitl Europen Cordless...