Перейти к содержимому

Сортировка вставками, элементы и алгоритм массив и include, int

Здравствуйте дорогие пользователи! В предыдущей записи этой категории мы разобрались с сортировкой пузырьком,сегодня же я хотел бы рассмотреть еще одну сортировку данных – сортировку вставками.
Алгоритм сортировки вставками, состоит из 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²

Плюсы данной сортировки: алгоритм эффективен при работе со списками, алгоритм отлично справляется с массивами небольшого размера, может работать с последовательно поступающими данными.

1.7/5 - (4 голоса)
Спасибо что пользуетесь сайтом best-exam. Поделитесь сайтом с друзьями!