Файл: Методы сортировки данных.pdf

Введение

Можно считать, что в любом из существующих программных проектов однажды возникнет необходимость в обработки большого количества единообразно организованных данных. В подобных ситуациях удобно прибегнуть к обработке данных как единого целого, для чего стоит представить их в виде единого массива — а именно формального объединения какого-то количества однотипных строк, объектов или символов, что будут рассматриваться как единое целое.

При решении любых экономических и научно-технических задач обработки большого количества заданий так или иначе придется столкнуться с понятием «массив». Именно массивы значительно упрощают процесс управления данными, где необходимо использование большего количества элементов данных схожего типа, что дает отличное ыыедение в разнообразные методики работы с базами данных. Они полезны в частности в вопросах обработки большого количества информации способами, кажущимися невозможными к реализации при использовании традиционных переменных.

Также одним из важнейших свойств алгоритма можно считать сферу его применения. Здесь классифицируется два типа упорядочивания:

Сортировка внутренняя — та, что оперирует лишь теми массивами, что занимают все место в оперативной памяти, сохраняя при этой совершенно свободный доступ к каждой из ячеек. ВА данном случае упорядочивание данных будет происходить в том же месте, но при этом не произведет особых незапланированных затрат.

В нынешних архитектурах ПК (персональных компьютеров) популярно прибегать к кэшировании памяти и подкачке. Именно поэтому крайне важно, чтоб алгоритм сортировки правильно считался с применяемыми алгоритмами подкачки и кэширования памяти.

В свою очередь, сортировка внешняя использует уже запоминающие устройства большего объема, но при этом имеют доступ с последовательным, а не произвольным, упорядочивающем файлов. Это значит, что в определенный момент мы можем увидеть лишь один элемент, хоть затраты на перемотку в сравнении с затратами на память слишком велики. Из-за того, что это имеет за собой последствия в виде дополнительных ограничений на алгоритм, приходится прибегать к специальным методам упорядочивания, которые обычно используют не основное, а дополнительное пространство дисков. Помимо этого, доступ к тем данным, которые хранятся на носителе, будет производиться гораздо медленнее, чем производились бы операции непосредственно с оперативной памятью.

Таким образом, доступ к носителям информации может быть обеспечен последовательным образом: в новый момент позволено учитывать и записывать лишь тот элемент, что идет вслед за текущим.

• объём данных не позволяет им разместиться в ОЗУ.

«Сортировкой» принято называть процесс, в который входит перестановка объектов какого-то множества в фиксированном порядке. Цель процесса сортировки — облегчение дальнейшего поиска элементов в заранее отсортированном множестве. В таком смысле присутствие элементов сортировки можно заметить почти в любых задачах. В оглавлениях, ведомостях, библиотеках, словарях и складах содержатся упорядоченные объекты, но их необходимо искать и изучать.

В наше время существует колоссальное количество различных вариантов сортировки, но их большая часть имеет сходства. Каждый из возможных методов имеет определенные особенности. От выбора метода будет зависеть эффективность каждого конкретного случая.

Таким образом, методы сортировки имеют колоссальную важность, особенно при обработке данных. Казалось бы, что легче рассортировать, чем набор данных? Однако с сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. Практически каждый из таких приемов можно встретить в связи с алгоритмами сортировки. В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых, в некотором смысле являются оптимальными, а большинство имеет какие-либо преимущества по сравнению с остальными. В настоящее время разработано достаточно много различных методов сортировки. Одни из них относятся к методам простых сортировок, другие к улучшенным.

Данная курсовая работа будет состоять из введения, двух глав, заключения и списка литературы.

Глава 1 Методы сортировки массивов

Алгоритмы устойчивой сортировки (самые медленные алгоритмы сортировки, принадлежащие к классу О(n²)):

Пузырьковая сортировка (метод простых обменов).

Шейкер-сортировка.

Сортировка методом выбора (метод простого выбора).

Сортировка методом вставок.

Сортировка парным (бинарным) деревом.

Сортировка слиянием.

В дальнейших разделах, используя пример колоды карт, мы рассмотрим и опишем методы пузырьковой сортировки, шейкер-сортировки, сортировки выбором и сортировки вставок. Для начала работы выбираем из колоды абсолютно все карты одной масти, к примеру, пики, перемешиваем (тасуем) их. То, что на руках мы имеем лишь тринадцать карт, значительно упростит предстоящую работу, а также сделает ее куда более наглядной. Детальное описание представленных методов изложено в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».^[1]

1.1 Пузырьковая сортировка (метод простых обменов)

Алгоритм, с которого следует начинать — пузырьковая сортировка, ведь именно с ним сталкивается каждый программист, приступая к изучению азов языка программирования.

Из всех существующий в наше время, пузырьковая сортировка является самым времязатратным методом. Однако, в нем есть и преимущества: его незначительно, но проще запрограммировать.

Рис. 1. Один проход с помощью алгоритма пузырьковой сортировки 

Пузырьковая сортировка работает следующим образом. Разложите ваши карты (помните, их всего 13). Посмотрите на двенадцатую и тринадцатую карту. Если двенадцатая карта старше тринадцатой, поменяйте их местами. То же сделайте и для пар (10, 11), (9, 10), и т.д., пока не дойдетё до первой и второй карты. После первого прохода по всей колоде туз окажется на первой позиции. Фактически когда вы «зацепились» за туз он «выплыл» на первую позицию, как показано на рисунке 1. Продолжайте процесс сортировки, уменьшая с каждым новым циклом количество просматриваемых карт и поступая так до тех пор, пока вся колода не будет отсортирована.

Идея данного метода заключается в том, что весь массив вариантов будет рассматриваться лишь один раз, а при каждом рассмотрении в сравнение будут идти лишь знаки 2-х соседних элементов. В том случае, если они находились в неверном порядке, произведется их перестановка. Так будет происходить долгое время, пока пока не останется ни одной перестановки для выполнения системой. Этот метод зовут именно «пузырьковой» сортировкой, ведь меньшие значения элементов всплывают подобно пузырькам воздуха в жидкости, в то время как более тяжелые элементы оседают на дно.

Имеет смысл предположение о том, что такого рода сортировки являются через чур утомительными и занимают слишком много времени. Именно медленной скоростью выполнения работы и выражается утомительность данного метода при его воспроизведении на языке Паскаль. Однако, придуман еще один вариант метода описания «пузырьковой» сортировки: в том случае, когда при выполнении не производится ни одной перестановки, мы можем предположить, что карты уже были рассортированы в необходимой последовательности.

Эффективность сортировки. За один проход непосредственно среднее число сравнений равно С=size/2. При этом среднее число всех возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равняется 1, максимальное − size -1, а среднее − size/2.

Лидирующая проблема метода пузырьковой сортировки заключается в том, что перестановка будет производиться лишь в соседних элементах отдельного избранного массива. В том случае, если этот элемент с минимальным значением случайно окажется в конце массива, он будет тратить довольно много времени, меняясь с каждым последующим элементом ровно столько времени, сколько потребуется ему для достижения первой позиции.

Исходя из вышеописанных проблем, метод пузырьковой сортировки можно отнести к наиболее нестабильным, ведь из двух элементов с одинаковыми значениями в уже готовом сортированном списке окажется тот, что стоял в первоначальном массиве дальше от начала. Если менять тип сравнения на«меньше чем» или «равен», а не просто «меньше», то метод пузырьковой сортировки будет устойчивее, однако и количество перестановок резко возрастет, так что эта оптимизация бессмысленна, ведь она не даст никакого выигрыша в скорости.

00000000000000000000000000000000000000000000000000000000000000000000099999

1.2 Шейкер-сортировка

Помимо базового алгоритма, у метода пузырьковой сортировки имеется и еще один вариант, дающую на практике увеличение скорости, хоть и незначительное. Это и есть так называемая в мире шейкер-сортировка (shake sort).^[2]

Вернёмся к картам. Выполним первый проход согласно алгоритму сортировки, как показано на рисунке 2.1. Туз попадает на первую позицию.