2. Методы поиска элементов

Методы поиска элемента зависят от формы хранения данных (списки, массивы, кучи, деревья). Для одних форм эффективный алгоритм поиска предопределен способом хранения, для других реализация быстрых алгоритмов вообще невозможна.

Для проведения поиска элемента в массиве можно использовать простейший алгоритм – перебор всех элементов. Однако этот метод очень медленный и является не эффективным для больших массивов. Более быстрым алгоритмом является алгоритм бинарного поиска, который основан на методе половинного деления. Этот метод реализован в функции стандартной библиотеки bsearch (от binary search). Для реализации этого алгоритма требуется, чтобы массив был отсортирован по возрастанию. Для реализации алгоритма необходима функция сравнения двух элементов, которая может быть такой же, как и для функции qsort.

При использовании функции сравнения необходимо учитывать, что сортировка производится по полному набору данных. В случае поиска элементов часто необходимо найти элементы с равенством нескольких полей. В этом случае последовательность сортировки должна быть такой, чтобы проверяемые поля были первыми. Например для того, чтобы определить наличие точек с указанным номером можно использовать следующий код.

int CmpFunc(const void *e1,const void *e2)

{

int index[4]={0,1,2,3};

int i;

int *element_1 = (int*) e1;

int *element_2 = (int*) e2;

for(i=0;i<4;i++)

{

if(elemnt_1[index[i]] > elemnt_2[index[i]]) return 1;

if(elemnt_1[index[i]] < elemnt_2[index[i]]) return -1;

}

return 0;

}

int FindFunc(const void *e1,const void *e2)

{

int *element_1 = (int*) e1;

int *element_2 = (int*) e2;

return *element_1-*element_2;

}

int V[100][4],i,j;

int Number=75;

…

qsort(&V[0][0], 100, sizeof(V[0]), CompFunc);

bsearch(&Number, &V[0][0], 100, sizeof(V[0]), FindFunc);

3. Методы оценки времени работы кода

В некоторых случаях необходимо выполнять оценку времени выполнения какого-то фрагмента кода. Для этого можно использовать функции, работающие с текущим временем системы (time, difftime). Однако это целесообразно только в случае использования медленных алгоритмов, т.е. когда время выполнения составляет несколько секунд. Для оценки работы кода, требующего меньшее время, используют функцию clock, которая позволяет вычислять время в тиках (в одной секунде 18.2 тика).

long start;

double time_shell, time_buble;

start = clock();

SortShell();

time_shell = (clock()-start)/CLK_TCK;

start = clock();

SortBuble();

time_buble = (clock()-start)/CLK_TCK;

Константа CLK_TCK содержит количество тиков в одной секунде.

При работе с малыми массивами (до 100 элементов) отличий в скорости сортировки заметить практически невозможно, при дальнейшем увеличении количества элементов в массиве время сортировки с помощью метода «пузырька» и Шелла начинают сильно отличаться. Размер массива желательно довести до 20000 элементов¹.

Если и это не позволяет определить разницу, то код повторяют несколько раз. Для сортировки необходимо предусмотреть выполнение действий для одного набора данных (начального несортированного массива).

long start;

double time_shell, time_buble;

int i;

int V[100],TV[100];

FormMassive(TV,100);

start = clock();

for(i=0;i<1000;i++)

{

CopyMassive(V,TV,100);

SortShell();

}

time_shell = (clock()-start)/CLK_TCK/1000;

В данном примере предполагается, что существуют ранее написанные функции FormMassive и CopyMassive, выполняющие заполнение и копирование массива.