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


 

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

80102. Morphology and Syntax as two main parts of grammar 25.78 KB
  Grammar is field of linguistics that covers the rules governing the use of any given natural language the rules of the language itself. The main object of TG is the grammatical structure of language, that is the system of the rules of word changing and sentence building....
80103. Word Meaning and its types 26.79 KB
  Milletrdquo; Word is the ssocition prticulr mening with prticulr group of sounds cpble of prticulr grmmticl employmentrdquo; Morosov fnsiev – speech unit used for purposes of humn communiction mterilly representing group of sounds possessing mening sucsessible to grmmticl employment nd chrcterized by forml nd semntic unity. It is recognized tht word mening is mde up of vrious components. the prgmtic communictive vlue of the word.The denottion of word is the direct explicit mening tht mkes communiction possible.
80104. ОБЪЕКТЫ ФИНАНСОВОГО ПРАВООТНОШЕНИЯ 61 KB
  Проблема объекта правоотношения в теории права долгое время являлась одной из наиболее дискуссионных. К сегодняшнему дню в связи с достаточно обширным исследованием этой проблемы как в теории права так и в отраслевых юридических науках научные взгляды на вопрос об объекте правоотношения несмотря на всю многоголосицу мнений более или менее определились. Согласно первой выраженной в обобщенном виде объектом правоотношения являются материальные или нематериальные блага на которые направлено или на которые воздействует поведение всех...
80105. Применяемый подход к построению системы оперативного управления финансами 74.5 KB
  В рамках системы тактического управления финансами задаются плановые показатели по возникновению и погашению обязательств и формируются детальные планы расходования средств на календарный месяц. Поэтому построение системы оперативного управления финансами как показывает практика является задачей первостепенной важности как для проблемного предприятия столкнувшегося с недостатком денежных поступлений так и для успешно развивающегося бизнеса которому требуется надежная защита от хозяйственных рисков и получение максимального эффекта от...
80106. Отчеты об исполнении федерального и консолидированного бюджета 100 KB
  Отчеты об исполнении федерального и консолидированного бюджета за истекший год составляет Министерство финансов РФ и представляет их в Правительство РФ. Отчет об исполнении бюджета составляется финансовыми органами на основании ведущегося ими через органы казначейства учета исполнения бюджета и отчетов учреждений и организаций кредитных учреждений участвующих в исполнении бюджета. Правительство РФ ежегодно в мае следующего за отчетным года представляет Федеральному Собранию отчетный доклад и отчет об исполнении федерального бюджета...
80107. ПОНЯТИЕ, РОЛЬ И ПРАВОВАЯ ФОРМА ГОСУДАРСТВЕННОГО И МЕСТНОГО БЮДЖЕТОВ 53 KB
  Бюджет необходимый атрибут государства и основа его суверенитета. Посредством бюджетов образуются денежные фонды соответствующего государственного или муниципального образования которые обеспечивают выполнение задач общего для них значения создают финансовую основу для осуществления функций органов государственной власти и местного самоуправления. В материальном аспекте государственный как и местный бюджет представляет собой централизованный в масштабах определенного государственного или муниципального образования денежный фонд который...
80108. ПОНЯТИЕ И ЗНАЧЕНИЕ ФИНАНСОВОГО КОНТРОЛЯ 38 KB
  Наличие финансового контроля объективно обусловлено тем что финансам как экономической категории присущи не только распределительная но и контрольная функции. Поэтому использование государством и муниципальными образованиями для решения своих задач финансов обязательно предполагает проведение с их помощью контроля за ходом выполнения этих задач. Значение финансового контроля выражается в том что при его проведении проверяются вопервых соблюдение установленного правопорядка в процессе финансовой деятельности органами государственной...
80109. ПРЕДМЕТ И ПОНЯТИЕ ФИНАНСОВОГО ПРАВА 71.5 KB
  В этом и заключается предназначение финансового права. Область финансов и отдельные их стороны затрагивают нормы и других отраслей права. Однако именно в сферу финансового права эта область подпадает в целом хотя на разные звенья финансовой системы его нормы распространяются не в одинаковой мере.