![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Обзор алгоритмов сортировкиСтр 1 из 5Следующая ⇒
Сортировка - это процесс перестановки объектов данного множества в определённом порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. Поэтому элементы сортировки присутствуют во многих задачах прикладного программирования. Рассмотрим алгоритмы сортировки " на месте", то есть те алгоритмы в которых не используется копирование массива. Удобной мерой эффективности алгоритмов сортировки " на месте" является число необходимых сравнений в ходе сортировки и число необходимых пересылок элементов. Эффективные алгоритмы сортировки требуют порядка
сравнений, где N - число элементов, а С - число необходимых сравнений. Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка
Методы сортировки " на месте" можно разбить на три основных класса: сортировка выбором сортировка вставками сортировка обменом В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется
местами предпоследним элементом и т.д. (рисунок 1).
Рисунок 1. Сортировка простым выбором
В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная - укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части (рисунок 2).
Рисунок 2. Сортировка простыми включениями
Основная характеристика сортировки обменом - перестановка местами двух соседних элементов, если они расположены не так, как требует отсортированный массив.
Рисунок 3. Сортировка простым обменом
В рассмотренной классификации существуют разные алгоритмы. Они отличаются сложностью, быстротой выполнения, последовательностью операций. Например: сортировка вставками; пузырьковая сортировка; корневая сортировка; пирамидальная сортировка; сортировка слиянием; быстрая сортировка; сортировка Шелла и др. Рассмотрим подробнее основные типы и виды сортировок (сначала простые сортировки затем более сложные).
|