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

Избыточность простой пузырьковой сортировки

На рисунке отмечены результаты последних итераций, и видно, что массив уже не менялся, так как был отсортирован во время первой итерации (вторая строка в на рисунке), тем не менее, остальные итерации выполнялись (хотя, были явно избыточными), именно про выполнение таких итерация я и говорил в самом начале, точнее, я говорил про исключение таких итераций. А исключаются они очень просто, нужно лишь фиксировать факт перестановки элементов во время каждой итерации. Т. е. если во время поочередного перебора элементов массива была хоть одна перестановка смежных элементов массива местами, то нужно зафиксировать этот факт в переменную типа bool (если были перестановки, переменная будет иметь значение true). А перед каждой последующей итерацией, будет проверяться значение этой самой переменной, если значение будет равно true, то значение переменной будет устанавливаться в false, а итерация запускаться, в противном случае (если значение переменной не равно true)  — сортировка прекращается, так как массив уже отсортирован (перестановок во время выполнения предыдущей итерации не было). А вот исходный код, с модифицированным алгоритмом (нововведения, относительно алгоритма, приведенного в предыдущей статье, выделены):

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++)
             {
                 //Эта переменная будет фиксировать факт перестановки элементов
                 bool isChanged = false;
                 
                 //Вложенный цикл (количество повторений, равно количеству элементов массива минус 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]);

                         //Раз поменяли местами, зафиксируем этот факт
                         isChanged = true;
                     }
                 }

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

                 //Если факт перестановки элементов не был зафиксирован
                 if (isChanged == false)
                     break; //Прерываем цикл (прекращаем сортировку)
            }
        }

        //Вспомогательный метод, "меняет местами" два элемента
        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(); 
        }
    }
}

А вот и результат выполнения программы:

Сокращение избыточности простой пузырьковой сортировки

Как видно, количество итераций существенно сократилось (первая строка — вывод исходного массива; вторая — результат первой итерации; третья — результат второй итерации, во время которой и стало понятно, что массив уже отсортирован). Но тем не менее, осталась одна избыточная итерация. Во время неё мы не меняли местами ни какие элементы массива, а значит — и не выполняли полезных действий (т.е. уже не сортировали), а использовали мы эту итерацию, только для того, чтобы понять что массив уже отсортирован. Но если ещё доработать алгоритм, то эта избыточная итерация тоже не понадобится. Ниже я привел исходный код модифицированного алгоритма, вдаваться в подробности я уже не буду (пояснения есть в комментариях), скажу лишь только, что идея данной модификации в подсчете количества перестановок элементов массива в рамках одной итерации:

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++)
             {
                 //Эта переменная будет хранить количество перестановок в рамках текущей итерации
                 int counter = 0;
                 
                 //Вложенный цикл (количество повторений, равно количеству элементов массива минус 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]);

                         //Раз поменяли местами, увеличим счетчик перестановок
                         counter++;
                     }
                 }

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

                  //Если было не больше одной перестановки
                  if (counter <= 1)
                      break; //Прерываем цикл (прекращаем сортировку)
            }
        }

        //Вспомогательный метод, "меняет местами" два элемента
        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(); 
        }
    }
}

А вот результат (количество итераций сократилось до минимума), первая строка — вывод исходного массива, вторая — результат первой, и единственной необходимой в данном случае итерации:

Сокращение избыточности простой пузырьковой сортировки до минимума

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