Сортировка методом прямого выбора
Сортировка выбором – один из самых простых методов сортировки. Его суть заключается в следующем: в массиве отыскивается элемент с наименьшим ключом и меняется местами с первым элементом массива 
. На следующей итерации находится второй наименьший элемент и меняется со вторым элементом массива 
. Итерации обмена продолжаются до тех пор, пока весь массив не будет отсортирован (всего потребуется выполнить 
итераций). Время сортировки выбором пропорционально 
.
Пример сортировки выбором массива 
( 
) приведен на рисунке 5.6.
| Итерация i | Результат сортировки | |||||||
| 1 | 40 | 61 | 8 | 38 | 112 | 10 | 
| 83 |
| 2 | 3 | 61 | 
| 38 | 112 | 10 | 40 | 83 |
| 3 | 3 | 8 | 61 | 38 | 112 | 
| 40 | 83 |
| 4 | 3 | 8 | 10 | 
| 112 | 61 | 40 | 83 |
| 5 | 3 | 8 | 10 | 38 | 112 | 61 | 
| 83 |
| 6 | 3 | 8 | 10 | 38 | 40 | 
| 112 | 83 |
| 7 | 3 | 8 | 10 | 38 | 40 | 61 | 112 | 
|
| Итог: | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 |
Рис. 5.6. Пример сортировки выбором
– минимальный элемент в диапазоне поиска;
– заменяемый на i-й итерации элемент;
| – левая граница сортировки
К недостаткам метода можно отнести то, что время сортировки не зависит от упорядоченности исходного файла – практически отсортированный файл и файл с случайной последовательностью элементов будут сортироваться приблизительно одинаковое время. Главным превосходство метода над другими является минимальное число перемещений при сортировке. Этому методу отдают предпочтение при сортировке данных большого размера – в этом случае затраты ресурсов на перезапись данных существенно превосходят затраты на сравнение ключей.
|
|
|
Сортировка слиянием
Под слиянием понимается двух и более упорядоченных массивов в единый упорядоченный массив.
Один из самых простых способов слияния – последовательное сравнение наименьших элементов массива с целью определения наименьшего из них. Найденный элемент выводится (или заносится в дополнительный массив), и процедура повторяется с оставшимися в массивах элементами. Пример слияния двух упорядоченных массивов 
) и 
( 
приведен на рисунке 5.7.
| Результат слияния: | Сливаемые массивы: | |
| ||
| 5 | 
| |
| 
| |
| 
| |
| 
| |
| 
| |
|
Рис. 5.7. Пример слияния двух массивов
– минимальный элемент
Сортировка методом простого слияния
Суть метода заключается в следующем: сортируемый массив разбивается на подмассивы таким образом, что в каждом подмассиве содержится один элемент исходного массива, число подмассивов – 
. Полученные подмассивы попарно сливаются на каждой следующей итерации до тех пор, пока не будет получен один отсортированный массив размерностью .
|
|
|
Пример сортировки методом простого слияния массива ( ) приведен на рисунке 5.8.
[40] [61] [8] [38] [112] [10] [3] [83]
[40 61] [8 38] [10 112] [3 83]
[8 38 40 61] [3 10 83 112]
[3 8 10 38 40 61 83 112]
Рис. 5.8. Пример сортировки методом простого слияния
Метод простого слияния считается одним из самых простых среди быстрых методов сортировки. Вычислительная сложность алгоритма оценивается как 
.
Поразрядная сортировка
Поразрядными методами сортировки называются методы, построенные на обработке чисел по одной позиции (одному разряду) за итерацию. Эти методы обрабатывают и сравнивают не весь ключ целиком, а его часть. Отличительной особенностью данной группы методов является то, что они не используют сравнений ключей.
Приято выделять два базовых подхода к поразрядной сортировке. В первом случае ключи рассматриваются слева направо (от старших разрядов к младшим), во втором – справа налево (от старших разрядов к младшим). Первая группа методов получила название MSD (most significant digit radix sort – поразрядная сортировка по старшей цифре), вторая – LDS (least significant digit radix sort – поразрядная сортировка по младшей цифре).
|
|
|
Важными параметрами поразрядной сортировки являются:
– количество разрядов самого длинного ключа;
– количество возможных значений каждого разряда ключа.
MSD и LSD сортировки
Первым шагом методов поразрядной сортировки является разбиение ключа на разряды (для слов – это буквы, для чисел – цифры). Далее на каждой итерации ключи сортируются по одному из разрядов. Для метода LSD предполагается рассмотрение всех ключей едином списком. Для MSD сортировки после каждой итерации исходный массив разбивается на подмассивы, состоящие из элементов, в которых значение разряда последней сортировки одинаково. В массивах, состоящих из одного элемента сортировка не выполняется.
Пример сортировки массива ( ) методами MSD (a) и LSD (б) приведен на рисунке 5.9.
Для рассматриваемого примера 
, 
.
| Исходная последовательность | Результат итерации 1 | Результат итерации 2 | Результат итерации 3 |
| 4 0 | 4 0 | 3 | 3 |
| 6 1 | 1 0 | 8 | 8 |
| 8 | 6 1 | 10 | 10 |
| 3 8 | 1 1 2 | 1 12 | 38 |
| 1 1 2 | 3 | 38 | 40 |
| 1 0 | 8 3 | 40 | 61 |
| 3 | 8 | 61 | 83 |
| 8 3 | 3 8 | 83 | 112 |
а) LSD-сортировка
| Исходная последовательность | Результат итерации 1 | Результат итерации 2 | Результат итерации 3 |
| 4 0 | 4 0 | 8 | 3 |
| 6 1 | 6 1 | 3 | 8 |
| 8 | 8 | 1 0 | 10 |
| 3 8 | 3 8 | 3 8 | 38 |
| 1 1 2 | 1 0 | 4 0 | 40 |
| 1 0 | 3 | 6 1 | 61 |
| 3 | 8 3 | 8 3 | 83 |
| 8 3 | 1 1 2 | 11 2 | 112 |
б) MSD-сортировка
|
|
|
Рис. 5.9. Пример работы методов поразрядной сортировки
Дробление массива на подмассивы меньшей размерности на каждой итерации сортировки MSD позволяет существенно сократить вычислительные затраты так как работа с такими массивами требует меньше операций сравнения и не выполняется совсем для массивов, состоящих из одного элемента.
При поразрядной сортировке можно обеспечить алфавитный порядок следования ключей (например, c, cd, fa, g, gr, ...). Для этого необходимо произвести выравнивание ключей сортировки по старшему разряду (рис. 5.10).
| Исходная последовательность | Результат итерации 1 | Результат итерации 2 | Результат итерации 3 |
| c a t | m y | a | a |
| d o g | o n | c at | ant |
| m y | a | o n | cat |
| a n t | d o g | a nt | dog |
| s u n | s u n | d og | my |
| o n | s o n | s on | on |
| s o n | c a t | s un | son |
| a | a n t | m y | sun |
а) LSD-сортировка
| Исходная последовательность | Результат итерации 1 | Результат итерации 2 | Результат итерации 3 |
| c a t | a n t | a | a |
| d o g | a | an t | ant |
| m y | c a t | ca t | cat |
| a n t | d o g | do g | dog |
| s u n | m y | my | my |
| o n | o n | on | on |
| s o n | s u n | so n | son |
| a | s o n | su n | sun |
б) MSD-сортировка
Рис. 5.10. Пример работы методов поразрядной сортировки для сортировки элементов в алфавитном порядке
Методы поиска информации
Как и в случае с сортировкой, методы поиска предполагают работу с данными, разделенными на записи (элементы), каждая из которых имеет уникальную характеристику – ключ. Цель поиска – получение элемента с ключом, соответствующем заданному ключу поиска.
Значимость операции поиска сложно переоценить. Она привлекала большое внимание специалистов-информатиков еще на заре компьютерной техники. В ту пору многие математические вычисления сводились к процедуре поиска (отыскание нужных значений в таблицах логарифмов, тригонометрических и иных таблицах). Широкое внедрение вычислительных машин в процесс решения научных задач в некоторых случаях заменили поиск на многократное повторное вычисление одних и тех же значений функций. Однако в некоторых случаях оказалось выгоднее не отказываться от поиска данных по таблицам.
Основная проблема, с которой сталкивались ученые при разработке методов поиска, заключалась в ограниченном доступе к данным (например, при хранении информации на лентах был возможен только последовательный однонаправленный доступ). В таких условиях эффективный поиск был невозможен. Разработка новых видов устройств памяти с произвольным доступом в 50-х года прошлого века привела к прорыву в области разработки методов поиска. Исследования в данной области не потеряли свою актуальность и в настоящее время.
Сегодня операция поиска в той или иной степени используется практически во всех программах. При этом данная процедура считается наиболее времязатратной ее частью. В связи с этим, разработка эффективных методов поиска позволяет существенно увеличить скорость работы таких программ.
Аналогично методам сортировки, методы поиска можно разделить на внутренние (когда данные хранятся в оперативной памяти) и внешние (данные располагаются на внешних носителях).
По принципу действия методы поиска могут быть разделены на две группы:
· методы, основанные на сравнении ключей (последовательный, бинарный, интерполяционный, по бинарному дереву и пр.);
· методы, основанные на цифровых свойствах ключей.
К первой группе метод
Постановка задачи поиска
Пусть имеется последовательность из элементов
.
Каждой 
записи последовательности поставлен в соответствие ключ 
.
Наряду с ключом, элементу может соответствовать иная информация, не влияющая на процесс поиска.
Ставится задача: отыскать в множестве 
элемент 
, ключ 
которого совпадает с ключом поиска 
.
Процедура поиска может быть завершена в двух случаях:
· ключ найден;
· проверены все элементы множества и элемент с ключом отсутствует во множестве.
Дата добавления: 2020-01-07; просмотров: 297; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!