Уроки C++

Сортировка Вставками C++

Данный вид сортировки тоже весьма прост, но в отличие от сортировки “Выбором”, в которой массив каждый раз проверяется весь заново, сортировка “Вставками”, найдя минимальный (или максимальный) элемент ставит его на первое место и далее проверяет уже массив без этого элемента, тем самым – с каждой проверкой уменьшается количество сортируемых элементов.
Предположим есть массив из 5 элементов:  4  7  3  -1  2
1)  -1    остаётся:  4  7  3  2
2)  -1  2    остаётся:  4  7  3
3)  -1  2  3    остаётся:  4  7
4)  -1  2  3  4    остаётся:  7
5) Результат:  -1  2  3  4  7

Ну а вот сам код данной сортировки:

---

#include "stdafx.h"
#include "iostream"
#include "time.h"
#include "iomanip"

using namespace std;

void InsertionSort(int *, int);   // объявление функции сортировки

int main()
{
setlocale(LC_ALL, "Russian");
int n;   // Количество элементов массива
cout << "Введите размер массива: ";
cin >> n;
cout << endl;
cout << "Массив: " << endl;
int *mas = new int [n];
srand(time(NULL));
for (int i = 0; i < n; i++)
{
mas[i] = rand() % 200 - 100;   // заполняем массив случайными числами
cout << mas[i] << " ";   // выводим массив на экран
}
cout << "\n\n";

InsertionSort(mas, n);   // вызываем функцию сортировки Вставками
cout << "Отсортированный массив: " << endl;
for (int i = 0; i < n; i++)
{
cout << mas[i] << " ";   // Вывод на экран отсортированного массива
}
cout << "\n\n";
system("PAUSE");
return 0;
}

void InsertionSort(int *sort_el, int length)   // сортировка Вставками
{
int temp,   // временная переменная, храненящая значения элемента сортируемого массива
pr;   // индекс предыдущего элемента
for (int j=1; j < length; j++)
  {
temp = sort_el[j]; // инициализируем временную переменную текущим значением элемента массива
pr = j-1;   // запоминаем индекс предыдущего элемента массива
while(pr >= 0 && sort_el[pr] > temp)   // пока индекс не равен 0 и предыдущий элемент массива больше текущего
    {
sort_el[pr + 1] = sort_el[pr];   // перестановка элементов массива
sort_el[pr] = temp;
pr--;
    }
  }
}

---

Результат:



<< К списку сортировок

---