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

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

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

Минусом же является высокая сложность алгоритма: O(n²).

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

Пример:

int* InsertSort(int* Array, int SizeArray)
{
    int i=0;
    int tmp=0;
    int j=0;

    for(i=1; i<SizeArray; i++)
    {
        tmp=Array[i];
        for(j=i-1; j>=0; j--)
        {
            if(tmp<Array[j])
                break;
            Array[j+1]=Array[j];
            Array[j]=tmp;
        }
    }

    return Array;
}

---

Wiki: Сортировка вставками