Алгоритъм за бързо сортиране в JavaСкрипт с пример

Какво е бързо сортиране?

Бързо сортиране е алгоритъм за сортиране чрез сравнение, който следва Разделяй и владей подход. Той избира един елемент като опорна точка, разделя масива на част, която съдържа стойности по-малки от опорната точка, и част, която съдържа по-големи стойности, и след това прилага същата процедура към всяка част, докато целият масив бъде подреден.

Бързото сортиране е един от най-широко използваните алгоритми за сортиране във всеки език за програмиране. Ако пишете JavaСценарий, вероятно вече сте използвали вградения вид() метод, така че може би се чудите защо си струва да се научи отделна имплементация на Quick Sort. За да отговорите на това, първо трябва да знаете какво означава сортиране и какво е сортирането по подразбиране в JavaСкриптът всъщност го прави.

Три свойства дефинират бързото сортиране:

• На място: пренарежда оригинала масив и не разпределя втори масив със същия размер.
• Рекурсивно: Всеки дял създава два по-малки диапазона, които са сортирани по една и съща функция.
• Нестабилен: Два елемента с еднакви ключове могат да се окажат в различен относителен ред от този, в който са започнали.

Какво е сортиране?

Сортирането означава подреждане на елементи в определен ред. Почти сигурно сте срещали това в училище: подреждането на числата от най-малкото към най-голямото е възходящ ред, а подреждането им от най-голямото към най-малкото е низходящ ред. Сортирането не е ограничено само до числа. Низовете могат да бъдат подредени по азбучен ред, датите – хронологично, а обектите – по всяко поле, което изберете, като например цена или резултат.

Сортирането е важно, защото подредените данни отключват по-бързи операции. Двоичното търсене се изпълнява за O(log n) време, но само върху сортиран вход. Дедупликацията, заявките за диапазон, класирането и операциите по сливане стават много по-евтини, след като данните са подредени, поради което всеки език предлага поне една рутина за сортиране.

Сортиране по подразбиране в JavaСценарий

Както е споменато по-рано, JavaСкриптът предоставя вид()Вземете малък масив, например [5,3,7,6,2,9], който искате да бъде подреден във възходящ ред. Извикайте вид() върху масива изглежда прави точно това.

Горната екранна снимка показва как конзолата на браузъра отпечатва сортирания масив. Ето същия код:

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

Изход:

[ 2, 3, 5, 6, 7, 9 ]

Тозият резултат е правилен, но само по случайност. Array.prototype.sort() преобразува всеки елемент в низ и сравнява низовете освен ако не предоставите функция за сравнение. Всяка стойност в този масив е едноцифрена, така че редът на низовете съвпада с числовия ред. Променете данните и илюзията се разпада.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Изход:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Какъв алгоритъм използва sort()?

Спецификацията не посочва алгоритъм, така че всеки двигател избира свой собствен. Всички съвременни двигатели използват алгоритъм, базиран на сливане:

• V8 (Chrome, Edge, Node.js) е използвал TimSort от V8 7.0, доставян в Chrome 70.
• Паяк маймуна (Firefox) използва сортиране по сливане.
• JavaScriptCore (Safari) също използва сортиране по сливане.

От ES2019 езикът гарантира, че sort() is стабилен, което изключва обикновено бързо сортиране вътре в двигателя. Сортирането, базирано на сливане, изисква O(n) спомагателна памет и трябва да извика вашата JavaСкрипт за сравнение за всяко едно сравнение. Ръчно написан числов инструмент за бързо сортиране сравнява числа директно и сортира на място, така че може да спечели при големи числови масиви. Сортирането на 1 000 000 случайни цели числа в Node.js 22 отне приблизително 100 мс с бързото сортиране по-долу и приблизително 210 мс с sort((a, b) => a - b).

Така че, Quick Sort си струва да се напише, когато имате нужда от сортиране на място, строг контрол върху паметта или просто солидно разбиране за това как работи сортирането. Нека разгледаме механиката подробно.

Как работи бързото сортиране?

Бързото сортиране повтаря една основна операция, наречена подялба, на все по-малки и по-малки диапазони. Ето стъпките по ред:

1. Намерете опорна точка елемент в масива.
2. Започнете левия показалец от първия елемент от диапазона.
3. Започнете десния показалец от последния елемент от диапазона.
4. Сравнете елемента при левия показалец с опорната точка. Ако е по-малък от опорната точка, преместете левия показалец с една стъпка надясно. Продължете, докато левият елемент стане по-голям или равен на опорната точка.
5. Сравнете елемента при десния показалец с опорната точка. Ако е по-голям от опорната точка, преместете десния показалец с една стъпка наляво. Продължете, докато десният елемент стане по-малък или равен на опорната точка.
6. Ако левият показалец е все още по-малък или равен на десния показалец, разменете двата елемента.
7. Увеличете левия показалец и намалете десния.
8. Ако левият индекс е все още по-малък или равен на десния индекс, повторете от стъпка 4. В противен случай върнете индекса на левия указател.

Диаграмата по-горе tracтези движения на показалеца върху примерен масив. Всеки елемент, по-малък от опорната точка, се озовава отляво, а всеки по-голям елемент - отдясно, което е точно това, което върнатият индекс маркира. Разделът по-долу разглежда същия масив стъпка по стъпка.

Как да определим опорния елемент

Изборът на опорна точка е единственото решение, което отличава бързото сортиране от бавното. Ако винаги вземате първи елемент, вече сортиран масив води до най-лошото възможно разделяне: една празна страна и една страна с всеки останал елемент. Това превръща алгоритъма в O(n²). Вземайки среден елементът (дължината на масива, разделена на две) избягва този капан за сортиран и обратно сортиран вход, поради което кодът по-долу го използва.

Често срещани стратегии за завъртане:

• Първи или последен елемент: най-лесно за кодиране, но O(n²) върху сортирани данни.
• Среден елемент: добра стойност по подразбиране, която обработва сортирани и обратно сортирани масиви за O(n log n).
• Случаен елемент: прави невъзможно предварителното конструиране на входни данни за най-лошия случай.
• Медиана от три: взема медианата на първата, средната и последната стойност; стандартният избор в производствените библиотеки.

Сега преминете през бързото сортиране на масива [5,3,7,6,2,9].

За Стъпка 1: Централният елемент е средният елемент. С ляво = 0 и дясно = 5, Math.floor((5 + 0) / 2) дава индекс 2, така че стойността на опорната точка е 7.

За Стъпка 2: Започнете указателите в краищата на масива. Левият указател е на индекс 0 (стойност 5) и десният показалец е на индекс 5 (стойност 9).

За Стъпка 3: Сравнете лявата стойност с опорната точка. 5 < 7, така че преместете надясно до индекс 1. 3 < 7, така че преместете надясно до индекс 2. Стойността там е 7, която не е по-малка от опорната точка, така че левият показалец спира на индекс 2.

За Стъпка 4: Сравнете дясната стойност с опорната точка. 9 > 7, така че преместете наляво до индекс 4. Стойността там е 2, която не е по-голяма от опорната точка, така че десният показалец спира на индекс 4.

За Стъпка 5: Левият индекс (2) е по-малък или равен на десния индекс (4), така че разменете двете стойности. Масивът става [5,3,2,6,7,9].

За Стъпка 6: Преместете и двата показалеца с една стъпка навътре. Левият показалец вече е на индекс 3, а десният показалец - на индекс 3.

За Стъпка 7: Повторете сканирането. Стойността в индекс 3 е 6 и 6 < 7, така че левият показалец се премества до индекс 4. Стойността в индекс 3 не е по-голяма от опорната точка, така че десният показалец остава на индекс 3.

За Стъпка 8: Левият индекс (4) вече е по-голям от десния индекс (3), така че цикълът приключва и функцията връща резултат. 4Всичко преди индекс 4 е по-малко или равно на опорната точка, а всичко от индекс 4 нататък е по-голямо или равно на нея.

Въз основа на това ръководство, ви е необходим код за две операции: swapping два елемента и разделяне на диапазон.

Code да размениш двама Numbers in JavaСценарий

Както показва екранната снимка на редактора по-горе, помощната функция за размяна използва временна променлива, за да размени стойностите на два индекса. Тя променя масива директно и не връща нищо.

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Изход:

[ 9, 3, 7, 6, 2, 5 ]

Code да извършите разделянето

Кодът на екранната снимка по-горе превръща стъпки от 1 до 8 във функция. Двете вътрешни примки придвижете напред указателите, if Блокът извършва размяната, а функцията връща индекса на разделяне.

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Изход:

[ 5, 3, 2, 6, 7, 9 ]
4

Изходът съвпада точно с ръчното ръководство: след едно преминаване през разделяне масивът е [5,3,2,6,7,9], а върнатият индекс на разделяне е 4.

Изпълнете рекурсивното OperaАЦИ

След като разделянето върне индекса на разделяне, използвайте го, за да разделите диапазона и да изпълните бързо сортиране на всяка половина. Ето защо се нарича алгоритъм „Разделяй и владей“. Рекурсията продължава, докато всеки поддиапазон съдържа един елемент, като в този момент целият масив се сортира.

Забележка: Бързото сортиране работи върху един и същ масив през цялото време. В процеса не се създават нови масиви, което го прави алгоритъм на място.

Значи вие се обаждате на дял () функцията, обяснена по-горе, и използвайте нейната връщана стойност, за да разделите масив на части. Ето кодът, който го прави:

Обърнете внимание на двете условия на защита, подчертани на екранната снимка. left < index - 1 потвърждава, че поне два елемента остават от лявата страна и index < right потвърждава същото и за дясната страна. Без тези предпазители функцията би се извиквала вечно в диапазони от един елемент.

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Изход:

[ 2, 3, 5, 6, 7, 9 ]

Пълно бързо сортиране Code

Събирането на частите за swap, partition и recursion дава пълната имплементация:

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

Изход:

[ 2, 3, 5, 6, 7, 9 ]

Горната екранна снимка показва цялата програма в редактора, заедно със сортирания масив в конзолата. Тази имплементация беше проверена спрямо вече сортиран масив, обратно сортиран масив, масиви, съдържащи дублирани и идентични стойности, отрицателни числа, единичен елемент и празен масив и връща правилния резултат във всеки случай.

Времева и пространствена сложност на бързото сортиране

Всяко преминаване на разделяне докосва всеки елемент в диапазона веднъж, така че едно преминаване струва O(n). Следователно общата цена зависи от това колко пъти масивът може да бъде разделен, преди диапазоните да станат тривиални.

Пространствената сложност е O(log n) за тази версия на място. Не се заделя втори масив, така че единствената допълнителна памет е стекът за рекурсия, а балансираното разделяне поддържа този стек с дълбочина около log₂(n) кадъра. В най-лошия случай стекът нараства до O(n) кадъра, поради което много големи масиви могат да препълнят стека за извиквания.

Две числа правят това конкретно. Сортирането на 4,096 случайни стойности с горния код използва приблизително 65 000 сравнения спрямо теоретично n·log₂(n) от 49 152, а най-дълбоката рекурсия достигна 24 кадъра, докато log₂(4096) е 12. И двете цифри са в рамките на малкия константен фактор, очакван от алгоритъм O(n log n).

Бързо сортиране срещу други видове сортиране Algorithms

Бързото сортиране рядко е единствената опция. Таблицата по-долу го сравнява с другите алгоритми, които е най-вероятно да срещнете, за да можете да изберете правилния за вашите данни.

Бързото сортиране обикновено печели на практика, защото вътрешният му цикъл е стегнат и работи в кеш-съвместими съседни диапазони. Изберете сортиране с сливане, когато имате нужда от гарантирано O(n log n) граница или стабилно подреждане, сортиране с куп, когато паметта е изключително ограничена, и сортиране с вмъкване за много малки или почти сортирани масиви. Производствените библиотеки често ги комбинират: интросортирането започва с Бързо сортиране, превключва към сортиране с куп, ако рекурсията стане твърде дълбока, и завършва със сортиране с вмъкване в малки диапазони.

Как бързо да сортирате обекти и низове

Показаната досега имплементация сравнява стойностите с < намлява >, което го ограничава до числа. Реалните приложения трябва да сортират обекти по свойство, низове по азбучен ред или дати по хронологичен ред. Решението е да се премести сравнението в обратно извикване, точно както вграденото sort() прави.

Компараторът получава две стойности и връща отрицателно число, когато първата трябва да е първа, положително число, когато втората трябва да е първа, и нула, когато двете са еквивалентни. Заместването на двете твърдо кодирани сравнения с извиквания на компаратор кара алгоритъма да работи с всеки тип данни.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Изход:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Струва си да се отбележат три детайла. Защитата от рекурсия вече е left >= right, което е правилно за всеки диапазон и не зависи от дължината на външния масив. Сравнението на низове използва localeCompare() така че ударенията и главните и малките букви да се обработват правилно, вместо по суров код. И тъй като бързото сортиране не е стабилно, записите, които споделят една и съща заплата, могат да разменят местата си; сортирайте по втори ключ за разделяне на равенството, ако първоначалният ред е важен за вас.

Готови ли сте да продължите? Укрепете основите с JavaВъведение в скрипта, упражнявайте механиката на показалеца в JavaЦикли на скриптове, обработете повече практически JavaПримери за скриптов код, сравнете реализациите в Сортиране по вмъкване намлява Сортиране на купчинаили добавете статични типове към този алгоритъм с TypeScript справка.

Въпроси и Отговори