СВЕТ: СПАСИБО
01-12-2023
Читать статью
Калужский Александр: Задача про Цаплю: https://www.youtube.co..
24-11-2023
Сергей: спасибо большое
Привет! Сегодня изучим сортировку вставками. Код писать будем на языке программирования 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 раз.
Сортировка вставками считается более эффективной по сравнению с методом пузырька, шейкер-сортировкой, сортировкой простым выбором.
Такой результат получился в нашей программе: