В данной публикации мы рассмотрим один из алгоритмов сортировки "Insertion Sort".
Название алгоритма говорит само за себя: "Insertion Sort" - "Сотрировка вставкой".
Одна из наболее часто встречающихся задач практикующего программиста - это именно сортировка какого-то массива данных, т.е. массива элементов где каждый элемент имеет "ключ" по которому будет проводиться сортировка.
В большинстве случаев даже не обязательно знать досконально структуру элементов, но необходимо знать "ключ" по которому производится сортировка и иметь доступ к нему.
Рассмотрим пример где элементы массива - это целые натуральные числа, т.е. значение элемента и есть ключ к сортировке.
На самом деле это может быть все что угодно: это могут быть структуры, в которых одно из полей содержит "ключ" сортировки, и потом не обязательно чтобы "ключ" был числом, это могут быть целые слова или же первые буквы слов.
Ещё один параметр для функции, которая будет делать сортировку - это количество элементов массива.
Итак, как уже было сказанно "Insertion Sort" - "Сотрировка вставкой".
Дано: 1. На входе - массив элементов, где ключ к сортировке - целое число.
2. Количество элементов массива - N
Задача: На выходе - массив состоящий из тех же элементов, что и массив на входе,
элементы массива отсортированны в возрастающем порядке.
Алгоритм:
1.) - Определим вспомогательный элемент, того же типа что и элементы массива.
2.) - Поделим весь массив на две части: уже отсортированная часть, и остаток который ещё надо сортировать.
3.) - Установим указатель на последний элемент отсортированной части и указатель на первый элемент на неотсортированную часть.
4.) - До тех пор пока существует несортированная часть массива
а.) - установим индекс на первый элемент из неотсортированной части и скопируем его во вспомогательный элемент.
б.) - до тех пор пока существует отсортированная часть массива И (AND) актуальное значение элемента отсортированной части больше значения временного элемента сдвигаем (копируем) элементы в сторону неотсортированной части, тем самым увеличивая на 1 размер уже упорядоченной части.
в.) - копируем в элемент на который указывает индекс значение вспомогательного элемента, увеличиваем размер отсортированной части, возвращаемся к 4.)
Теперь как это сделать на практике: (Рассмотрим пример работы этого алгоритма на языке С.)
int array[10] = {30, 70, 40, 10, 50, 100, 20, 90, 60, 80}; // массив с именем array состояший из 10 элементов
-- -- -- -- -- --- -- -- -- --
|30|70|40|10|50|100|20|90|60|80| array
-- -- -- -- -- --- -- -- -- --
Функция сортировки Insertion Sort
void InsertionSort(int *array, unsigned n)
{
unsigned i, j;
int tmp;
for (i = 0; i < n-1; i++)
{
j = i+1;
tmp = array[j];
while(j > 0 && array[j-1] > tmp)
{
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
return;
}
Итак, разберем эту функцию. Функция имеет два параметра:
- int *array - указатель на первый элемент массива
- unsigned n - беззнаковое целое число, номер элементов массива
Далее определяем две локальные переменные типа unsigned (i и j) для перебора элементов массива, которые мы и будем использовать как индескы элементов массива, одну локальную переменную типа int (tmp) - это и есть вспомогательнвй элемент, он должен быть того же типа, как и элементы массива.
Отследим наш алгоритм:
1.Определим вспомогательный элемент,того же типа что и элементы массива.
Переменная int tmp;
2.Поделим весь массив на две части: уже отсортированная часть, и остаток который ещё надо сортировать. Сначала отсортированной части не существует, точнее мы предполагаем, что массив состоит из только одного элемента, расположенного по индексу 0 (array[0]) и значит он уже отсортирован.
3.Установим указатель на последний элемент отсортированной части. Устанавливает переменную i=0 и таким образом делим массив, т.е. элемент 0 уже стоит на своем месте, все остальное (от 1 до n-1) - это материал для сортировки. Далее мы будем устанавливать j на первый элемент несортированной части массива.
4.До тех пор пока существует несортированная часть массива Это цикл for (i = 0; i < n-1; i++).
Неотсортированная часть - это все то что находится после элемента с индексом 0 и до n.
Цикл запускаем от 0 и до n-1, т.к. переменная j указывает на первый элемент несортированной части массива (см. далее), который следует сразу за i. Таким образом, на последнем шаге, когда i будет указывать на предпоследний элемент, j укажет на следующий за ним, т.е. на единственный оставшийся последний элемент массива.
а.) - установим индекс на первый элемент из неотсортированной части и скопируем его во вспомогательный элемент.
j = i+1; // j указывает на первый элемент неотсортированной части
tmp = array[j]; // скопировали во вспомагательную переменную значение элемента
// на который указывает индекс j
б.) - до тех пор пока существует отсортированная часть массива И (AND) значение элемента отсортированной части на которую указывает индекс больше значения временного элемента, сдвигаем (копируем) элементы в сторону неотсортированной части, тем самым увеличивая на 1 размер уже упорядоченной части.
while(j > 0 && array[j-1] > tmp)
{
array[j] = array[j-1];
j--;
}
На первом шаге этого цикла array[j] - это первый элемент неотсортированной части, array[j-1] - это последний элемент отсортированной части. Если условие цикла while(j > 0 && array[j-1] >= tmp) выполняется, то в array[j] будет скопированно значение предыдущего элемента и т.д. пока не найдется элемент, который меньше или равен значению вспомогательного элемента, или пока не будет достигнут первый элемент, т.е. array[0]. В любом случае, то значение, которое будет находиться по адресу array[j] будет так же и по адресу array[j+1] и значения всех последущих элементов будут большими чем значение вспомогательной переменной tmp.
в.) - копируем в элемент на который указывает индекс значение вспомогательного элемента, увеличиваем размер отсортированной части, возвращаемся к 4.)
array[j] = tmp;
размер отсортированной части увеличивается в цикле for и там же проверяется условие и переход к 4.)
Теперь вся программа:
#include <stdio.h>
#define NUM_ELEM 10
void InsertionSort(int *, unsigned );
void PrintArray(int *array, unsigned n); //Эта функция для печати содержимого массива int main()
{
int array[NUM_ELEM] = {30, 70, 40, 10, 50, 100, 20, 90, 60, 80};
printf("ARRAY\n");
PrintArray(array, NUM_ELEM);
InsertionSort(array, NUM_ELEM);
printf("\n\nSORTED ARRAY\n");
PrintArray(array, NUM_ELEM);
return 0;
}
void InsertionSort(int *array, unsigned n)
{
unsigned i, j;
int tmp;
for (i = 0; i < n-1; i++)
{
j = i+1;
tmp = array[j];
while(j > 0 && array[j-1] > tmp)
{
array[j] = array[j-1];
j--;
}
array[j] = tmp;
}
return;
}
void PrintArray(int *array, unsigned n)
{
int i;
for (i=0; i<n; i++)
printf("[ %d ] = %d\n", i, array[i]);
return;
}
/***********************************/
Стоит отметить, что алгоритм Insertion Sort является линейным и не всегда целесообразно использовать именно его для сортировки массивов, поскольку здесь операция "копия" содержимого элемента будет совершена очень много раз.
Даже если элемент находится на правильной позиции и не должен быть "передвинут", он все равно будет скопирован во временный элемент (tmp) и потом опять перекопирован на свое же место. Например, в случаях, когда элементы имеют существенный "вес", использование этого алгоритма не советуется.
Алгоритм Insertion Sort может быть использован в случаях, когда элементы запрашивают небольшой объем памяти и операция копирования не вызывает особых трудностей ни для ПК ни для ОС ни для Hardware.
Об альтернативных алгоритмах сортировки в наших следующих публикациях.
