Шейкер-сортировка на C#

Привет, Друзья! Сегодня разберём алгоритм сортировки "метод встряхивания" или Шейкер-сортировку. Данная тема хорошо подходит для повторения массивов на уроке информатики. Алгоритм основан на методе пузырька, который я уже разбирал на своём сайте.

Предположим нам необходимо отсортировать массив: 3, 4, 22, 6, 1 . Если мы будем сортировать этот массив классическим методом пузырька, то самый последний элемент 1 встанет на своё место только после прохождения длина массива - 1 раз по всему массиву.

В шейкер-сортировке сначала ищется самый большой элемент, как и в методе пузырька, но затем, ищется самый маленький элемент. Потом опять самый большой, затем опять самый маленький и т.д., при этом, уменьшая границы прохождения массива соответственно. Из-за такого подхода алгоритм получил название "метод встряхивания", потому что мы идём то вверх по массиву, то вниз. Это позволяет быстро отсортировать массив, если он почти упорядочен, но пару элементов стоят неудачно, как в нашем примере. Если мы при этом будем анализировать массив на "готовность", то можем немного выиграть у метода пузырька во времени.

Но если массив изначально плохо отсортирован, то можем получить такое же время, как и "пузырёк". Время выполнения квадратично зависит от длины массива n².

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

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

namespace ConsoleApp14
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = { 3, 4, 22, 6, 1 };
            int l = 0;
            int r = a.Length - 1;
            bool exchange;
           
            do
            {
                exchange = false;

                bubble(ref a, l, r, ref exchange);
                r--;

                bubble(ref a, r, l, ref exchange);
                l++;
            } while (exchange);


            for (int i=0; i < a.Length;i++)
            { 
                Console.WriteLine(a[i]);
            }
           
            Console.ReadKey();

        }

        static void bubble( ref int[] b, int n, int m, ref bool exchange)
        {
            int temp;

            if (m == n) return ;
  
            if (n < m)
            {
                for(int i = n; i < m; i++)
                {
                    if(b[i] > b[i+1])
                    {
                        temp = b[i];
                        b[i] = b[i + 1];
                        b[i + 1] = temp;
                        exchange = true;
                    }  
                }
            }
            else
            {
                for (int i = n; i > m; i--)
                {
                    if (b[i] < b[i-1])
                    {
                        temp = b[i];
                        b[i] = b[i - 1];
                        b[i - 1] = temp;
                        exchange = true;
                    }
                }
            }
            return ;
        } 
    }
}