QuickSort đệ quy trong JavaScript

Cần viết hàm JavaScript nhận mảng số. Hàm áp dụng thuật toán quicksort để sắp xếp mảng tăng dần hoặc giảm dần.

Thuật toán QuickSort

QuickSort thực hiện các bước sau:

Bước 1 - Chọn bất kỳ phần tử làm pivot (ưu tiên đầu hoặc cuối, nhưng bất kỳ phần tử nào cũng được)

Bước 2 - Phân vùng mảng dựa trên pivot

Bước 3 - Áp dụng quick sort đệ quy cho phân vùng trái

Bước 4 - Áp dụng quick sort đệ quy cho phân vùng phải

Độ phức tạp trung bình và tốt nhất của QuickSort là O(nlogn) trong khi trường hợp xấu có thể chậm đến O(n^2).

Ví dụ

Mã thực hiện như sau:

const arr = [5,3,7,6,2,9]; 
const swap = (arr, leftIndex, rightIndex) => { 
    let temp = arr[leftIndex]; 
    arr[leftIndex] = arr[rightIndex]; 
    arr[rightIndex] = temp; 
}; 
const partition = (arr, left, right) => { 
    let pivot = arr[Math.floor((right + left) / 2)]; 
    let i = left; 
    let j = right; 
    while (i <= j) { 
        while (arr[i] < pivot) { 
            i++; 
        }; 
        while (arr[j] > pivot) { 
            j--; 
        }; 
        if (i <= j) { 
            swap(arr, i, j); //hoán đổi hai phần tử 
            i++; 
            j--; 
        }; 
    }; 
    return i; 
} 
const quickSort = (arr, left = 0, right = arr.length - 1) => { 
    let index; 
    if (arr.length > 1) { 
        index = partition(arr, left, right); 
        if (left < index - 1) { 
            quickSort(arr, left, index - 1); 
        }; 
        if (index < right) { 
            quickSort(arr, index, right); 
        }; 
    } 
    return arr; 
} 
let sortedArray = quickSort(arr); 
console.log(sortedArray);

Kết quả

Kết quả trong console sẽ là:

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