Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Сортировка данных.
Сортировка - важная часть вычислительной математики и отнимает значительную часть времени работы компьютера. Сортировка относится к алгоритмам обработки таблиц (массивов) любого типа.
Сортировка данных - это обработка информации, в результате которой элементы ее (записи) располагаются в определенной последовательности в зависимости от значения некоторых признаков элементов этой информации.
Наиболее распространенным видом сортировки данных является упорядочение массива - расположение записей сортируемого массива данных в порядке монотонного изменения некоторого ключевого признака. Сортировка данных позволяет сократить во много раз продолжительность решения задач, которые связаны с обработкой больших массивов информации. С отсортированными данными легче работать. Когда элементы отсортированы, как в телефонном справочнике, их проще найти, обновить, исключить.
Смысл любой сортировки заключается в перестановке элементов таблицы в определенном заданном порядке. Упорядочение осуществляется в процессе многократного просмотра исходного массива. Обычно методы сортировки подразделяют на два класса:
- внутренняя сортировка, когда все записи хранятся в быстрой оперативной памяти;
- внешняя сортировка, когда все записи в ней не помещаются.
Методы внутренней сортировки обеспечивают большую гибкость при построении структур данных и доступа к ним. Для внутренней сортировки характерно небольшое количество записей и весь процесс можно провести в оперативной памяти компьютера с большим быстродействием.
Внешние методы обеспечивают достижение нужного результата в условиях ограниченных ресурсов, поэтому в существующих методах внешней сортировки время обращения к внешней памяти занимает значительную часть общего времени сортировки. Следовательно, важной целью методов внешней сортировки данных является минимизация количества просмотров сортируемого массива, записанного во внешней памяти, используемой, как правило, в режиме последовательной выборки.
Невозможно назвать алгоритм сортировки универсально наилучшим в любой ситуации. Имеется много наилучших способов, но только в случаях, когда известно, что сортируется и с какой целью. Эффективность алгоритма зависит от множества факторов:
– количества элементов, участвующих в сортировке;
– возможности помещения всех элементов в доступную область или в доступный интервал;
– степени первоначальной отсортированности элементов;
– диапазона и распределения значений сортируемых элементов;
– записи элементов в файл или массив;
– предположения, будут ли элементы периодически исключаться или
дополняться;
– возможности сравнения элементов параллельно.
Сортировать можно любые данные, однако важно, чтобы их можно было сравнить тем или иным способом. Отсортировать числовую таблицу – это означает переставить элементы в ней так, чтобы они расположились в порядке убывания (возрастания) значений с возрастанием (убыванием) нового номера элемента.
Сортировка символьной (текстовой) информации заключается в упорядочении значений (текстовых строк) по алфавиту. Метод сортировки является устойчивым, если относительный порядок элементов с равными значениями не меняется после упорядочения. Сортировку можно рассматривать и как самостоятельную задачу (например, для получения упорядоченного по алфавиту списка сотрудников какого-либо учреждения), и как вспомогательную – для облегчения последующего поиска элементов в упорядоченной таблице или массиве.
2.1 Простой выбор
Идея метода простого выбора заключается в следующем: выделяется наименьший (наибольший) элемент массива и отделяется от остальных. Далее снова выделяется наименьший (или наибольший) из оставшихся и т.д.
Например, расположить элементы последовательности А1, А2,…,АN в порядке убывания. Найти в массиве элемент с наибольшим значением и поменять его местами с первым элементом. Далее те же действия выполнить с остальными N-1 элементами массива, затем N-2 элементами и т.д., пока не останется один элемент – последний, наименьший.
Допустим, что два первых элемента являются упорядоченными. Необходимо отыскать максимальный элемент среди остальных. Если несколько элементов последовательности оказываются равными, то следует найти первый среди максимальных элементов. Таким образом можно достичь устойчивости сортировки. Найденный элемент из двух первых и третий по списку элемент следует поменять местами. Для получения результата необходимо N-1 раз найти максимальное значение в массиве, длина которого будет уменьшаться с каждым шагом на 1.
Словесный алгоритм сортировки простым выбором будет следующий:
1. Начать сортировку с первого элемента i=1.
2. Найти максимальный элемент и его номер в массиве А1, А2,…,АN;
3. Поменять местами Аi
и максимальный элемент Аk;
4. Перейти к следующему элементу i=i+1;
5. Если рассмотрены не все N-1 элементы, то повторить с п.2.
Чтобы выполнить сортировку по возрастанию, необходимо производить
те же действия, только на каждом шаге находить минимум.
Данный алгоритм является простым для реализации, работает достаточно быстро, если последовательность частично упорядочена, а также при малых значениях N.
2.2 Простой обмен
Идея метода простого обмена заключается в следующем: если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены.
Любой метод сортировки так или иначе связан с обменом – перестановкой двух элементов в памяти. Для обменной сортировки это основная характеристика процесса. Принцип сортировки простым обменом заключается в многократном сравнении элементов массива, стоящих рядом, и перестановке этих элементов в заданном порядке. Таким образом, соседние элементы А1 и А2, А2 и А3, А3 и А4, А4… поочередно сравниваются. Если Аi-1 > Аi, то элементы меняются местами.
Если представить, что элементы таблицы – это пузырьки в сосуде с водой, каждый с весом, равным ему по значению, то каждый проход с обменом снизу вверх по таблице приводит к «всплыванию пузырька» на соответствующий его весу уровень. Благодаря такой аналогии сортировка простым обменом получила название пузырьковой сортировки.
Составим алгоритм для решения этой задачи. Основная часть алгоритма – цикл, который должен выполниться за N-1 раз. Выбор границ 1 и (N-1) или 2 и N влияет только на задание индексов сравниваемых элементов.
Словесный алгоритм выглядит следующим образом:
1. i = 2;
2. Сравнить попарно элементы АN, АN-1,…, Аi
, Аi-1;
3. i = i+1$
4. Если i <=N, то повторить с п.2.
Для организации цикличности сравнения в схеме алгоритмов можно использовать цикл с параметром, который зависит от i , так как при каждом новом проходе по таблице длина ее будет уменьшаться.
Алгоритм обменной сортировки осуществляет максимально возможное количество сравнений, много раз приходится просматривать список и выполнять много перестановок. Это дает повод считать данный алгоритм неэффективным.
2.3 Простые вставки
Идея метода простых вставок заключается в следующем: элементы просматриваются по одному. Каждый новый элемент вставляется в подходящее место среди ранее упорядоченных элементов. Сортировки простым выбором и простым обменом относятся к сортировкам с убывающим шагом. Сортировка простыми вставками работает со списком неупорядоченных целых чисел и сортирует их в порядке возрастания.
Отсортированный список вначале пуст. На каждом шаге первое число из неотсортированного списка удаляется и помещается в отсортированный список на соответствующее место. Для этой цели отсортированный список должен каждый раз быть просмотрен, начиная с наименьшего числа и до тех пор, пока нужное место не будет найдено. При этом все реорганизации списка происходят в одном списке. Алгоритм заканчивает свою работу, когда элемент, стоящий до сих пор на последнем месте, будет вставлен на соответствующее место в отсортированном списке.
Основой алгоритма вставок является цикл, который должен определить, для какого элемента последовательности следует найти место в левой упорядоченной части.
Обобщенный алгоритм вставок выглядит следующим образом:
1. i=2;
2. Найти место Аk для Аi
в упорядоченной последовательности, где уже
находится Аi-1;
3. Выполнить сдвиг элементов Аk+1, Аk+2,…, Аi+1 вправо;
4. Поставить элемент Аi
на нужное место (Аk = X, если X определено);
5. i = i+1;
6. Если i<=N, повторить с п.2.
Сложность данного алгоритма зависит от того, какой алгоритм поиска используется для определения места выделенному элементу в новом массиве.
Метод прост для программной реализации и является достаточно эффективным при малых значениях N, не требует дополнительного объема памяти. При больших значениях N алгоритм становится очень медленным.