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

Алгоритм сортировки основан на вставке очередного элемента в надлежащее место уже отсортированной до этого части массива. Пусть в массиве A содержится n элементов. Отсортируем массив по возрастанию. По массиву A необходимо выполнить n-1 проход.

Рассмотрим i-ый проход (1£ i £ n-1, один нулевой элемент изначально считаем отсортированным). Подмассив A[0]…A[i-1] уже отсортирован по возрастанию. В качестве вставляемого выберем элемент A[i], поместим его в переменную buf, и будем продвигаться к началу массива, сравнивая buf с элементами A[i-1], A[i-2] и т.д. Пока эти элементы больше buf, они перемещаются на одну позицию вправо (A[j]=A[j-1]). Просмотр заканчивается на элементе A[j], который меньше или равен buf, или дошли до начала массива (j = -1). Когда подходящее место для элемента A[i] найдено, он вставляется в позицию j+1.

Процесс сортировки рассмотрим на примере пятиэлементного целочисленного массива 9, 3, 5, 10, 7. Число элементов в массиве n = 5, проходов требуется n-1 = 4.

Исходный массив:

1-проход: подмассив A[0] отсортирован,

A[1]=3 → buf; A[0] → A[1]; buf → A[0]

2-проход: подмассив A[0]…A[1] отсортирован,

A[2]=5 → buf; A[1] → A[2]; buf → A[1]

3-проход: подмассив A[0]…A[2] отсортирован,

A[3]=10 → buf; buf → A[3]

4-проход: подмассив A[0]…A[3] отсортирован,

A[4]=7 → buf; A[3] → A[4]; A[2] → A[3]; buf → A[2]

Массив A отсортирован по возрастанию.

ПРИЛОЖЕНИЕ 2. Создание файла с результатами препроцессорной обработки в среде Visual Studio

1. В окне Обозреватель решений Visual Studio выберите проект.

2. В обозревателе решений щёлкните правой кнопкой мыши по узлу проекта и выберите пункт Свойства (Properties).

3. В окне Property Pages выберите пункт С/С++:

4. Щёлкните для выбора страницы свойств Preprocessor (Препроцессор). Измените значение свойства Generate Preprocessed File (Создание предварительно обработанного файла) с No на Without Line Numbers (/EP /P):

Нажмите на кнопки Применить и ОК.

5. Нажмите функциональную клавишу F7. Пусть имя проекта pr1, а имя файла с программой pr1.cpp. Тогда в папке pr1/pr1 появится файл pr1.i с результатами препроцессорной обработки, но файл pr1.obj не создаётся. Чтобы создать файлы pr1.obj и pr1.exe, надо в странице Preprocessor вернуть установку значения свойства Generate Preprocessed File на No и скомпилировать программу (нажать F7, Build Solution). Чтобы выполнить программу, нажмите Ctrl+F5.