Рассмотрим один из методов сортировки данных, который называется сортировка вставками. Будет приведен алгоритм метода и его реализация на языке программирования Си с подробными комментариями.
Главная идея метода состоит в том, что при добавлении нового элемента в уже отсортированный массив его необходимо вставлять на нужное место, вместо того, что бы ставить его в произвольное, и потом заново сортировать всю последовательность.
Рассмотрим алгоритм метода сортировки вставками на примере сортировки по возрастанию. Первый элемент в массиве образует уже отсортированную последовательность. Сравниваем второй элемент с первым. Если порядок между ними нарушен, то первый элемент передвигается на одну позицию вправо. Теперь отсортированный массив состоит из двух элементов.
Далее, в течении каждой итерации, берем следующий элемент (третий, четвертый и т.д) и сравниваем его поочередно с другими элементами в уже отсортированном списке, начиная с конца этого списка. Если порядок между сравниваемыми элементами нарушен, то меняем их местами, если нет, то «вставка» нового элемента закончена, переходим к следующему.
Сортировка вставками имеет большую вычислительную сложность. Поэтому она эффективна на небольших наборах данных. Рекомендуется использовать этот метод на наборах размером до десятков элементов. Сортировка вставками эффективна на последовательностях с данными, которые уже частично отсортированы.
Реализуем описанный выше алгоритм сортировки с помощью языка программирования Си. Напишем функцию void InsertionSort(int n, int mass[]), которая в качестве аргументов принимает: число элементов в массиве и сам массив (если быть точным, то указатель на массив).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
void InsertionSort(int n, int mass[]) { int newElement, location; for (int i = 1; i < n; i++) { newElement = mass[i]; location = i - 1; while(location >= 0 && mass[location] > newElement) { mass[location+1] = mass[location]; location = location - 1; } mass[location+1] = newElement; } } |
Приведем пример консольной программы, которая считывает с клавиатуры последовательность элементов, сортирует их методом вставок и выводит отсортированный массив на экран.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <stdio.h> #include <malloc.h> //сортировка вставками void InsertionSort(int n, int mass[]) { int newElement, location; for (int i = 1; i < n; i++) { newElement = mass[i]; location = i - 1; while(location >= 0 && mass[location] > newElement) { mass[location+1] = mass[location]; location = location - 1; } mass[location+1] = newElement; } } int main() { //ввод N int N; printf("Input N: "); scanf_s("%d", &N); //выделение памяти под массив int* mass; mass = (int *)malloc(N * sizeof(int)); //ввод элементов массива printf("Input the array elements:\n"); for (int i = 0; i < N; i++) scanf_s("%d", &mass[i]); //сортировка вставками InsertionSort(N, mass); //вывод отсортированного массива на экран printf("Sorted array:\n"); for (int i = 0; i < N; i++) printf("%d ", mass[i]); printf("\n"); //освобождение памяти free(mass); return 0; } |
Демонстрация работы программы представлена на скриншоте ниже:
Скачать исходник программы можно, нажав на кнопку:
Смотрите также:
Сортировка методом выбора на языке Си
Сортировка методом подсчета на Си
Поделиться в соц. сетях: