Алгоритм сортировки методом вставки (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. Проиллюстрируем это на пример сортировки массива числе и строк. Для начала создадим форму:
И для иллюстрации работы наших алгоритмов напишем вот такой пример:
|
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(); }
} } |
Все, теперь мы можем протестировать работу алгоритма:
Исходники к уроку можно скачать здесь.