15. Написать программу, сортирующую список студентов группы по алфавиту и использующую сортировку вставками. Теория: Сортировка вставками (Insertion sort) При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную.

15. Написать программу, сортирующую список студентов группы по алфавиту и использующую сортировку вставками.
Теория:
Сортировка вставками (Insertion sort)
При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.
На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.
Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i].
void SortAlgo::insertionSort(int data[], int lenD)
{
int key = 0;
int i = 0;
for(int j = 1;j<lenD;j++){
key = data[j];
i = j-1;
while(i>=0 && data[i]>key){
data[i+1] = data[i];
i = i-1;
data[i+1]=key;
}
}
}