
Алгоритмы сортировок и их реализации
	Главная

Меню сайта

Статистика

Наш опрос

Сортировка вставками (простыми включениями)

Сортировка вставками (англ. insertion sort) — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

прост в реализации
эффективен на небольших наборах данных
эффективен на наборах данных, которые уже частично отсортированы
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)
может сортировать список по мере его получения

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

Реализация на C

typedef int array_type; /* или typedef char array_type;*/

void insertSort(array_type a[], int length) {
int i, j;
array_type value;
for (i = 1; i < length; i++) {
value = a[i];
for (j = i-1; (j >= 0) && (a[j] > value); j--) {
a[j+1] = a[j];
}
a[j+1] = value;
}
}

Реализация на C++

void insertSort(int a[],int length_a) {
int i,j,value;
for(i = 1; i < length_a; i++) {
value = a[i];
for (j = i-1; (j >= 0) && (a[j] > value); j--){
a[j+1] = a[j];
}
a[j+1] = value;
}
}

Реализация на PASCAL

{Arr = Array [1..Count]}

For i:=2 to Сount do
Begin
Tmp:=Arr[i];
j:=i-1;
While (j>0) and (Arr[j]<Tmp) do
Begin
Arr[j+1]:=Arr[j];
j:=j-1;
End;
Arr[j+1]:=Tmp;
End;

Литература

Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Сортировка вставкой // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 206-209. ISBN 0-201-74395-7
Википедия

Создать бесплатный сайт с uCoz