>> МАРК 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: Справді?