Обьясните пожалуйста суть алгоритма сортировки quicksort и помогите пожалуйста реализовать это всё на языке C#
Алгоритм быстрой сортировки следующий:
1. Выбираем опорный элемент
2. Разбиваем массив на 3 части
3. Создаём переменные l и r — индексы соответственно начала и конца рассматриваемого подмассива
4. Увеличиваем l, пока l-й элемент меньше опорного Уменьшаем r, пока r-й элемент больше опорного. Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r Если l вдруг становится больше r, то прерываем цикл
5. Повторяем рекурсивно, пока не дойдём до массива из 1 элемента
Как видим, тут нет абсолютно ничего сложного. Теперь реализация на C#:
public static void Quicksort(IComparable[] elements, int left, int right) { int i = left, j = right; IComparable pivot = elements[(left right) / 2];while (i <= j) { while (elements[i].CompareTo(pivot) < 0) { i ; } while (elements[j].CompareTo(pivot) > 0) { j--; } if (i <= j) { // Swap IComparable tmp = elements[i]; elements[i] = elements[j]; elements[j] = tmp; i ; j--; } } // Recursive calls if (left < j) { Quicksort(elements, left, j); } if (i < right) { Quicksort(elements, i, right); } }