Алгоритм:
- Вычисляем опорный элемент (способов много, в моем случае был взят средний элемент);
- Средний элемент вычисляем как:
left + (right - left) / 2(в случае(left + right) / 2- возможно переполнение); - Создаем локальную переменную l (left) и r (right);
- Увеличиваем l (left), пока l < pivot (опорного значения);
- Увеличиваем r (right), пока r > pivot (опорного значения);
- Меняем местами l и r элементы, если l <= r, одновременно увеличивая l и уменьшая r иначе выходим из цикла;
- Повторяем с 1-го пункта, если l <= r;
- Выполняем с 1-го пункта, с входными значениями left (указанный на входе в алгоритм), r (на котором вышли из цикла);
- Выполняем с 1-го пункта, с входными значениями l (на котором вышли из цикла), right (указанный на входе в алгоритм);
Использование:
Что бы использовать алгоритм быстрой сортировки, необходимо подключить заголовочный файл:
#include "Arrays.h".
Функция сортировки:
void Arrays::quickSort(void *data, int size, int left, int right, int(*comparator) (const void *, const void *))
Функция не возвращает значение и принимает на входе следующие параметры:
data- указатель на данные;size- размер одного блока данных;left- с какого блока начинать сортировку;right- по какой блок сортировать;comparator- указатель на функцию, для сравнения опорного элемента с левым и правым элементом;
Функция компаратор должна иметь следующий вид:
int compare(const void *o1, const void *o2)
Функция имеет следующие аргументы:
o1- 1-й блок данных;o2- 2-й блок данных;
Функция должна возвращаеть (при сортировке по увеличению):
-1- если значение у 1-го элемента меньше 2-го;0- если значение 1-го и 2-го элемента равны;1- если значение 1-го элемента больше 2-го;
В качестве примера работы реализована сортировка списка студентов из файла students.csv