ARRAY SORTING – VẤN ĐỀ MUÔN THUỞ
Javascript
199
sorting
1
#Javascript
22
White

Lam Pham viết ngày 04/02/2018

Từ xưa đến nay, sắp xếp giữ một vai trò vô cùng quan trọng. Nhiều ứng dụng (từ điển, danh bạ, quản lý tài khoản,…) thường có chức năng sắp xếp theo thứ tự từ điển (a-z). Việc này giúp cho người quản lý và người dùng dễ dàng tìm kiếm nội dung hơn. Do đó, trong bài viết này, tôi sẽ cùng với các bạn tìm hiểu về vấn đề Array Sorting trong JavaScript.

Về sắp xếp nói chung, chúng ta có rất nhiều thuật toán với độ phức tạp khác nhau, có thể kể đến là: selection sort, insertion sort, binary insertion sort, interchange sort, bubble sort, shaker sort, quick sort, merge sort, heap sort,…

(Xem thêm hai bài tổng hợp về thuật toán sắp xếp trong C/C++: phần 1, phần 2)

Tuy nhiên, bạn không cần thiết phải implement lại những thuật toán sắp xếp này. Vì JavaScript hỗ trợ sẵn cho chúng ta một function để sắp xếp.

Cú pháp:

arr.sort()
arr.sort(compareFunction)

Tham số

compareFunction: dùng để xác định thứ tự sắp xếp. Nếu bạn bỏ qua tham số này thì mặc định JavaScript sẽ sắp xếp theo thứ tự tăng dần trong bảng mã Unicode (hay đơn giản thì cứ gọi là thứ tự tăng dần bảng chữ cái).

Giá trị trả về

Mảng đã được sắp xếp (và mảng ban đầu có bị thay đổi).

var a = ['c', 'g', 'w', 'a'];
var b = a.sort();
console.log(a); // => ["a", "c", "g", "w"]
console.log(b); // => ["a", "c", "g", "w"]

Tìm hiểu compareFunction

Hàm compareFunction dùng để xác định thứ tự sắp xếp. Nếu a và b là hai phần tử dùng để so sánh thì:

  • Nếu compareFunction(a, b) trả về < 0 thì a sẽ đứng trước b.
  • Nếu compareFunction(a, b) trả về > 0 thì a sẽ đứng sau b.
  • Nếu compareFunction(a, b) trả về = 0 thì không sắp xếp (giữ nguyên thứ tự).

Array sorting với numbers

JavaScript hỗ trợ sắp xếp nhiều kiểu dữ liệu. Tuy nhiên, phổ biến nhất vẫn là numbers. Và như tôi đã nói ở trên, mặc định hàm sort sẽ so sánh theo kiểu string. Do đó, kết quả sẽ như thế này:

var a = [9, 100, 45, 33];
console.log(a.sort());
// => [100, 33, 45, 9]

Bạn không nhìn lầm đâu. Kết quả trên là hoàn toàn chính xác. Vì khi so sánh theo kiểu string thì ‘1’ < ‘3’ < ‘4’ < ‘9’. Vì vậy, để sắp xếp chúng theo kiểu numbers thì bạn cần phải sử dụng hàm compareFunction.

Sử dụng hàm compareNumbers sắp xếp numbers theo thứ tự tăng dần

function compareNumbers(a, b) {
  return a - b;
}
var a = [9, 100, 45, 33];
console.log(a.sort(compareNumbers));
// => [9, 33, 45, 100]

Theo đúng mô tả của hàm compareFunction, khi a < b => a – b < 0 => a sẽ đứng trước b. Nghĩa là số bé hơn sẽ đứng trước. Áp dụng quy tắc này, ta được mảng các số sắp xếp theo thứ tự tăng dần.

Ngoài cách viết hàm riêng như trên, bạn có thể áp dụng JavaScript closures:

var a = [9, 100, 45, 33];
console.log(a.sort(function(a, b){
    return a - b;
}));
// => [9, 33, 45, 100]

Sắp xếp numbers theo thứ tự giảm dần

Để sắp xếp mảng numbers theo thứ tự giảm dần thì bạn chỉ cần thay đổi nội dung hàm compareNumbers. Thay vì return a – b thì bây giờ tôi sẽ return b – a.

var a = [9, 100, 45, 33];
console.log(a.sort(function(a, b){
    return b - a;
}));
// => [100, 45, 33, 9]

Bây giờ, khi a < b => b – a > 0 => a sẽ đứng sau b. Nghĩa là số nhỏ hơn sẽ đứng sau. Do đó, kết quả thu được là dãy số giảm dần như trên.

Trên đây là cách sử dụng hàm sort (mặc định) của JavaScript để sắp xếp mảng. Tuy nhiên, nếu như bạn không muốn sử dụng hàm mặc định này thì bạn vẫn có thể tự implement sử dụng một số thuật toán sắp xếp cơ bản.

Array sorting trong JavaScript sử dụng thuật toán

Nếu bạn từng học ít nhất một ngôn ngữ lập trình như C/C++, Java,… thì tôi dám chắc là bạn đã implement thuật toán sắp xếp rồi.

Một số thuật toán cơ bản là:

  • Thuật toán sắp xếp chọn trực tiếp – Selection Sort
  • Sắp xếp chèn trực tiếp – Insertion Sort
  • Sắp xếp chèn trực tiếp dựa trên tìm kiếm nhị phân – Binary Insertion Sort
  • Thuật toán sắp xếp đổi chỗ trực tiếp – Interchange Sort
  • Sắp xếp nổi bọt – Bubble Sort
  • Thuật toán Shaker Sort
  • Sắp xếp nhanh – Quick Sort
  • Sắp xếp trộn – Merge Sort
  • Sắp xếp vun đống – Heap Sort

Array sorting với sắp xếp chọn trực tiếp – Selection Sort

function selectionSort(array){
 for(let i = 0; i < array.length - 1; i++){
   let idmin = i;
   for(let j = i + 1; j < array.length; j++){
     if(array[j] < array[idmin]) idmin = j;
   }

   // swap
   let t = array[i];
   array[i] = array[idmin];
   array[idmin] = t; 
 }
}

Sắp xếp chèn trực tiếp – Insertion Sort

function insertionSort(array){
  let pos, x;
  for(let i = 1; i < array.length; i++){
    pos = i - 1;
    x = array[i];
    while(pos >= 0 && array[pos] > x){
      array[pos + 1] = array[pos];
      pos--; 
    }
    array[pos + 1] = x;
  }
}

Sắp xếp chèn trực tiếp dựa trên tìm kiếm nhị phân – Binary Insertion Sort

function binaryInsertionSort(array){
 let l, r, m, x;
 for(let i = 1; i < array.length; i++){
   l = 0;
   r = i - 1;
   x = array[i];

   while(l <= r){
     m = Math.floor((l + r) / 2);
     if(array[m] > x) r = m - 1;
     else l = m + 1;
   }

   for(let j = i; j > l; j--)
     array[j] = array[j - 1];
   array[l] = x;
 }
}

Sắp xếp đổi chỗ trực tiếp – Interchange Sort

function interChangeSort(array){
 for(let i = 0; i < array.length - 1; i++){
   for(let j = i + 1; j < array.length; j++){
     if(array[j] < array[i]){
       let t = array[i];
       array[i] = array[j];
       array[j] = t;
     }
   }
 }
}

Sắp xếp nổi bọt – Bubble Sort

function bubbleSort(array){
 for(let i = 0; i < array.length - 1; i++){
   for(let j = array.length - 1; j > i; j--){
     if(array[j] < array[j-1]){
       let t = array[j];
       array[j] = array[j - 1];
       array[j - 1] = t;
     }
   }
 }
}

Thuật toán Shaker Sort

function shakerSort(array){
    let left, right, k;

    left = 0;
    right = array.length - 1;
    k = array.length - 1;

    while(left < right)
    {       
        for(let j = right; j > left; j--)
        {
            if(array[j] < array[j - 1])
            { 
                let t = array[j];
                array[j] = array[j - 1];
                array[j - 1] = t;
                k = j;  
            }              
        }
        left = k;

        for (let j = left; j < right; j++)
        {  
            if (array[j] > array[j + 1])
            { 
                let t = array[j];
                array[j] = array[j + 1];
                array[j + 1] = t;
                k = j;
            }    
        } 
        right = k;
    }
}

Sắp xếp nhanh – Quick Sort

function quickSort(array, left, right){
    let l = left, r = right;
    let m = Math.floor((l + r) / 2);
    let pivot = array[m];

    while(l <= r){
        while(array[l] < pivot) l++;
        while(array[r] > pivot) r--;
        if(l <= r){
            let t = array[l];
            array[l] = array[r];
            array[r] = t;
            l++;
            r--;
        }
    }

    if(l < right) quickSort(array, l, right);
    if(r > left) quickSort(array, left, r);
}

Sắp xếp trộn – Merge Sort

function merge(array, left, m, right){
    let l = left, r = m + 1;
    let tmp = [];

    while(l <= m && r <= right){
        if(array[l] < array[r]) tmp.push(array[l++]);
        else tmp.push(array[r++]);
    }

    while(l <= m) tmp.push(array[l++]);
    while(r <= right) tmp.push(array[r++]);

    for(let i = 0; i < tmp.length; i++)
        array[i + left] = tmp[i];
}

function mergeSort(array, left, right){
    if(left < right){
        let m = Math.floor((left + right) / 2);
        mergeSort(array, left, m);
        mergeSort(array, m + 1, right);
        merge(array, left, m, right);
    }
}

Sắp xếp vun đống – Heap Sort

function heapify(array, N, i){
    let left = 2*i + 1, right = 2*i + 2, largest;

    if(left < N && array[left] > array[i]) largest = left;
    else largest = i;

    if(right < N && array[right] > array[largest]) largest = right;

    if(largest != i){
        let t = array[i];
        array[i] = array[largest];
        array[largest] = t;
        heapify(array, N, largest);
    }
}

function buildHeap(array){
    let m = Math.floor(array.length / 2 - 1);
    for(let i = m; i >= 0; i--)
        heapify(array, array.length, i);
}

function heapSort(array){
    buildHeap(array);

    for(let i = array.length - 1; i >= 0; i--)    {
        let t = array[0];
        array[0] = array[i];
        array[i] = t;

        heapify(array, i, 0);
    }
}

Trên đây là những vấn đề cơ bản về Array Sorting, cùng với một số thuật toán sắp xếp. Theo tôi, đây là những kiến thức cơ bản và có thể được áp dụng rất nhiều.

Cuối cùng, xin chào và hẹn gặp lại ở bài viết sau trong series JavaScript cơ bản.

Thân ái,

Tham Khảo

Bản gốc: Blog Complete JavaScript
Facebook Fanpage: Complete JavaScript
Facebook Group: Hỏi đáp JavaScript VN

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Lam Pham

17 bài viết.
16 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
14 5
Trước khi vào nội dung bài viết. Tôi xin đính chính giúp anh trả lời những câu hỏi chỉ là tựa đề của một bài hát tôi không có ý xưng hô là anh. Bài...
Lam Pham viết 23 ngày trước
14 5
White
10 6
Có thể bạn thừa biết, JavaScript là một ngôn ngữ chạy (Link). Điều đó có nghĩa là nếu bạn thực hiện một tác vụ quá lớn trên giao diện chính thì khả...
Lam Pham viết 1 tháng trước
10 6
White
3 0
Nếu bạn theo dõi các bài viết của tôi từ đầu tới giờ thì có thể thấy tôi đã giới thiệu với các bạn về (Link), (Link) và (Link). Hôm nay, tôi sẽ tiế...
Lam Pham viết 1 tháng trước
3 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
17 bài viết.
16 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!