Привет, читатель :) Вот я и решил начать, причем начать я решил не с азов (я считаю что рассматривать их не стоит) но и чего-то запредельно сложного тут не найти. Я всего лишь студент который учиться как и ты.
Итак, первое о чем я хотел написать, так это о сортировке и ее реализации. Почему именно с нее? все просто, очень часто на собеседованиях требуют знания как работает тот или иной метод сортировки, или просят его реализовать, а во вторых всегда приятнее уметь самому делать то что уже реализовано. Так что то я заговорился не по делу, пора начинать.
Задача: Реализовать *.DLL библиотеку которая будет реализовывать сортировку массива методом пузырька или быстрой сортировкой по возрастанию и убыванию.
Так с задачей мы определились, начнем реализовывать.
Подробно о этих методах сортировки можно ознакомиться тут:
Сортировка пузырьком,
Быстрая сортировка.
Так с теорией мы тоже разобрались :) Быстро продвигаемся.
Начнем с реализации метода пузырька, так как он проще: Создадим класс с именем "BubbleSort.cs"
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ASort
{
public class BubbleSort
{
}
}
Заглянем немного на перед и вспомним что потом нам придется реализовывать сортировку по возрастанию и убыванию, следовательно нам нужно свойство которое бы содержало эту информацию, давайте его добавим:
private bool IsDown;
public bool IsDownValue
{
get
{
return IsDown;
}
set
{
IsDown = value;
}
}
Почему мы сделали именно так? все просто, потому что нам необходимо обеспечить безопасность этого свойства и мы не хотим что бы в него попало не хорошее значение, непонятно откуда.
Теперь начнем самое интересное саму сортировку, так как мы не знаем какой тип данных будет в массиве используем универсальный интерфейс IComparable, объявление метода будет следующим:
public Array Sort(T[] arr)where T:IComparable
{
//тут происходит сортировка
return arr;
}
Я продемонстрирую как сделать сортировку по возрастанию, для убывания вы с легкостью сделаете сами:
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length-1; j++)
{
if (!IsDownValue)
{
if (arr[j].CompareTo(arr[j + 1]) > 0)//возрастание
{
T temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
else
{
//по аналогии с предыдущем условием делаем для убывания
}
}
}
Результатом работы данного метода будет массив той же размерности и типа что входной, однако уже упорядоченный.
Теперь давай те попробуем сделать тоже самое но методом быстрой сортировки. Создадим новый класс в проекте назовем, например "QuickSort.cs" и как и в прошлый раз создадим в нем точно такое же свойство.
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable
int partition( T[] m, int a, int b) where T :IComparable
{
int i = a;
for (int j = a; j <= b; j++) // просматриваем с a по b
{
if (m[j].CompareTo( m[b]) <= 0) // если элемент m[j] не превосходит m[b],
{
T t = m[i]; // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...
m[i] = m[j]; // то есть переносим элементы меньшие m[b] в начало,
m[j] = t; // а затем и сам m[b] «сверху»
i++; // таким образом последний обмен: m[b] и m[i], после чего i++
}
}
return i - 1; // в индексе i хранится <новая позиция элемента m[b]> + 1
}
void quicksort( T[] m, int a, int b) where T : IComparable// a - начало подмножества, b - конец
{ // для первого вызова: a = 0, b = <элементов в массиве> - 1
if (a >= b) return;
int c = partition( m, a, b);
quicksort( m, a, c - 1);
quicksort( m, c + 1, b);
}
//Пример вызова
//double[] arr = {9,1.5,34.4,234,1,56.5};
//quicksort(arr,0,arr.Length-1);
Теперь добавим возможность выбора сортировки по возрастанию и убыванию.
private int partition(T[] arr, int start, int end) where T : IComparable
{
int i = start;
for (int j = start; j <= end; j++)
{
if (!IsDownValue)
{
if (arr[j].CompareTo(arr[end]) <= 0)
{
T t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
}
}
else
{
if (arr[j].CompareTo(arr[end]) >= 0)
{
T t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
}
}
}
return i - 1;
}
Ну вот и все. Все готово. Советую собирать проект в виде dll и использовать как библиотеку, как ее использовать описано
тут в заголовке
ASort, там же можно скачать то что получилось у меня.
Не давно нашел пример быстрой сортировки с помощью лямбда выражений:
using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable QuickSort(this IEnumerable list) where T : IComparable
{
if (!list.Any())
{
return Enumerable.Empty();
}
var pivot = list.First();
var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();
var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();
return smaller.Concat(new[] { pivot }).Concat(larger);
}
//(тоже самое, но записанное в одну строку, без объявления переменных)
public static IEnumerable shortQuickSort(this IEnumerable list) where T : IComparable
{
return !list.Any() ? Enumerable.Empty() : list.Skip(1).Where(
item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })
.Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());
}
}
Ну вот и все, спасибо за внимание.
Для начала создадим проект WinForms и добавим на форму: Label и Button.