Сортировка массива C#. Алгоритм «Сортировка вставками»

Сортировка вставками — это алгоритм, в котором элементы массива просматриваются по одному, и каждый элемент элемент размещается в подходящее место среди ранее упорядоченных элементов. С этим алгоритмом сортировки многие из нас сталкиваются в жизни, не подозревая, что используют сортировку вставками — когда сортируют деньги в кошельке. Например, вы получаете в магазине сдачу — 550 рублей. Открываете кошелек — там лежит 200, 1000 и 5000 рублей. Те, кто любит порядок делают так: берут 50 рублей и вставляют их в подходящее место (в самое начало), затем берут 500 рублей и вставляют между 200 и 1000 рублями и в итоге получают упорядоченный «массив» денег 50, 200, 500, 1000 и 5000 рублей. Вот наглядный пример сортировки вставками. Этот алгоритм чем-то напоминает гномью сортировку, но требует вложенного массива.

Алгоритм

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

Реализация алгоритма вставками в C#

Для реализации алгоритма нам потребуется метод Swap() меняющий два элемента массива местами и, собственно, метод, реализующий метод сортировки массива вставками.

static void Swap(int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

static void InsertionSort(int[] inArray)
{
    int x;
    int j;
    for (int i = 1; i < inArray.Length; i++)
    {
        x = inArray[i];
        j = i;
        while (j > 0 && inArray[j - 1] > x)
        {
            Swap(inArray, j, j - 1);
            j -= 1;
        }
        inArray[j] = x;
    }
}

Пример сортировки массива

Console.WriteLine("Введите через запятую целые числа и нажмите Enter");
string[] nums = Console.ReadLine().Split(new char[] { ',' });
int[] intArray = new int[nums.Length];
for (int i = 0; i < nums.Length; i++)
{
    intArray[i] = int.Parse(nums[i]);
}

InsertionSort(intArray);

Console.WriteLine("\r\nОтсортированный массив:");
foreach (int value in intArray)
{
    Console.Write($"{value} ");
}

Консольный вывод: