Сортировка вставками C#

Привет! Сегодня изучим сортировку вставками. Код писать будем на языке программирования C#.

На страницах данного сайта мы уже говорили о сортировке методом пузырька, шейкер-сортировке и о сортировке проcтым выбором.

Метод вставок похож на сортировку игральных карт в руках.

Слева в руке у нас уже есть часть карт, которые отсортированы попорядку. А справа, допустим, карты, которые только хотим отсортировать. Мы берём очередную карту и помещаем ("вставляем") в уже отсортированную часть. Вставляем карту, найдя ей соответсвующее место.

Алгоритм сортирует данные без привлечения дополнительный памяти.

Реализуем данный алогритм сортировки вставками на языке программирования C#.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;



namespace ConsoleApp22
{
    class Program
    {
        // Сортировка вставками
        static void Main(string[] args)
        {

            int[] a = { 7, 0, -4, 3, 1, -2, 5 };

            for(int i=1; i < a.Length; i++)
            {
                int k = a[i];
                int j = i - 1;

                while(j>=0 && a[j] > k)
                {
                    a[j + 1] = a[j];
                    a[j] = k;
                    j--;
                }
            }
            
            // Распечатываем массив.
            Console.WriteLine("Сортировка вставками");
            for(int i=0; i < a.Length; i++)
            {
                Console.WriteLine(a[i]);
            }

            Console.ReadKey();

        }
    }
}

Массив a - это массив, который нужно отсортировать методом вставок. Нумерация массива начинается с нуля, поэтому начинаем цикл for c первого элемента. Нулевой элемент считается отсортированной частью массива. Всё что правее - та часть, которую нужно отсортировать (область нашей работы).

Берём очередной элемент, кладём его в переменную k. Ему нужно найти местно в отсортированной части массива. С помощью цикла while ищем, где нужно разместить элемент k.

В отсортированной части идём сверху вниз. Пока очередной элемент из отсортированной части a[j] больше, чем элемент k, меняем местами k и a[j]. Как только условие a[j] > k перестало выполняться или мы дошли до начала массива, значит, элемент k нашёл своё место.

Чтобы программа точно соответствовала анимированной картинке, её можно переписать следующим образом:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;



namespace ConsoleApp22
{
    class Program
    {
        // Сортировка вставками
        static void Main(string[] args)
        {

            int[] a = { 7, 0, -4, 3, 1, -2, 5 };

            for(int i=1; i < a.Length; i++)
            {
                int k = a[i];
                int j = i - 1;

                while(j>=0 && a[j] > k)
                {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = k;
            }

            // Распечатываем массив.
            Console.WriteLine("Сортировка вставками");
            for(int i=0; i < a.Length; i++)
            {
                Console.WriteLine(a[i]);
            }

            Console.ReadKey();

        }
    }
}

Здесь мы убрали внутри цикла while cтрочку a[j] = k и дописали после цикла while a[j+1] = k. Теперь переставляем только те элементы, которые находятся в уже отсортированной области. Ищём тот элемент, который будет меньше или равен нашему элементу k. Как только найдём такой элемент, мы уже узнаем его индекс и после цикла вставим элемент k. Такая программа наиболее точно соответствует анимированной картинке, указанной выше.

Время выполнения квадратично зависит от длины массива n², ведь здесь используется вложенные циклы, которые повторяются порядка n раз.

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

Такой результат получился в нашей программе: