Главная Посты Курсы Связь О сайте

Сортировка вставками 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. Такая программа наиболее точно соответствует анимированной картинке, указанной выше.


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


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


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



Сортировка вставками - результат работы программы





14-08-2022 в 19:57:35







Поддержать сайт:

Похожая статья:

Шифр Виженера на C#

Шифруем сообщение методом Виженера с помощью ключа....

Категория: Алгоритмы  Подкатегория: Шифрование
Дата: 15-01-2018 в 16:47:34 2



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально: