Доброго времени суток! В этой статье я расскажу об алгоритме сортировки массивов, достаточно простом и не самом эффективном (причем, далеко не самом), но тем не менее, для изучения базовых алгоритмов (в данном случае сортировки), разобрать его будет весьма полезно для начинающих программистов. Сортировка, реализованная по данному алгоритму, называется «пузырьковая сортировка» (bubble sort).

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

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

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

А теперь перейдём к практике! Ниже приведена реализация простейшей пузырьковой сортировки на языке программирования C#:

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

namespace BubbleSort
{
    class Program
    {        
         //Метод, сортирующий массив целых чисел (по возрастанию)
         public static void Bubble_Sort(int[] anArray)
         {
             //Выводим элементы массива (массив в исходном виде), исключительно диагностический вывод информации
             PrintArray(anArray);

             //Основной цикл (количество повторений равно количеству элементов массива)
             for (int i = 0; i < anArray.Length; i++)
             {
                 //Вложенный цикл (количество повторений, равно количеству элементов массива минус 1 и минус количество выполненных повторений основного цикла)
                 for (int j = 0; j < anArray.Length - 1 - i; j++)
                 {
                     //Если элемент массива с индексом j больше следующего за ним элемента
                     if (anArray[j] > anArray[j + 1])
                     {
                         //Меняем местами элемент массива с индексом j и следующий за ним
                         Swap(ref anArray[j], ref anArray[j + 1]);
                     }
                 }

                 //Выводим элементы массива после очередной итерации, исключительно диагностический вывод информации
                 PrintArray(anArray);
            }
        }

        //Вспомогательный метод, "меняет местами" два элемента
        public static void Swap(ref int aFirstArg, ref int aSecondArg)
        {
            //Временная (вспомогательная) переменная, хранит значение первого элемента
            int tmpParam = aFirstArg;

            //Первый аргумент получил значение второго
            aFirstArg = aSecondArg;
 
            //Второй аргумент, получил сохраненное ранее значение первого
            aSecondArg = tmpParam;
        }

        //Вспомогательный метод, выводящий на консоль элементы массива
        public static void PrintArray(int[] anArray)
        {
            //Перебор всех элементов массива
            for (int i = 0; i < anArray.Length; i++)
            {
                //Вывод значения текущего элемента и пробел после него
                Console.Write(anArray[i] + " ");
            }

            //Перевод строки
            Console.WriteLine("\n");
        }

        //Главный метод программы 
        static void Main(string[] args) 
        { 
            //Некий массив целых чисел, который нужно отсортировать 
            int[] someArray = new int[] { 1, 2, 4, 3, 8, 5, 7, 6, 9, 0}; 

            //Сортируем его 
            Bubble_Sort(someArray); 

            //Чтобы окно быстро не закрылось 
            Console.ReadKey(); 
        }
    }
}

А теперь, давайте разбираться в реализации… В классе «Program», первым делом определено метод «Bubble_Sort», реализующий алгоритм сортировки (данный метод подробнее мы рассмотрим чуть позже). Так же, реализовано два вспомогательных метода: «Swap» (меняет два элемента, передаваемых в качестве аргументов, местами) и «PrintArray» (совсем уж вспомогательный, предназначен для вывода элементов массива на экран, сделан, так как данная операция выполняется очень часто, для наглядности).

Действия, выполняемые методом «Swap» откомментированы, и не думаю, что нуждаются в пояснениях, обращу только внимание на передачу параметров в метод, они передаются по ссылке (при передаче аргументов по значению, должного эффекта не добиться, подробнее см. в статье C#. Передача параметров в методы). Метод «PrintArray» ещё проще. А вот в методе «Bubble_Sort» самое интересное…

Первым делом, в методе «Bubble_Sort» выводятся в консоль все элементы массива с помощью вспомогательного метода «PrintArray».

Этот вывод исключительно диагностический, и к алгоритму сортировки не имеет ни какого отношения!

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

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

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

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

Да, а вот результат работы программы:

Результат работы программы (сортировка массива)