Программная реализация алгоритмов сортировки

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

1. Массив состоит из элементов произвольного типа, но постоянной длины;

2. Для сравнения двух элементов будем использовать функцию со следующим прототипом:

int fcmp(const int a, const int b, const void *base, const size_t width);

Здесь a и b – индексы элементов, подлежащих сравнению, base – указатель на сортируемый массив, width – длина элемента массива в байтах.

3. Для обмена содержимого двух элементов будем использовать функцию со следующим прототипом:

void elemswap(const int a, const int b, void *base, const size_t width);

Здесь a и b – индексы элементов, подлежащих обмену, base – указатель на сортируемый массив, width – длина элемента массива в байтах.

Метод пузырька.

Метод пузырька является наиболее простым методом сортировки. Идея его очень проста: перебираются все элементы массива (за исключением последнего), и каждый из них сравнивается с последующим элементом. Если предыдущий элемент больше последующего, эти два элемента меняются местами. После этого перебор элементов начинается сначала. Так повторяется до тех пор, пока при переборе элементов массива не будет совершено ни одного обмена элементов.

void bubble(void *base, size_t nelem, size_t width,int (*fcmp)(const int, const int, const void*, const size_t))

{

int i,sw;

do

{

sw = 0;

for (i = 0; i <= (int)nelem - 2; i++)

{

if (fcmp(i, i+1, base, width) > 0)

{

elemswap(i, i+1, base, width);

sw = 1;

}

}

} while (sw);

}

Метод обмена.

Метод обмена также является довольно простым методом. Суть его в следующем: перебираются все элементы массива. Для каждого из них перебираются все следующие за ним элементы. Из числа этих элементов выбирается наименьший. После этого текущий и найденный элементы меняются местами. Таким образом, все элементы до текущего отсортированы. Когда перебраны все элементы, сортировка завершена.

void exchange(void *base, size_t nelem, size_t width, int (*fcmp)(const int, const int, const void*, const size_t))

{

int j, i, min;

for (j = 0; j < (int)nelem; j++)

{

min = j;

for (i = j + 1; i < (int)nelem; i++)

{

if (fcmp(i, min, base, width) < 0)

{

min = i;

}

}

if (min > j)

{

elemswap(j, min, base, width);

}

}

}

Метод вставки.

Метод вставки похож на метод обмена. Как и в методе обмена, в методе вставки перебираются все элементы массива. Однако, на этот раз для каждого из них перебираются все предыдущие элементы. В ходе этого перебора определяется место, куда среди них следует поместить текущий элемент. После того, как это место определено, текущий элемент помещается туда. Как и в методе вставки, все элементы до текущего отсортированы. Когда перебраны все элементы, сортировка завершена.

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

void insertion(void *base, size_t nelem, size_t width, int (*fcmp)(const void *, const void *))

{

int j, i;

void *tmp;

tmp=malloc(width);

for (j = 1; j < (int)nelem; j++)

{

memcpy(tmp, (char *)base + j*width, width);

for (i = j; i > 0; i--)

{

if (fcmp((char *)base + (i-1)*width, tmp) > 0)

{

memcpy((char *)base + i*width, (char *)base + (i-1)*width, width);

}

else

{

break;

}

}

memcpy((char *)base + i*width, tmp, width);

}

free(tmp);

}