Остальные алгоритмы сортировки
Топологическая сортировка
Упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого.
Внешняя сортировка
Сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам…
Идея большинства методов заключается в расчленении данных на ряд последовательностей помещающихся в оперативную память. Далее применяется один из методов внутренней сортировки, после чего последовательности сливаются. Чем больше объём оперативной памяти, тем длиннее будут последовательности и, следовательно, тем меньшим окажется их количество, что увеличит скорость сортировки. Если же объём оперативной памяти мал, то можно разделить исходные данные на несколько последовательностей, после чего непосредственно использовать процедуру слияния.
Основа алгоритма сортировки методом простых вставок
Сортировка вставками является простым алгоритмом сортировки. Хотя этот метод сортировки намного менее эффективен, чем более сложные алгоритмы, у него есть ряд преимуществ:
прост в реализации
эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим
эффективен на наборах данных, которые уже частично отсортированы
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
может сортировать список по мере его получения
не требует временной памяти, даже под стек
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Пример работы метода сортировки изображен на рис.1. На рис.1 (a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рис.1(b) для числа 1. Наконец, на рис.1(c) мы завершаем сортировку, поместив 2 на нужное место. Если длина нашего массива равна n, нам нужно пройтись по n - 1 элементам. Каждый раз нам может понадобиться сдвинуть n - 1 других элементов, получая алгоритм с временем работы O(n2).
Рисунок 1 - Процесс сортировки
Сортировка вставками относится к числу методов сортировки по месту. Другими словами, ей не требуется вспомогательная память, мы сортируем элементы массива, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой - если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.
Заключение
Целью данной курсовой работы являлось разработка и анализ алгоритма сортировки методом простых вставок на основе сортировки таблицы адресов, а также анализ зависимости среднего времени сортировки от объема сортируемых данных, что и было проделано.
Необходимо отметить, что в результате экспериментального сравнения, мы получили, что среднее время сортировки возрастает, по мере того как возрастает количество сортируемых элементов. Кроме того, экспериментально определили, что скорость сортировки методом простых вставок на основе таблицы адресов почти в два раза превышает скорость сортировки данным методом на основе перестановки данных.
Таким образом, используя алгоритм сортировки на основе сортировки таблиц адресов, мы получаем экономию времени .