Лекции
Начать
Начать обучение
JavaRush /Курсы /Harvard CS50 /Алгоритмы сортировки. Сортировка вставками

Алгоритмы сортировки. Сортировка вставками

Harvard CS50
3 уровень , 10 лекция
Открыта

Внимание! Практически весь материал этой лекции был в видеолекции.



Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.

Основная идея этого алгоритма — разделение нашего массива на две части, отсортированную и неотсортированную. На каждом шаге алгоритма число переходит от неотсортированной к отсортированной части. 

Алгоритмы сортировки. Сортировка вставками - 1

Давайте на примере ниже разберем, как работает сортировка вставкой. До того, как мы начали, все элементы считаются неотсортированными.

Алгоритмы сортировки. Сортировка вставками - 2

Шаг 1. Возьмем первое неотсортированное значение (3) и вставим его в отсортированный подмассив. На этом шаге весь отсортированный подмассив, его начало и конец и будут этой самой тройкой.

Telegram
Алгоритмы сортировки. Сортировка вставками - 3


Шаг 2. Поскольку 3 < 5, мы вставим 5 в отсортированный подмассив справа от 3.

Алгоритмы сортировки. Сортировка вставками - 4

Шаг 3. Теперь работаем над вставкой числа 2 в наш отсортированный массив. Сравниваем 2 со значениями справа налево, чтобы найти правильную позицию. Поскольку 2 < 5 и 2 < 3 и мы дошли до начала отсортированного подмассива. Следовательно, мы должны вставить 2 слева от 3. Для этого подвигаем 3 и 5 вправо, чтобы появилось место для двойки и вставляем её в начало массива.

Алгоритмы сортировки. Сортировка вставками - 5

Шаг 4. Нам повезло: 6 > 5, поэтому мы можем вставить это число сразу за числом 5.

Алгоритмы сортировки. Сортировка вставками - 6


Шаг 5. 4 < 6 и 4 < 5, но 4 > 3. Следовательно, мы знаем, что 4 нужно вставить справа от 3.

Снова мы вынуждены подвинуть 5 и 6 вправо, чтобы создать лакуну для 4. 

Алгоритмы сортировки. Сортировка вставками - 7

Готово!

Обобщенный алгоритм:

Берем каждый неотсортированный элемент n и сравниваем его со значениями в отсортированном подмассиве справа налево, пока не определим подходящую позицию для n (то есть, в тот момент, когда находим первое число, которое меньше, чем n). Затем сдвигаем все отсортированные элементы, которые находятся справа от этого числа вправо, чтобы образовалось место для нашего n, и вставляем его туда, тем самым расширяя отсортированную часть массива.
Для каждого неотсортированного элемента n нужно: 

  1. Определить место в отсортированной части массива, куда нужно вставить n
  2. Сдвинуть отсортированные элементы вправо, чтобы сделать лакуну для n
  3. Вставить n в образовавшуюся лакуну в отсортированной части массива.

А вот и код! Рекомендуем написать свою версию программы сортировки. 

Алгоритмы сортировки. Сортировка вставками - 8

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

В самом плохом случае мы сделаем одно сравнение со вторым элементом, два сравнения с третьим и так далее. Таким образом, наша скорость равна O(n2).

В лучшем случае мы будем работать с уже отсортированным массивом. Отсортированная часть, которую мы строим слева направо без вставок и передвижений элементов займет время Ω(n).

Комментарии (18)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Global Dev Уровень 1
22 января 2025 

#include<stdio.h>
#include<cs50.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

int main(void)
{
    int array_size = get_int("Input length of array: ");
    int array[array_size];
    for(int i = 0; i < array_size; i++)
    {
        do
        {
            array[i] = get_int("\033[H\033[2J\033[3JInput (More than 0!)\nNumber for %i index: ", i);
        }
        while(array[i] < 1);
    }
    printf("\033[H\033[2J\033[3JUnsorted Numbers: ");
    for(int i = 0; i < array_size; i++)
    {
        printf("%i ", array[i]);
    }
    printf("\n");
    for(int i = 0, element = 0; i < array_size; i++)
    {
        element = array[i];
        while(i > 0 && array[i-1] > element)
        {
            array[i] = array[i-1];
            i--;
        }
        array[i] = element;
    }
    printf("Sorted Numbers: ");
    for(int i = 0; i < array_size; i++)
    {
        printf("%i ", array[i]);
    }
    printf("\n");
}
Анна Уровень 2
1 марта 2023
а нормально, что парень с цифрой 7 в спортивных шортах и шлепках на лекции?)
FeatHonnar Уровень 16
22 сентября 2022
Зачем нужная переменная j в коде? Написал точно такой же код, но убрал j, заменив все на i. Работает так же 

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main()
{
    string num = get_string("Ваше число:\n");
    int n = strlen(num);

    for (int i = 0; i < n; i++) {
        int el = num[i];
        while ((i > 0) && num[i - 1] > el) {
            num[i] = num[i - 1];
            i -= 1;
        }
        num[i] = el;
    }
    printf("%s", num);
}
Shahin Уровень 2
27 октября 2022
на 13-ой строке при замене значений ячеек третью переменнную не нужно использовать для временного сохранения,типа tmp (temporary)??? Он напрямую сохраняет значение в другую ячейку,без использования третьей переменной???
Sui Уровень 1
18 июля 2022
#include <stdio.h> #define MAX 5 int a[MAX]; int rand_seed=5; int insert (int array[]); /* from K&R - returns random number between 0 and 32767.*/ int rand(void) { rand_seed = rand_seed * 1103515245 +12345; return (unsigned int)(rand_seed / 65536) % 32768; } int main(void) { int i; /* fill array */ for (i=0; i < MAX; i++) { a[i]=rand(); printf("%d\n",a[i]); } insert (a); return 0; } int insert (int array[]) { int t,j,y; for (int i=0; i < MAX; i++) { t = array[i]; j = i; while (j > 0 && array[j-1] > t) { array[j] = array[j - 1]; j = j - 1; array[j] = t; } } printf("---------------------\n"); for (int i=0; i < MAX; i++) printf("%d\n", array[i]); return 0; }
Plumbum Уровень 2
8 августа 2021 

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

// Сортировка вставками

int main (int argc, string agrv[])
{
    int m = argc -1;
    int box[m];
    int el;
    int j = 0;

    for (int i=0; i<m; i++)
    {
        box[i]=atoi(agrv[i+1]); // создаем копию массива за исключением команды "старт"
    }

    for (int i=0; i<m; i++)
    {
        j = i;
        el = box[i]; // сохраняем число для дальнейшей замены

        while (j>0 && box[j-1]>box[j])
        {
            box[j]=box[j-1]; // тут меняем значения
            box[j-1] = el;
            j = j - 1; // запоминаем позицию меньшего числа
        }
    }
    for (int i=0; i<m; i++)
    {
        printf("%i", box[i]);
        printf("\n");
    }
}
Эдик Марруго Уровень 0
16 ноября 2020
#include <stdio.h> #include <stdlib.h> #define SIZE 10 void sort(int* mas, int size); void fillArray(int* mas, int size); void printArray(int* mas, int size); int checkIfSorted(int* mas, int size); int main() { int mas[SIZE]; fillArray(mas, SIZE); printArray(mas, SIZE); sort(mas, SIZE); printArray(mas, SIZE); checkIfSorted(mas, SIZE); } void fillArray(int* mas, int size) { for (int i = 0; i < size; i++) { mas[i] = (rand() % 100); } } void printArray(int* mas, int size) { for (int i = 0; i < size; i++) { printf("%i\n" , mas[i]); } printf("\n"); } void sort(int* mas, int size) { int temp = 0; for (int i = 0; i < size; i++) { int n = i; while (n > 0 && (mas[n - 1] > mas[n])) { temp = mas[n]; mas[n] = mas[n - 1]; mas[n - 1] = temp; n--; } } } int checkIfSorted(int* mas, int size) { for (int i = 0; i < (size - 1); i++) { if (mas[i] > mas[i + 1]) { printf("Array dont sorted"); return 0; } } printf("Array sorted"); return 1; }
Ихтияр Кадыров Уровень 1
1 ноября 2020 

/**
 * Производит сортировку в массиве
 * haystack согласно алгоритму 
 * сортировки вставкой.
 * 
 * @param haystack [Сортируемый массив]
 * @param size     [Длина массива]
 */
void insertion_sort (int haystack[], const size_t size)
{

	size_t j;
	int key;

	for (size_t i = 0; i < size; i++)
	{
		if (i > 0 && haystack[i] < haystack[i - 1])
		{
			j = i;
			key = haystack[i];
			
			while (j > 0 && key < haystack[j - 1])
			{
				haystack[j] = haystack[j - 1];
				j--;
			}

			haystack[j] = key;
		}
	}

}
prime Уровень 42
3 марта 2022
на основе твоего алгоритма public class InsSort { private static void print(int arr[]) { for (int a:arr) System.out.print(a+" "); System.out.println(""); } private static int[] inssort (int arr[]) { int[] result = arr; int j; int key; for (int i = 0; i < arr.length; i++) { if (i > 0 && arr[i] < arr[i - 1]) { j = i; key = arr[i]; while (j > 0 && key < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } result[j] = key; } } return result; } public static void main(String[] args) { int array[]= {4,7,12,15,3,9,2,11,0,13,20}; print(array); int []sort=inssort(array); print(sort); } }
Серега Уровень 20
29 августа 2020
https://www.youtube.com/playlist?list=PLyApprAtr5yjywFgRkxhfGfesgYoIhU8U
Михаил Уровень 1
30 июля 2020 

/*Прогрмамма для сортировки вставками*/
#include <stdio.h>
#include <cs50.h>    //get_string
#include <string.h>  //strlen
int main(void)
{
    int i, n, j, e;
    string s = get_string("Введите ряд позитивных чисел:\n");
    for(i = 0, n = strlen(s); i < n; i++)
    {
        e = s[i];       //e - элемент, для сравнения чисел
        j = i;

    while(j > 0 && s[j - 1] > e)   //цикл для того, чтобы 1е число не трогать и сравнивать предыдущие число с последующим...
    {
      s[j] = s[j - 1];      //...если предыдущее больше последующего, то меняем их местами
      j = j - 1;
      s[j] = e;
    }
    }
    printf("%s", s);
    printf("\n");
    return 0;
}
Андрей Уровень 0
4 мая 2020
Вот моё решение. #include <stdio.h> #include <cs50.h> int main (){ int n = get_int ("Введите длину массива: "); float a[n]; for (int i = 0; i < n; i++){ printf ("Введите число %d: ", i+1); scanf ("%f", &a[i]); } for (int i = 0; i < n; i ++){ float element = a[i]; int j = i; while (j > 0 && a[j-1] > element){ a[j] = a[j-1]; j = j - 1; a[j] = element; } } printf ("Отсортированный по возрастанию цикл: "); for (int i = 0; i < n; i++){ printf("%.2f, ", a[i]); } printf("\n"); return 0; }