Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Алгоритмы arrow Алгоритм сортировки методом вставки (C#, параметризированный класс).
28.02.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Алгоритм сортировки методом вставки (C#, параметризированный класс). Печать E-mail
Автор megabax   
12.11.2012 г.
Циклы

Алгоритм сортировки методом вставки (C#, параметризированный класс).

Исходники к уроку можно скачать здесь.

Сегодня мы рассмотрим алгоритм сортировки методом вставки. В отличии от сортировки методом пузырька и отбора, в этом алгоритме количество сравнений зависит исходной упорядоченности массива. Если список уже отсортирован (наилучший случай) то количество сравнений равно n-1, если отсортирован в обратном порядке (наихудший случай), то сравнений будет (1/2)*(n2+n). В среднем же случае количество сравнений равно (1/4)*(n2+n).

Суть алгоритма в следующем: На первом шаге сортируем первые два элемента. Затем вставляем третий элемент к этим двум элементам в соответствии с его порядковой позиций. Затем в этот список таким же макаром вставляем четвертый элемент и так далее.

Например, пусть у нас имеется вот такой список чисел: 3,2,5,1,8. Вот как будет происходить сортировка:

Исходный массив 3,2,5,1,8
Шаг 1 2,3,5,1,8
Шаг 2 2,3,5,1,8
Шаг 3 1,2,3,5,8
Шаг 4 1,2,3,5,8

Как видим, в любом случае алгоритм сделает n-1 проходов, и, в уже отсортированном массиве количество сравнений равно столько же.  Если массив требуется сортировать, то количество сравнений будет возрастать, при чем тем больше, чем несортированней массив. Как видим, данный алгоритм ведет себя естественно - уже отсортированный массив или его часть не сортирует, а наибольшее количество итераций делает для массива, который отсортирован в порядке, обратном требуемому.

А сейчас мы реализуем данный алгоритм на C#. Для этого создадим параметризированный класс Sort:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace WindowsFormsApplication1

{

    class Sort<TType>

    {

        //сортируемый массив

        public List<TType> list;

 

        private IComparer<TType> comparer;

 

 

        public Sort(IComparer<TType> defaultComparer)

        {

            comparer = defaultComparer ?? Comparer<TType>.Default;

            list = new List<TType>();

        }

 

 

        public bool isLess(TType a, TType b)

        {

           return comparer.Compare(a, b)==-1;

        }

 

        public void SortInsert()

        {

            int a, b;

            TType t;

            int count=list.Count;

            for (a = 1; a < count; ++a)

            {

                t = list[a];

                for (b = a - 1; b >= 0 && isLess(t, list[b]); b--)

                {

                    list[b + 1] = list[b];

                }

                list[b + 1] = t;

            }

        }

    }

}

Таким образом, имея параметризируемый класс, мы можем сортировать любые данные, поддерживающие интерфейс IComparer. Проиллюстрируем это на пример сортировки массива числе и строк. Для начала создадим форму:

Алгоритм сортировки методом вставки (C#, параметризированный класс).

И для иллюстрации работы наших алгоритмов напишем вот такой пример:

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace WindowsFormsApplication1

{

    public partial class frmSortInsert : Form

    {

        private int amount = 10; //количество элементов в массиве

        private Sort<int> intsort; //сортируемый массив чисел

        private Sort<string> stringsort; //сортируемый массив строк

        private string letters = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя"; //алфавит

        private int len; //длина алфавита

 

        //создаем массив чисел

        private void InitInt(int count)

        {

            intsort.list.Clear();

            Random rnd = new Random();

            for (int i = 1; i <= count; i++)

            {

                intsort.list.Add(rnd.Next(100));

            }

        }

 

        //создаем массив строк

        private void InitString(int count)

        {

            stringsort.list.Clear();

            Random rnd = new Random();

            for (int i = 1; i <= count; i++)

            {

                string str = "";

                for(int j=0; j<10; j++) str += letters[rnd.Next(len)];

                stringsort.list.Add(str);

            }

        }

 

        //конструктор формы примера

        public frmSortInsert()

        {

            InitializeComponent();

            intsort = new Sort<int>(Comparer<int>.Default);

            stringsort = new Sort<string>(Comparer<string>.Default);

            len = letters.Length;

        }

 

        //обработчик нажатия на кнопку "пуск"

        private void btnStart_Click(object sender, EventArgs e)

        {

            lbIntAfter.Items.Clear();

            lbIntBefore.Items.Clear();

            lbStringAfter.Items.Clear();

            lbStringBefore.Items.Clear();

            InitInt(amount);

            InitString(amount);

            ShowInt(lbIntBefore, intsort.list);

            ShowString(lbStringBefore, stringsort.list);

            intsort.SortInsert();

            stringsort.SortInsert();

            ShowInt(lbIntAfter, intsort.list);

            ShowString(lbStringAfter, stringsort.list);

        }

 

        //отобразить массив чисел

        private void ShowInt(ListBox listBox, List<int> list)

        {

            foreach(int item in list)

            {

                listBox.Items.Add(item);

            }

        }

 

        //отобразить массив строк

        private void ShowString(ListBox listBox, List<string> list)

        {

            foreach (string item in list)

            {

                listBox.Items.Add(item);

            }

        }

 

 

        private void btnOur_Click(object sender, EventArgs e)

        {

            intsort = new Sort<int>(Comparer<int>.Default);

            intsort.list.Add(3);

            intsort.list.Add(2);

            intsort.list.Add(5);

            intsort.list.Add(1);

            intsort.list.Add(8);

            intsort.SortInsert();

        }

 

    }

}

Все, теперь мы можем протестировать работу алгоритма:

Алгоритм сортировки методом вставки (C#, параметризированный класс).

Исходники к уроку можно скачать здесь.

Последнее обновление ( 12.11.2012 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги