Здравствуйте дорогие пользователи! В предыдущей записи этой категории мы разобрались с сортировкой пузырьком,сегодня же я хотел бы рассмотреть еще одну сортировку данных – сортировку вставками.
Алгоритм сортировки вставками, состоит из 3 простых шагов:
1. Ищем в нашей последовательности данных минимальный элемент
2. Перемещаем найденный элемент на первое место, остальные элементы сдвигаем вправо
3. Теперь уже среди N-1 элемента ищем минимальный и проделываем такие же действия
Для тех кому лень читать выше написанное смотрим реализацию сортировки в картинках ниже:
Пример сортировки вставками
Реализация алгоритма вставками на си++
#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <clocale>
using namespace std;
const int N=10;// размер массива
int main()
{
setlocale(LC_CTYPE,"rus");
srand(time(0));
int mas[N];
cout<<"Исходный массив:"<<endl;
for(int i=0;i<N;i++)
{
mas[i]=rand()%45-5;// заполняем массив случайными числами
cout<<mas[i]<<" "; // выводим его на экран
}
// собственно сортировка вставками
int x,j;
for(int i=1;i<N;i++)
{
x=mas[i];
j=i;
while((j>1) &&(x<mas[j-1]))
{
mas[j]=mas[j-1];
j--;
}
mas[j]=x;
}
cout<<endl<<"Сортировка массива вставками:"<<endl;
for(int i=0;i<N;i++)
{
cout<<mas[i]<<" ";
}
cout<<endl;
return 0;
}Результат выполнения данного кода:
Минусы и плюсы сортировки вставками
Минуса два: очень много перемещений элементов массива и высокая алгоритмическая сложность N²
Плюсы данной сортировки: алгоритм эффективен при работе со списками, алгоритм отлично справляется с массивами небольшого размера, может работать с последовательно поступающими данными.