Задачи поиска и сортировки возникают в самых разных контекстах. Рассмотрим задачу поиска в следующей постановке. Дан массив Items c элементами типа (класса) T и элемент pattern типа T, называемый образцом. Необходимо определить, встречается ли образец в массиве и, если да, определить индекс его вхождения.
Задача сортировки состоит в том, чтобы отсортировать массив Items. Предполагается, что тип T является упорядоченным типом, так что его элементы можно сравнивать. Задачу можно конкретизировать, полагая, например, что T - это тип string, и рассматривать поиск и сортировку строковых массивов. Поскольку алгоритмы поиска и сортировки практически не зависят от типа T, то отложим конкретизацию типа настолько, насколько это возможно.
Рассмотрим три классических алгоритма поиска - линейный поиск, линейный поиск с барьером, бинарный поиск в упорядоченном массиве.
Алгоритм линейного поиска предельно ясен. В цикле по числу элементов сравнивается очередной элемент массива с образцом. При нахождении элемента, совпадающего с образцом, поиск прекращается. Если цикл завершается без нахождения совпадений, то это означает, что в массиве нет искомого элемента. Время работы такого алгоритма линейно. В худшем случае придется сравнить образец со всеми элементами, в лучшем - с одним, в среднем - число сравнений равно n/2, где n - число элементов массива. У линейного поиска есть один недостаток: если образец не присутствует в массиве, то без принятия предохранительных мер поиск может выйти за границы массива, вследствие чего может возникнуть исключительная ситуация. В классическом варианте линейного поиска приходится на каждом шаге дополнительно проверять корректность значения текущего индекса.
Чтобы эта простая задача смотрелась интереснее, рассмотрим параметризованный алгоритм с параметром T, задающим тип элементов, и его реализацию на языке C#. Построим универсальный класс (класс с родовыми параметрами):
public class Service<T> where T:IComparable<T>{}
Класс Service имеет параметр T, на который наложено ограничение - класс T должен быть наследником интерфейса IComparable, следовательно, должен реализовать метод CompareTo этого интерфейса. Содержательно это означает, что T является упорядоченным классом.
Класс Service будем рассматривать как сервисный класс, реализованный в виде модуля, предоставляющий клиентским классам некоторые сервисы, в частности, возможность осуществлять поиск в массивах любого типа. Добавим в этот класс два статических метода, реализующих алгоритм линейного поиска:
/// <summary> /// Линейный поиск образца в массиве /// </summary> /// <param name="massiv">искомый массив</param> /// <param name="pattern">образец поиска</param> /// <returns> /// индекс первого элемента, совпадающего с образцом /// или -1, если образец не встречается в массиве /// </returns> public static int SearchPattern(T[] massiv, T pattern) { for (int i = 0; i < massiv.Length; i++) if (massiv[i].CompareTo(pattern)==0) return (i); return (-1); } /// <summary> /// Вариация линейного поиска образца в массиве /// </summary> /// <param name="massiv">искомый массив</param> /// <param name="pattern">образец поиска</param> /// <returns> /// индекс первого элемента, совпадающего с образцом /// или -1, если образец не встречается в массиве /// </returns> public static int SearchPattern1(T[] massiv, T pattern) { int i = 0; while((i<massiv.Length)&& (massiv[i].CompareTo(pattern)!=0)) i++; if (i == massiv.Length) return (-1); else return (i); }
Две вариации линейного поиска отличаются лишь деталями. В первой из них проще условие цикла, но зато в тело цикла встроен оператор if, при выполнении условия которого завершается не только цикл, но и сам метод. В другой вариации усложнено условие цикла, но тело цикла совсем простое. В принципе тело цикла можно сделать пустым в этом варианте, внеся увеличение индекса во второе условие цикла. Но это уже трюк, снижающий ясность понимания программы. Трюкачество я не приветствую. Какую из эквивалентных версий выбирать - это дело программистского вкуса.
