Информационный центр "Центральный Дом Знаний"
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
Алгоритмы сортировкиОглавление: Введение 3 Теоретическая часть 5 Практическая часть 13 Список литературы: 20 Введение В данной курсовой работе я буду углубленно изучать в теоретической части алгоритмы сортировки применяемые в информатике, а в практической части закреплю уже имеющиеся знания решением экономической задачи при помощи использования Microsoft Excel – программы для работы с электронными таблицами. Как было отмечено выше, в теоретической части курсовой работы будут изучены алгоритмы сортировки, применяемые в информатике. Будет подробно исследована проблема упорядочивания данных с практической точки зрения: достоинства и недостатки восьми различных методов сортировки. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. При выполнении теоретической части курсовой работы я отвечу на следующие вопросы, которые раскрывают подробно свойства каждого алгоритма, а именно: - какое сравнение, определяет упорядоченность пары элементов? - какая перестановка меняет местами пару элементов? - каков собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены? Подобными свойствами обладают и восемь алгоритмов сортировки, которые рассмотрены ниже. Они отобраны из множества алгоритмов, потому что, во-первых, наиболее часто используются, а во-вторых, потому что большинство остальных алгоритмов является различными модификациями описанных здесь. При выполнении курсовой работы я буду использовать следующие прикладные программы: это Microsoft Word и Microsoft Excel. Microsoft Word - это представляет собой текстовый редактор, предназначенный для создания, редактирования, вывода на экран и печать, а также сохранения в виде файлов различного рода документов и данных. Microsoft Word представляет собой пакет прикладных программ, который наряду с перечисленными выше операциями позволит производить форматирование текста (по всему документу и его части), формировать различные стили оформления документов, пользоваться большим количеством шрифтов, выделять (курсивом, подчеркиванием, жирным шрифтом и другими средствами) участки текста, набирать текст в виде колонок, включать в тексты иллюстрации, формировать различного рода указатели и ссылки, вводить верхние и нижние колонтитулы страниц, производить автоматизированный поиск элементов текста и исправление ошибок, копировать и переносить в другой документ любые участки текста, а также многое другое. Microsoft Excel – это табличный редактор, наименование прикладной программы, предназначенной для решения широкого круга вычислительных задач (экономических, бухгалтерских, инженерных, статистических и т.д.) на больших массивах данных, представляемых в табличной форме. Microsoft Word я буду использовать при оформлении курсовой работы в общем, то есть её текстовой части, а Microsoft Excel - в теоретической части, при решении экономической задачи. При выполнении курсовой работы я использовала персональный компьютер со следующими характеристиками: Процессор: Intel Corel 2 Duo E 4500 (2200 Hz/800MHz/2 MB); Жесткий диск: 160 Gb; Оперативная память: 1 Gb; Видеокарта: PCI – E 16x; Программное обеспечение: Windows Professional XP. Теоретическая часть Одним из важнейших процедур обработки структурированной информации является сортировка и поиск. Сортировка - это процесс упорядочения некоторого множества элементов в некотором определенном порядке. Определенный порядок (например, упорядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик, по классам, типам и т.п.) в последовательности объектов необходимо для удобства работы с этим объектом. Целью алгоритмов сортировки является упорядочение последовательности элементов данных. Под поиском подразумевается процесс нахождения в заданном множестве объекта, обладающего свойствами или качествами задаваемого шаблона. Поиск элемента в последовательности отсортированных данных занимает время, пропорциональное логарифму количеству элементов в последовательности, а поиск элемента в последовательности не отсортированных данных занимает время, пропорциональное количеству элементов в последовательности, то есть намного больше. Существует множество различных методов сортировки данных. В курсовой работе я рассмотрю следующие методы сортировки: Метод пузырька; Сортировка выбором; Сортировка вставкой; Метод Шелла; Быстрая сортировка (метод Хоара); Сортировка бинарным деревом; Сортировка массивом (хеширование); Обменная поразрядная сортировка. Важнейшей характеристикой любого алгоритма сортировки является скорость ее работы, которая определяется функциональной зависимостью среднего времени сортировки последовательностей элементов данных, заданной длинны, от этой длинны. Время сортировки будет пропорционально количеству сравнений и перестановки элементов данных в процессе их сортировки. Вообще, алгоритмы сортировки - одна из самых хорошо исследованных областей информатики. Тем не менее, не исключены открытия и в этой области, потому что наверняка существуют еще какие-то пока неизвестные методы сортировки, основанные на новых принципах и идеях. Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации. Некоторые задачи обработки данных решаются проще, если данные упорядочены. Примеры таких задач я рассмотрю в этой курсовой работе. Метод пузырька Пузырьковая сортировка - один из наиболее широко известных алгоритмов сортировки. В этом методе массив также делится на две части: отсортированную и неотсортированную. На каждом шаге метода мы пробегаем от меньших индексов к большим по неотсортированной части, каждый раз сравнивая два соседних элемента: если они не упорядочены между собой (меньший следует за большим), то меняем их местами. Тем самым за один проход путем последовательных обменов наибольший элемент неотсортированной части сдвинется к ее концу. Алгоритм называют пузырьковой сортировкой, потому что на каждом шаге наибольший элемент неотсортированной части подобно пузырьку газа в воде всплывает вверх. Запишем алгоритм на языке Паскаль, заметив, что в том случае, когда за очередной проход не было сделано ни одного обмена, массив уже отсортирован и следующие проходы можно пропустить. Для отслеживания такой ситуации введем логическую переменную Flag - признак совершения обмена на очередном проходе: for i := N-1 downto 1 do begin Flag := false; for j := 1 to i do if a[j]>a[j+1] then begin Tmp := A[j]; A[j] := A[j+1]; A[j+1] := Tmp; Flag := true; end; if not Flag then Break; end; Этот алгоритм имеет среднюю и максимальную временные сложности T(n2) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти за исключением памяти для фиксированного числа переменных (i, j, Tmp, Flag). Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к T(n). Сортировка выбором Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте. Потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементном и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором, поскольку он работает, циклически выбирая наименьший из оставшихся элементов. Этот метод работает очень хорошо для небольших файлов. Его «внутренний цикл» состоит из сравнения a[i]<a[min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить. Кроме того, хотя сортировка выбором является методом «грубой силы», он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами. Сортировка вставкой Это изящный и простой для понимания метод. Вот в чем его суть: создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку. Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после - большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив. Вот как такой алгоритм можно реализовать на языке программирования Pascal: Program InsertionSort; Var A,B : array[1..1000] of integer; N,i,j : integer; Begin {Определение размера массива A (N) и его заполнение} … {сортировка данных} for i:=1 to N do begin j:=i; while (j>1) and (B[j-1]>A[i]) do begin B[j]:=B[j-1]; j:=j-1; end; B[j]:=A[i]; end; {Вывод массива B} … End. Виды сортировок вставкой: Сортировка простыми вставками; Сортировка бинарными вставками; Сортировка двухпутевыми вставками. Здесь первый - элемент помещается в середину области вывода, и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее. Таким образом, удается сэкономить примерно половину времени работы по сравнению с простыми вставками за счет некоторого усложнения программы. Метод Шелла Такой метод предложен в 1959 г. Дональдом Л. Шеллом. Метод Шелла является усовершенствованием простого включения, которое основано на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле мы избавлялись от сдвига A[i], сохраняя его в промежуточной переменной, но сути метода это не изменяло, так как передвигалось место, оставленное под сохраненное значение). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом. Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и так далее, где h - положительная константа. Таким образом формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно. Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1. В настоящее время неизвестна последовательность hi, hi-1, hi-2, ..., h1, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что hi+1=3hi+1, а h1=1. Начинается процесс с hm-2, где m - наименьшее целое такое, что hmі n. Другими словами hm-2 первый такой член последовательности, что hm-2і [n/9]. Теперь запишем алгоритм: Step := 1; while Step < N div 9 do Step := Step*3 + 1; Repeat for k := 1 to Step do begin i := Step + k; while i <= N do begin x := A^[i]; j := i - Step; while (j >= 1) and (A^[j]>x) do begin A^[j + Step] := A^[j]; Dec(j); end; A^[j + Step] := x; Inc(i, Step); end; end; Step := Step div 3; until Step=0; Как показывают теоретические выкладки, которые мы приводить не будем, сортировке методом Шелла требуется в среднем 1,66n1,25 перемещений. Быстрая сортировка (метод Хоара) Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым методом сортировки из тех, что оперируют сравнениями. Суть этого метода заключается в том, чтобы найти такой элемент сортируемой последовательности, который бы делил последовательность на две части так, что слева от него находились бы элементы не меньшие его, а справа – не большие. Поиск такого элемента можно организовать многими способами. Установим два индекса на 1-ый (индекс ί) и на последний (индекс ј) элемент последовательности. Затем пока элемент с индексом ј меньше или равен элементу с индексом ί, будем уменьшать ј на 1. Если же элемент с индексом ј больше или равен элементу с индексом ί, то меняем местами элементы с индексами ί и ј. Затем, пока элемент с индексом ј меньше или равен элементу с индексом ί, будем увеличивать ί на 1. Если же элемент с индексом ј больше или равен элементу с индексом ί, то меняем элемент с индексом ί на ј. Этот процесс продолжается до тех пор, пока ј не станет равным ί. Элемент с индексом ί = ј и есть искомый. Сортировка бинарным деревом Бинарным (двоичным) деревом называют упорядоченную структуру данных, в которой каждому элементу данных поставлены в соответствие до трех других элементов: левый и правый преемник и предшественник. Левый преемник должен быть больше, а правый – меньше или равен предшественнику. Единственный элемент, не имеющий предшественника, называется корнем дерева. Если по исходной последовательности данных построить бинарное дерево, а затем вывести его элементы по определенным правилам обхода дерева, то полученная в результате последовательность окажется отсортированной. Правила обхода дерева: Обход начинается с корня, предыдущим элементом считается верхний; Если предыдущий элемент – верхний, то если левый преемник существует, то переход к этому элементу, в противном случае вывод текущего элемента данных и если правый приемник существует, то переход к этому элементу, в противном случае переход к предшественнику; Если предыдущий элемент – левый, то вывод текущего элемента и если правый приемник существует, то переход к правому преемнику, в противном случае переход к предшественнику; Если предыдущий элемент – правый, то переход к предшественнику; Обход заканчивается после вывода последнего элемента, по счетчику. Сортировка бинарным деревом – это нерекрусивная быстрая сортировка. При рекурсивной быстрой сортировке дерево автоматически строится и обходится в сетке. Сортировка массивом (хеширование) Сортировка массивом – это самый быстрый метод сортировки, однако существует множество существенных недостатков. Суть метода заключается в заполнении вспомогательного массива, содержащего элементы несколько больше, чем исходная последовательность. Заполнение этого вспомогательного массива происходит таким образом: вычисляются значения некоторой монотонной функции, называемой хэш-функция, на элементах сортируемой последовательности и эти значения считаются индексами этих элементов в заполняемом массиве. Если же окажется, что подлежащий заполнению элемент вспомогательного массива уже занят, то происходит сдвиг соответствующих элементов этого массива так, чтобы образовалось "окно” для вносимого элемента и сохранялась упорядоченность между элементами. Функция должна выбираться так, чтобы ее значения лежали внутри диапазона индексов вспомогательного массива. Например, если известно, что сортируемая последовательность состоит из натуральных чисел от 1 до N, то в качестве искомой функции можно взять , . В общем случае, в качестве такой функции рекомендуется взять: , где A – это исходная последовательность (массив), Max(A) и Min(A) максимальный и минимальный элемент A,B – это вспомогательный массив, а Size(B) – это его размер. Эта монотонная (почти линейная) функция гарантирует, что ее значение на элементах сортируемого массива будут лежать в диапазоне от 1 до Size(B). Она определена только при Max(A) ≠ Min(A). Если же Max(A) = Min(B), то это означает, что массив состоит из одинаковых элементов, то есть он отсортирован. Обменная поразрядная сортировка Этот метод, совершенно отличен от всех схем сортировки, которые рассматривались прежде; в нем используется двоичное представление ключей, и потому он предназначен исключительно для двоичных машин. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли 0 или 1 отдельные биты ключа. В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструю сортировку. Так как он зависит от разрядов ключа, представленного в двоичной системе счисления, мы называем его "обменной поразрядной сортировкой". В общих чертах этот алгоритм можно описать следующим образом: Последовательность сортируется по старшему значащему двоичному биту так, чтобы все ключи, начинающиеся с 0, оказались перед всеми ключами, начинающимися с 1. Для этого надо найти самый левый ключ Ki, начинающийся с 1, и самый правый ключ Kj, начинающийся с 0, после чего Ri и Rj меняются местами, и процесс повторяется, пока не станет i > j. Пусть F0—множество элементов, начинающихся с 0, а F1—все остальные. Применим к F0 поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F0 не будет полностью отсортировано; затем проделаем то же с F1. Алгоритм обмена по разрядной сортировки: Записи R1, . . . , RN переразмещаются на том же месте; после завершения сортировки их ключи будут упорядочены:K1 ≤ . . . ≤ KN. Предполагается, что все ключи—m-разрядные двоичные числа (a1 a2 . . . am)2; i-й по старшинству бит ai называется "бит i" ключа. Требуется вспомогательный стек, вмещающий до m − 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями. Итак, я изучила восемь методов сортировки. Можно сделать вывод, что не существует одного единственного самого оптимального алгоритма сортировки. Найти оптимальный алгоритм, не привязываясь при его выборе к условию задачи невозможно. Какой алгоритм, из множества известных сейчас самый быстрый? Ответа на этот вопрос не существует. Нет самого оптимального алгоритма в абстрактном смысле. Выбор его очень сильно зависит от условия задачи, которую необходимо решить.(......) |
Loading
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||