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

На данный момент у нас уже хватает знаний, чтобы попробовать написать простейшую программу в C#. Но, простейшая — не значит бесполезная. Наша программа будет сортировать массив C#. При написании различных программ нам часто приходится сталкиваться с таким понятием как сортировка. Например, необходимо отсортировать список людей по алфавиту или произвести сортировку оценок учащихся по возрастанию. И для того, чтобы максимально эффективно решить такую задачу мы должны знать не только сам язык программирования, но и алгоритмы сортировки — их сложность, как они реализуются на практике и так далее. Сегодня мы рассмотрим самый простой алгоритм сортировки массива C# — сортировку выбором.

Задача

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

В консоль программа выведет неотсортированный и отсортированный массивы.

Алгоритм «Сортировка выбором»

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

1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Ищем минимальный элемент в неотсортированной части массива, т.е., начиная уже со второго элемента массива.
4. Меняем местами второй элемент массива и найденный минимальный.
5. Ищем минимальный элемент в массиве, начиная с третьего, меняем местами третий и минимальный элементы.
6. Продолжаем алгоритм до тех пор пока не дойдем то конца массива.

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

Вначале приведу реализацию алгоритма сортировки массивы выбором в C#. Код постарался максимально пояснить с помощью комментариев:

//intArray - это массив целых чисел
int indx; //переменная для хранения индекса минимального элемента массива
for (int i = 0; i < intArray.Length; i++) //проходим по массиву с начала и до конца
{
    indx = i; //считаем, что минимальный элемент имеет текущий индекс 
    for (int j = i; j < intArray.Length; j++) //ищем минимальный элемент в неотсортированной части
    {
        if (intArray[j] < intArray[indx])  
        {
            indx = j; //нашли в массиве число меньше, чем intArray[indx] - запоминаем его индекс в массиве
        }
    }

    if (intArray[indx] == intArray[i]) //если минимальный элемент равен текущему значению - ничего не меняем
        continue;
    //меняем местами минимальный элемент и первый в неотсортированной части
    int temp = intArray[i]; //временная переменная, чтобы не потерять значение intArray[i]
    intArray[i] = intArray[indx];
    intArray[indx] = temp;
}

Проверить работу алгоритма нам поможет небольшая консольная программка в C#, которую мы сейчас и напишем.

Программа сортировки массива C# выбором

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

Собираем массив целых чисел

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]);
}

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

string[] nums = Console.ReadLine().Split(new char[] { ',' });

здесь nums — это массив строк.

Метод Console.ReadLine() возвращает нам последнюю строку из консоли.

Метод Split(new char[] { ',' })— это метод для типа string, который возвращает массив строк, созданный из исходной строки. В качестве аргумента этот метод принимает массив символов по которым будет делиться строка. Так как у нас, по условиям задачи, разделитель всего один — запятая, то и массив разделителей в методе Split() содержит всего один элемент.

На следующем шаге мы создаем массив целых чисел размер которого совпадает с размером массива nums.

int[] intArray = new int[nums.Length]

Далее, в цикле for мы наполняем наш созданный массив числами, используя метод Parse() у типа данных int, который возвращает нам целое число из строки.

for (int i = 0; i < nums.Length; i++) 
  { 
    intArray[i] = int.Parse(nums[i]); 
  }

Выводим неотсортированный массив в консоль

Вывести неотсортированный массив пользователю проще простого, если воспользоваться циклом foreach:

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

Сортируем массив, используя алгоритм «Сортировка выбором» и показываем результат

Для этого используем реализацию алгоритма, которая представленная выше. Чтобы вывести отсортированный массив пользователю снова используем цикл foreach.

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

так как для неосортированного массива мы использовали метод Console.Write(), которые не производит переход на следующую строку, то здесь, в методе Console.WriteLine() мы использовали управляющие символы C# /r/n для перехода на новую строку и возврат каретки в начало строки.

Результат работы программы

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

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

Исходный код программы

Ниже приведен весь исходный код программы C# для сортировки массива:

using System;

namespace SelectSort
{
    class Program
    {
        static void Main(string[] args)
        {
            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]);
            }

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

            int indx; //переменная для хранения индекса минимального элемента массива
            for (int i = 0; i < intArray.Length; i++) //проходим по массиву с начала и до конца
            {
                indx = i; //считаем, что минимальный элемент имеет текущий индекс 
                for (int j = i; j < intArray.Length; j++) //ищем минимальный элемент в неотсортированной части
                {
                    if (intArray[j] < intArray[indx])
                    {
                        indx = j; //нашли в массиве число меньше, чем intArray[indx] - запоминаем его индекс в массиве
                    }
                }

                if (intArray[indx] == intArray[i]) //если минимальный элемент равен текущему значению - ничего не меняем
                    continue;
                //меняем местами минимальный элемент и первый в неотсортированной части
                int temp = intArray[i]; //временная переменная, чтобы не потерять значение intArray[i]
                intArray[i] = intArray[indx];
                intArray[indx] = temp;
            }


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

Также, Вы можете загрузить исходный код приложения из нашего репозитория на Github.

Итого

Сегодня мы написали своё первое полноценное приложение на C# для сортировки массива. Как видите, для этого нам пригодилось всё, что мы изучали ранее — переменные, работа с массивами, литералы, циклы и так далее. Постепенно, наши программы будут «обрастать» новыми возможностями, станут более устойчивыми к различным ситуациям (например, сегодня я даже не пытался проверить то, что ввел пользователь, хотя такую проверку необходимо проводить). Но всё это будет делаться постепенно, по мере изучения возможностей C#.