Thuật toán sắp xếp nhanh trong JavaScript

Sắp xếp là gì?

Sắp xếp không gì khác hơn là sắp xếp các phần tử theo thứ tự mà chúng ta muốn. Bạn có thể đã gặp điều này trong thời đi học hoặc đại học. Giống như sắp xếp các số từ nhỏ đến lớn (tăng dần) hoặc từ lớn đến nhỏ (giảm dần) là những gì chúng ta đã thấy cho đến nay và được gọi là sắp xếp.

Sắp xếp mặc định JavaScript

Như đã đề cập trước đây, JavaKịch bản có sắp xếp (). Chúng ta hãy lấy một ví dụ với một vài mảng phần tử như [5,3,7,6,2,9] và muốn sắp xếp các phần tử mảng này theo thứ tự tăng dần. Chỉ cần gọi sắp xếp () trên mảng mục và sắp xếp các phần tử mảng theo thứ tự tăng dần.

Mã Code:

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

Lý do để chọn Sắp xếp nhanh thay vì sắp xếp mặc định() trong JavaScript

Mặc dù Sort() cho kết quả như mong muốn nhưng vấn đề nằm ở cách nó sắp xếp các phần tử mảng. Sắp xếp mặc định() trong JavaSử dụng tập lệnh sắp xếp chèn by Động cơ V8 của Chrome và Hợp nhất sắp xếp by Mozilla Firefox và Safari.

Tuy nhiên, điều này không phù hợp nếu bạn cần sắp xếp số lượng lớn các phần tử. Vì vậy, giải pháp là sử dụng Sắp xếp nhanh cho tập dữ liệu lớn.

Vì vậy, để hiểu đầy đủ, bạn cần biết cách Sắp xếp nhanh hoạt động và chúng ta hãy xem chi tiết điều đó ngay bây giờ.

Sắp xếp nhanh là gì?

Sắp xếp nhanh sau Phân chia và chinh phục thuật toán. Nó đang chia các phần tử thành các phần nhỏ hơn dựa trên một số điều kiện và thực hiện các thao tác sắp xếp trên các phần được chia nhỏ hơn đó. Do đó, nó hoạt động tốt cho các tập dữ liệu lớn. Vì vậy, đây là các bước cách tính năng Sắp xếp nhanh hoạt động bằng những từ đơn giản.

1. Đầu tiên chọn một phần tử được gọi là pivot thành phần.
2. Tiếp theo, so sánh tất cả các phần tử mảng với phần tử trục đã chọn và sắp xếp chúng theo cách sao cho các phần tử nhỏ hơn phần tử trục nằm ở bên trái và lớn hơn phần tử trục xoay ở bên phải.
3. Cuối cùng, thực hiện các thao tác tương tự trên các phần tử bên trái và bên phải đối với phần tử trụ.

Vì vậy, đó là nội dung cơ bản của Sắp xếp nhanh. Dưới đây là các bước cần được thực hiện từng bước một để thực hiện Sắp xếp nhanh.

QuickSort hoạt động như thế nào

1. Đầu tiên hãy tìm "trục" phần tử trong mảng.
2. Bắt đầu con trỏ bên trái ở phần tử đầu tiên của mảng.
3. Bắt đầu con trỏ bên phải ở phần tử cuối cùng của mảng.
4. So sánh phần tử trỏ với con trỏ trái và nếu nó nhỏ hơn phần tử trụ thì di chuyển con trỏ trái sang phải (thêm 1 vào chỉ số bên trái). Tiếp tục điều này cho đến khi phần tử bên trái lớn hơn hoặc bằng phần tử trụ.
5. So sánh phần tử trỏ với con trỏ phải và nếu nó lớn hơn phần tử trụ thì di chuyển con trỏ phải sang trái (trừ 1 cho chỉ số bên phải). Tiếp tục điều này cho đến khi phần tử bên phải nhỏ hơn hoặc bằng phần tử trụ.
6. Kiểm tra xem con trỏ bên trái có nhỏ hơn hoặc bằng con trỏ bên phải hay không, sau đó hoán đổi các phần tử ở vị trí của các con trỏ này.
7. Tăng con trỏ bên trái và giảm con trỏ bên phải.
8. Nếu chỉ số của con trỏ bên trái vẫn nhỏ hơn chỉ số của con trỏ bên phải thì lặp lại quy trình; nếu không thì trả về chỉ mục của con trỏ bên trái.

Vì vậy, chúng ta hãy xem các bước này bằng một ví dụ. Chúng ta hãy xem xét mảng phần tử mà chúng ta cần sắp xếp là [5,3,7,6,2,9].

Xác định phần tử Pivot

Nhưng trước khi tiếp tục với tính năng Sắp xếp nhanh, việc chọn phần tử trục đóng vai trò chính. Nếu bạn chọn phần tử đầu tiên làm phần tử trụ thì nó sẽ mang lại hiệu suất kém nhất trong mảng được sắp xếp. Vì vậy, luôn nên chọn phần tử ở giữa (độ dài của mảng chia cho 2) làm phần tử trụ và chúng ta cũng làm như vậy.

Dưới đây là các bước để thực hiện Sắp xếp nhanh được hiển thị với ví dụ [5,3,7,6,2,9].

BƯỚC 1: Xác định trục là phần tử ở giữa. Vì thế, 7 là phần tử trục.

BƯỚC 2: Bắt đầu con trỏ trái và phải lần lượt là phần tử đầu tiên và cuối cùng của mảng. Vì vậy, con trỏ trái đang trỏ tới 5 tại chỉ số 0 và con trỏ bên phải đang trỏ tới 9 ở chỉ số 5.

BƯỚC 3: So sánh phần tử ở con trỏ bên trái với phần tử trụ. Vì 5 < 6 dịch chuyển con trỏ trái sang phải tới chỉ số 1.

BƯỚC 4: Bây giờ, vẫn là 3 <6 nên hãy chuyển con trỏ sang trái sang một chỉ mục nữa ở bên phải. Vì vậy, bây giờ 7 > 6 dừng tăng con trỏ trái và bây giờ con trỏ trái ở chỉ số 2.

BƯỚC 5: Bây giờ, so sánh giá trị ở con trỏ bên phải với phần tử trụ. Vì 9 > 6 hãy di chuyển con trỏ phải sang trái. Bây giờ khi 2 < 6 dừng di chuyển con trỏ bên phải.

BƯỚC 6: Hoán đổi cả hai giá trị hiện tại ở con trỏ trái và phải với nhau.

BƯỚC 7: Di chuyển cả hai con trỏ thêm một bước nữa.

BƯỚC 8: Vì 6 = 6, di chuyển con trỏ tới một bước nữa và dừng lại khi con trỏ trái vượt qua con trỏ bên phải và trả về chỉ mục của con trỏ trái.

Vì vậy, ở đây dựa trên cách tiếp cận trên, chúng ta cần viết mã để hoán đổi các phần tử và phân vùng mảng như đã đề cập ở các bước trên.

Mã để hoán đổi hai số trong JavaScript

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

Mã để thực hiện phân vùng như đã đề cập ở các bước trên

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;
}

Thực hiện thao tác đệ quy

Sau khi thực hiện các bước trên, chỉ mục của con trỏ bên trái sẽ được trả về và chúng ta cần sử dụng chỉ số đó để chia mảng và thực hiện Sắp xếp nhanh trên phần đó. Do đó, nó được gọi là thuật toán Chia để trị.

Vì vậy, sắp xếp nhanh được thực hiện cho đến khi tất cả các phần tử ở mảng bên trái và mảng bên phải được sắp xếp.

Lưu ý: Sắp xếp nhanh được thực hiện trên cùng một mảng và không có mảng mới nào được tạo trong quy trình.

Vì vậy, chúng ta cần gọi đây là vách ngăn() đã giải thích ở trên và dựa vào đó chúng tôi chia mảng vào các bộ phận. Vì vậy, đây là mã nơi bạn sử dụng nó,

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);

Hoàn thành mã sắp xếp nhanh

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]

LƯU Ý: Sắp xếp nhanh chạy với Độ phức tạp thời gian của O(nlogn).