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

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

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

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

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

Код:

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

Каква е причината да изберете Бързо сортиране пред sort() по подразбиране в JavaСценарий

Въпреки че sort() дава резултата, който искаме, проблемът е в начина, по който сортира елементите на масива. По подразбиране sort() в JavaСкрипт използва вмъкване сортиране by V8 двигател на Chrome намлява Сливане на сортиране by Mozilla Firefox намлява сафари.

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

Така че, за да разберете напълно, трябва да знаете как работи бързото сортиране и да видим това в подробности сега.

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

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

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

И така, това е основната схема на Бързо сортиране. Ето стъпките, които трябва да се следват една по една, за да се извърши бързо сортиране.

Как работи QuickSort

1. Първо намерете "опорна точка" елемент в масива.
2. Стартирайте левия показалец от първия елемент на масива.
3. Стартирайте десния показалец при последния елемент от масива.
4. Сравнете елемента, който сочи с левия показалец и ако е по-малък от основния елемент, преместете левия показалец надясно (добавете 1 към левия индекс). Продължете това, докато левият страничен елемент стане по-голям или равен на шарнирния елемент.
5. Сравнете елемента, сочещ с десния показалец и ако е по-голям от основния елемент, преместете десния показалец наляво (извадете 1 от десния индекс). Продължете това, докато десният страничен елемент стане по-малък или равен на шарнирния елемент.
6. Проверете дали левият показалец е по-малък или равен на десния показалец, след което разменете елементите в местоположенията на тези показалци.
7. Увеличете левия показалец и намалете десния.
8. Ако индексът на левия показалец все още е по-малък от индекса на десния показалец, повторете процеса; иначе връща индекса на левия показалец.

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

Определете Pivot елемент

Но преди да продължим с бързото сортиране, избирането на осевия елемент играе важна роля. Ако изберете първия елемент като основен елемент, тогава той дава най-лоша производителност в сортирания масив. Така че винаги е препоръчително да изберете средния елемент (дължината на масива, разделена на 2) като основен елемент и ние правим същото.

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

За Стъпка 1: Определете опорната точка като среден елемент. така че 7 е основният елемент.

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

За Стъпка 3: Сравнете елемента в левия показалец с основния елемент. Тъй като 5 < 6 измества левия показалец надясно до индекс 1.

За Стъпка 4: Сега, все още 3 <6, така че преместете левия показалец към още един индекс вдясно. Така че сега 7 > 6 спрете да увеличавате левия показалец и сега левият показалец е на индекс 2.

За Стъпка 5: Сега сравнете стойността на десния показалец с основния елемент. Тъй като 9 > 6 преместете десния показалец наляво. Сега, когато 2 < 6, спрете да местите десния показалец.

За Стъпка 6: Разменете двете стойности, присъстващи в левия и десния указател, една с друга.

За Стъпка 7: Преместете двата показалеца с още една стъпка.

За Стъпка 8: Тъй като 6 = 6, преместете показалците на още една стъпка и спрете, когато левият показалец пресича десния показалец и върнете индекса на левия показалец.

И така, тук, въз основа на горния подход, трябва да напишем код за размяна на елементи и разделяне на масива, както е споменато в горните стъпки.

Код за размяна на две числа JavaСценарий

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); //swap 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 result = quickSort(items, 0, items.length - 1);

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

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); //sawpping 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); //prints [2,3,5,6,7,9]

ЗАБЕЛЕЖКА: Бързото сортиране работи с Времевата сложност на O(nlogn).