Сортировка вставками (простыми включениями)
Сортировка вставками (англ. 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;
|
Литература
|
