МАРК GROZEN-СМИТ: Привет, я Марк Grozen-Смит, и это Quicksort. Так же, как сортировку вставками и пузырь сортировать, быстрой сортировки является алгоритмом сортировка списка или массив вещей. Для простоты предположим, что те, вещи просто целые числа, но знаем, что быстрая сортировка работ по более, чем просто цифры. Быстрый старт немного сложнее чем вставка или пузырь, но это также гораздо более эффективным в большинстве случаев. Подожди секунду. Он только что сказал "наиболее случаи, "не" все "? Интересно, что нет. Не все случаи одинаковы. Не волнуйтесь об этом подробно, если вам не видел большой обозначения O пока нет, но Быстрая сортировка является О (п квадрат) Алгоритм в худшем случае, так же, как вставки или пузырьковой сортировки. Однако, как правило, действует гораздо более как старый аналоговый алгоритма м. Почему? Мы вернемся к этому позже. Но сейчас, давайте просто узнать как быстрая сортировка работает. 

Так что давайте идти через Quicksorting это массив целых от наименьшего к величине. Здесь у нас есть целые числа 6, 5, 1, 3, 8, 4, 7, 9 и 2. Во-первых, мы выбираем окончательный элемент этот массив - в этом случае, два - и назвать это "Стержень". Далее, мы начинают смотреть на две вещи - один, самый низкий показатель, который я буду называть как оставаться справа от стена, и, два, самый левый элемент, который я называю "ток элемент ". То, что мы собираемся сделать, это Посмотреть все другие элементы, другие чем стержень, и поставить все элементы меньше, чем поворота к слева от стены, и все те больше, чем поворота к Право стене. Тогда, наконец, мы будем опускать стержень Право на той стене, чтобы положить его между все числа меньше, чем и все числа больше. 

Так давайте сделаем это. Возьмите 2, поставить стену на начинается, и вызвать "текущий 6 элемент ". Таким образом, мы хотим посмотреть на наш текущий элемент, 6. И так как это больше, чем 2, мы оставляем его там, чтобы Право стене. Затем мы перейдем к смотреть на 5, как наши текущий элемент и посмотреть, что это , опять же, больше центрального, поэтому мы оставить его там, где он находится справа стороны стены. Мы идем дальше. Наш текущий элемент сейчас 1, и - о. Теперь Это отличается. Текущий элемент теперь меньше, чем стержень, поэтому мы хотим, чтобы положить его слева от стены. Чтобы сделать это, давайте просто переключиться текущий элемент с наименьшим индексом сидя только направо стены. Теперь мы переходим к стене до одного индекса так что 1 находится слева сторона стены сейчас. 

Подождите. Я просто перепутал элементы на Правая часть стены, не так ли? Не волнуйтесь. Это нормально. Единственное, что мы заботимся о сейчас является то, что все эти элементы в Право стене больше, чем поворота. Нет реальный порядок не предполагается еще. 

Теперь вернемся к сортировке. Поэтому мы продолжаем смотреть на Остальные элементы. И в этом случае, мы видим, что есть никакие другие элементы меньше, чем стержень, поэтому мы оставим их все на правая сторона стены. Наконец, мы добираемся до текущего элемента и вижу, что является стержнем. Теперь, что означает, что у нас есть два разделы массива, первый из которых небольшой по оси и на левой стороне стены, а второй больше, чем поворота к Правая часть стены. Мы хотим положить ведущий элемент между два, и тогда мы будем знать, что стержень находится в своем праве Окончательный отсортированный место. Так мы переходим первый элемент на Правая часть стены с шарниром, и мы знаем, что стержень'S в правильном положении. 

Затем мы повторить этот процесс для подмассивы слева и справа от оси поворота. Так как последнее подмассив только один элемент длиной, мы знаем, что уже отсортированный потому как вы можете быть из заказать, если вы только один элемент? Для правой стороны подмассива, мы видеть, что стержень находится в 5, и стеной только слева от 6. И текущий элемент также начинается как 6. Так 6 больше, чем 5. Мы оставляем его там, где он находится на Правая часть стены. Теперь, двигаясь по 3 меньше 5. Таким образом, мы включить его с первым элементом раз из стены. Теперь, я переехал в стену до одного. Теперь переходим к 8. 8 больше, чем 5, и поэтому мы оставим его. 4 меньше 5, поэтому мы включить его. А на. А на. 

Каждый раз, когда мы повторяем процесс на левая и правая стороны массива. мы выбрать стержень и делать сравнения и создать еще один уровень влево и правый подмассивы. Это рекурсивный вызов будет продолжаться до мы достигаем конца, когда мы делится на общую массив в всего подмассивы длины 1. Оттуда, мы знаем, что массив отсортирован потому что каждый элемент имеет, по крайней некоторая точка, был стержень. Другими словами, для каждого элемента, все цифры слева являются наименьшим ценности и все числа до Право иметь большие значения. 

Этот метод работает очень хорошо, если Ценность поворота выбранного является примерно в середине диапазон значений список. Это означает, что, после того, как мы движемся элементы вокруг, около, как многие элементы слева от оси поворота как есть вправо. И разделяй и властвуй характер Алгоритм быстрой сортировки, принимается полный преимущество. Это создает время работы O (п § п,) п, так что мы должны сделать н минус 1 сравнения на каждом поколении и журнал н, потому что мы должны разделить список войти п раз. Тем не менее, в худших случаях это Алгоритм может быть на самом деле O (п в квадрате.) Пусть на каждом поколении, стержень просто так случается, маленький или самый большой из Номера мы сортировки. Это означало бы, ломая список п раз и решений п минус 1 сравнения каждый раз. Таким образом, о н в квадрате. 

Как мы можем улучшить метод? Один хороший способ улучшить метод является чтобы сократить вероятность того, что время работы от батарей когда-либо фактически о н в квадрате. Запомните этот худший, наихудший сценарий может произойти только, когда стержень выбрали всегда самая высокая или низкое значение в массиве. Чтобы обеспечить это вряд ли произойдет, мы можем найти точку опоры на выборе нескольких элементов и принимая значение медианы. 

Меня зовут Марк Grozen-Смит, и это CS50. 

Для простоты предположим, что те, вещи просто целые числа, но знать, что QUICKSERT - QUICKSERT? Извините. 

Здесь у нас есть целые числа 6, 5, 1, 3, 8, 4, 9. 

Выступающий 1: В самом деле? 

СПИКЕР 2: Не останавливаться на достигнутом. 

Выступающий 1: В самом деле?