Научно-образовательный IT-форум при КНИТУ-КАИ

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Научно-образовательный IT-форум при КНИТУ-КАИ » Доклады и заметки » Сортировка массива методом пузырька на C#


Сортировка массива методом пузырька на C#

Сообщений 1 страница 2 из 2

1

В данной заметке мы рассмотрим сортировку методом пузырька, реализованную на языке C#.

Описание алгоритма:

Идея данной сортировки заключается в попарном сравнении соседних элементов, начиная с нулевого в массиве. Больший элемент при этом в конце первой итерации оказывается на месте последнего элемента массива, и в следующих итерациях мы его уже не сравниваем его с остальными элементами (то есть у нас будет n-1 сравнений). Затем таким же образом мы находим второй по максимальности элемент и ставим его на предпоследнее место, и т. д. После всех итераций получится, что на месте нулевого элемента окажется элемент с наименьшим числовым значением, а на месте последнего – с наибольшим числовым значением.  Таким образом у нас как бы “всплывают” элементы от большего к меньшему.

Примечание: можно также реализовать последовательность от меньшего к большему. В коде это лишь замена знака “>” на знак “<” в коде (подробнее в примечании ниже).

Пример:

У нас имеется массив: 7 2 9 4 1 0

Проводим первую итерацию. Мы берем нулевой элемент массива (7) и сравниваем его с соседним:

7<>2 9 4 1 0

Так как 7 больше, чем 2, мы меняем эти элементы местами. Получается массив:

2 7 9 4 1 0

Далее мы сравниваем 7 и 9.

2 7<>9 4 1 0

Число 9 больше, чем 7. Значит 7 остаётся на своём месте. Теперь мы будем сравнивать число 9 с остальными числами и, если 9 будет больше, чем соседние с ним числа, то будет меняться местами с ними.

2 7 9<>4 1 0

2 7 4 9<>1 0

2 7 4 1 9<>0

2 7 4 1 0 9

Большего числа, чем 9 в нашем массиве не оказалось, поэтому 9 занимает последний элемент в массиве. На этом первая итерация окончена. Теперь мы найдём следующее число, которое по значению будет меньше 9, но больше остальных чисел. Причём нам незачем больше трогать 9, так как оно уже на своём месте и в любом случае у него самое больше числовое значение. Поэтому количество шагов в итерации у нас уменьшается на 1 (n-1).

Вторая итерация. Мы опять “захватываем” нулевой элемент массива (2) и сравниваем его с соседним.

2<>7 4 1 0 9

Число 2 меньше, чем 7, поэтому они не будут меняться местами, а на следующем шаге будет сравниваться число 7 со следующим соседним элементом.

2 7<>4 1 0 9

И следующим:

2 4 7<>1 0 9

И следующим:

2 4 1 7<>0 9

Отлично, мы нашли второй элемент, и он занимает предпоследнее место в массиве. Вторая итерация окончена. Опять уменьшаем шаги итерации на 1, так как нам не надо больше сравнивать оставшиеся числа с 7.

После второй итерации наш массив выглядит так:

2 4 1 0 7 9

Третья итерация. Повторяем всё точно так же. Начинаем с нулевого элемента и ищем большее значение среди оставшихся чисел.

2<>4 1 0 7 9

2 4<>1 0 7 9

2 1 4<>0 7 9

Итого получается:

2 1 0 4 7 9

Третья итерация окончена. Начинаем четвертую и не забываем уменьшить шаги итерации на 1.

2<>1 0 4 7 9

1 2<>0 4 7 9

1 0 2 4 7 9

Осталась последняя итерация и сравнение лишь двух чисел:

1<>0 2 4 7 9

Сортировка окончена. Наш упорядоченный массив теперь выглядит вот так:

0 1 2 4 7 9

Код программы:

Программу будем делать в консоли. Для начала создадим функцию самой сортировки (перед функцией main):

Код:
static int[] BubbleSort(int[] mas)
        {
            int temp;
            for (int i = 0; i < mas.Length; i++)
            {
                for (int j = i + 1; j < mas.Length; j++)
                {
                    if (mas[i] > mas[j])
                    {
                        temp = mas[i];
                        mas[i] = mas[j];
                        mas[j] = temp;
                    }                   
                }            
            }
            return mas;
        }


Мы создаём функцию BubbleSort. В неё будет передан массив mas, который мы заполним числами для сортировки.

Здесь мы сравниваем, так сказать, предыдущий элемент (i) с последующим (j).

Если элемент массива под номером i будет больше, чем элемент массива под номером j, то меняем элементы местами и продолжаем сравнение дальше, как в алгоритме.

Примечание: выше обсуждалась возможность менять “направление” сортировки, где меньший элемент будет в конце массива, а больший в начале. Для этого надо лишь поменять строку  if (mas[i] > mas[j]) на  if (mas[i] < mas[j]).

Данная функция возвращает отсортированный массив mas.

Теперь разберем основную функцию main:

Код:
static void Main(string[] args)
        {
            Console.WriteLine("Сколько чисел будем сортировать?");
            int N = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Введите числа для сортировки:");
            int[] mas=new int[N];
            for (int i = 0; i < mas.Length; i++)
            {
                mas[i] = Convert.ToInt32(Console.ReadLine());
            }
            BubbleSort(mas);
            Console.WriteLine("После сортировки:");
            for (int i = 0; i < mas.Length; i++)
            {
                Console.WriteLine(mas[i]);
            }
            Console.ReadLine();
        }


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

Далее мы вызываем функцию сортировки, передаём в неё полученный массив, получаем отсортированный массив.

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

Вот так будет выглядеть наша программа в консоли:

https://bitbucket.org/landwatersun/forum/downloads/201802071127.png

Исходный код программы можно скачать по ссылке.

2

Программу можно дописать с контролем диапазона (с генерацией пользовательского исключения):

Код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BubbleSort
{
    class RangeArrayException : ApplicationException
    {
        // Реализуем стандартные конструкторы.
        public RangeArrayException() : base() { }
        public RangeArrayException(string str) : base(str) { }
        // Переопределяем метод ToString() для класса
        // RangeArrayException.
        public override string ToString()
        {
            return Message;
        }
    }

    class Program
    {
        static int[] BubbleSort(int[] mas)
        {
            int temp;
            for (int i = 0; i < mas.Length; i++)
            {
                for (int j = i + 1; j < mas.Length; j++)
                {
                    if (mas[i] > mas[j])
                    {
                        temp = mas[i];
                        mas[i] = mas[j];
                        mas[j] = temp;
                    }
                }
            }
            return mas;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Сколько чисел будем сортировать?");
            int N = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Введите числа для сортировки:");
            int[] mas = new int[N];
            try
            {
                for (int i = 0; i < mas.Length; i++)
                {
                    mas[i] = Convert.ToInt32(Console.ReadLine());
                    if (mas[i] < -100 || mas[i] > 99)
                        throw new RangeArrayException("Ошибка! Числа должны находиться в диапазоне [-100;100).");
                }
                BubbleSort(mas);
                Console.WriteLine("После сортировки:");
                for (int i = 0; i < mas.Length; i++)
                {
                    Console.WriteLine(mas[i]);
                }
                Console.ReadLine();
            }
            catch (RangeArrayException Err)
            {
                Console.WriteLine(Err.ToString());
            }
        }
    }
}

Вы здесь » Научно-образовательный IT-форум при КНИТУ-КАИ » Доклады и заметки » Сортировка массива методом пузырька на C#