Не так давно я рассматривал наиболее просто реализуемый алгоритм сортировки пузырьком. Но, как вы поняли он не самый быстрый! Алгоритм QuickSort был разработан C.A.R. Hoare и считается лучшим изобретённым алгоритмом сортировки. Он основан на идее разделений. Процедура состоит в выборе значения компарада (операнда в операции сравнения) с последующим разделением массива на две части. Элементы которые больше или равны ему перемещаются в одну часть, остальные — в другую. Этот процесс повторяется для каждой части массива до тех пор пока тот не станет полностью отсортированным.
К примеру возьмём массив fedacb и будем использовать в качестве компарада — d. После первого прохода массив преобразуется в такой — bcadef. После чего процесс повторится для bca и def.
Значение компарада выбирают двумя способами: либо случайным образом, либо выбирают значение из середины массива (я склоняюсь к использованию этого метода).
Вот текст алгоритма на С++ целиком:
#include <iostream> #include <cstring> using namespace std; void quicksort(char *items, int len); void qs(char *items, int left, int right); int main() { char str[] = "984656131235484165"; cout << "Массив в исходном порядке: " << str << "\n"; quicksort(str, strlen(str)); cout << "Отсортированный массив: " << str << "\n"; return 0; } void quicksort (char *items, int len){ /* при первом вызове предлагаем к сортировке весь массив. */ qs(items, 0, len-1); } void qs(char *items, int left, int right){ int i, j ; char x, y; i = left; j = right; /* находим середину. для компаранда */ x = items[( left+right) / 2 ]; /* переносим элементы в разделённые области */ do { while((items[i] < x) && (i < right)) i++; while((x < items[j]) && (j > left)) j--; if(i <= j) { y = items[i]; items[i] = items[j]; items[j] = y; i++; j-- ; } } while(i <= j ); /* если массив не отсортирован вызываем функцию рекурсивно */ if(left < j) qs(items, left, j ) ; if(i < right) qs(items, i, right); }
Этот алгоритм отсортирует заданный массив по возвростанию.
После компиляции у меня получился вот такой вывод:
Массив в исходном порядке: 984656131235484165
Отсортированный массив: 111233444555666889
Как видите алгоритм сработал безупречно.
Стоит отметить, что в стандартной библиотеке С++ уже есть функция для сортировки, которая основана на этом алгоритме, — qsort()
Мы использовали две функции для удобства использования. В функции quicksort параметр items указывает на массив с данными для сортировки, а len — его длина. Функция qs() принимает область массива предлагаемую ей для сортировки.