Учимся делать quicksort

Question

Я в университете, пытаясь научиться использовать быстрый сортировку. Я собираюсь сделать программу через пару недель, но сначала я пытаюсь понять, как это работает. Я нашел домашнюю проблему, которая выглядит так, как будто это поможет мне понять. Единственная проблема заключается в том, что, посмотрев на Википедию и пару других сайтов, я просто оставлен в замешательстве и безнадежен.

Применить quicksort к последовательности A = {6, 4, 3, 9, 4, 7, 5}. Вместо того, чтобы на основе шарнира медианного из-трех, использовать первый элемент подпоследовательности. (Это знаменует риск наихудших результатов, но проблема проще решить вручную.) Покажите свою работу следующим образом. Указывает, когда элемент становится стержнем, поместив квадрат вокруг него. Позже укажите, что элемент/является стержнем, подчеркивая его. Используйте маркеры точек и стрелки, чтобы указать , как левый-правый поиск элементов для подкачки. Выполнение работы как рекурсия диктует: , то есть обрабатывать левые подпоследовательности перед правыми подпоследовательностями. То есть,

6 4 3 9 4 7 5 определить Pivot

5 4 3 9 4 7 6 двигаться стержень из пути и поиска элементов для замены

Может кто-нибудь объяснить мне, шаг шаг за шагом, как это работает?

Answer 1

Простая функция быстрой сортировки, как:

1. Partition основан на шарнирах - то, что эта функция поворота делает то, что он перемещает элемент поворота на правильное положение (как это было бы в отсортированном массиве). По правильному положению я имею в виду, что все элементы слева от поворота будут меньше, чем элемент поворота, а справа будут элементы, большие поворотные точки.
2. быстрой сортировки() элементы от 0 до new_index из поворота // это будет сортировать элементы по левому, используя подход разделов рекурсивно
3. () сортировки элементов из new_indexof поворота +1 к последнему индексу // Таким образом, вы будете сортировать элементы по право ...

Например:

2 1 4 3 // first element as pivot,pivot =2 

1. после раздела

2. быстрой сортировки (1)

   2,1 - использует разбиение находит один элементы, что означает его отсортированный массив влево = (1)

3. QuickSort (4,3)

   3.1 раздела 4,3 массива направо (3,4)