Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

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

· прост в реализации

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим

· эффективен на наборах данных, которые уже частично отсортированы

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы)

· может сортировать список по мере его получения

· не требует временной памяти, даже под стек

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

//Описание функции сортировки методом простого включения

void InsertSort (int k,int x[max]) {

int i,j, temp;

for (i=0;i<k;i++) {

//цикл проходов, i - номер прохода

temp=x[i];

//поиск места элемента

for (j=i-1; j>=0 && x[j]>temp; j--)

x[j+1]=x[j];//сдвигаем элемент вправо, пока не дошли

//место найдено, вставить элемент

x[j+1]=temp;

}

}

Задания

1.Отсортируйте по возрастанию методом «пузырька» одномерный целочисленный массив, заданный случайными числами на промежутке [-100; 100). Выведите на экран исходный и отсортированный массивы.

2.Отсортируйте по возрастанию методом простого выбора одномерный вещественный массив, заданный случайными числами на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.

3.Отсортируйте по возрастанию методом простого включения одномерный целочисленный массив, заданный с клавиатуры. Выведите на экран исходный и отсортированный массивы.

Домашние задания

1.Отсортируйте по убыванию методом простого обмена одномерный целочисленный массив, заданный случайными числами на промежутке [-100; 100).

2.Отсортируйте по убыванию методом простого выбора одномерный вещественный массив, заданный случайными числами на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.

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

4. Индивидуальное задание. Номер варианта определяется по журналу. Напишите программу, оформив её в виде функций генерации, вывода и обработки массивов. Предусмотрите ввод количества элементов массива и ввод границ диапазона случайных чисел с клавиатуры. Для решения задания используйте «однопроходные» алгоритмы, позволяющие получить результат после однократного просмотра массива.

Варианты индивидуального задания