Сортировка вставками на Си

Рассмотрим один из методов сортировки данных, который называется сортировка вставками. Будет приведен алгоритм метода и его реализация на языке программирования Си с подробными комментариями.

Главная идея метода состоит в том, что при добавлении нового элемента в уже отсортированный массив его необходимо вставлять на нужное место, вместо того, что бы ставить его в произвольное, и потом заново сортировать всю последовательность.

Рассмотрим алгоритм метода сортировки вставками на примере сортировки по возрастанию. Первый элемент в массиве образует уже отсортированную последовательность. Сравниваем второй элемент с первым. Если порядок между ними нарушен, то первый элемент передвигается на одну позицию вправо. Теперь отсортированный массив состоит из двух элементов.

Далее, в течении каждой итерации, берем следующий элемент (третий, четвертый и т.д) и сравниваем его поочередно с другими элементами в уже отсортированном списке, начиная с конца этого списка. Если порядок между сравниваемыми элементами нарушен, то меняем их местами, если нет, то “вставка” нового элемента закончена, переходим к следующему.

Сортировка вставками имеет большую вычислительную сложность. Поэтому она эффективна на небольших наборах данных. Рекомендуется использовать этот метод на наборах размером до десятков элементов. Сортировка вставками эффективна на последовательностях с данными, которые уже частично отсортированы.

Реализуем описанный выше алгоритм сортировки с помощью языка программирования Си. Напишем функцию void InsertionSort(int n, int mass[]), которая в качестве аргументов принимает: число элементов в массиве и сам массив (если быть точным, то указатель на массив).

Приведем пример консольной программы, которая считывает с клавиатуры последовательность элементов, сортирует их методом вставок и выводит отсортированный массив на экран.

Демонстрация работы программы представлена на скриншоте ниже:

Сортировка вставками на Си - vscode.ru

Скачать исходник программы можно, нажав на кнопку:

Скачать исходник

 

 

Смотрите также:

Сортировка методом выбора на языке Си

Сортировка пузырьком на Си

Сортировка методом подсчета на Си

 

Сортировка вставками на Си
5 (100%) 3 votes

Поделиться в соц. сетях:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">