Series học thuật toán bằng Javascript phần 1

Chào anh em, chúc anh em một ngày làm việc hiệu quả và tràn đầy năng lượng.

Hôm nay mình sẽ chia sẻ kiến thức về thuật toán và phần thực hành viết bằng Javascript. Mục đích của bài viết này là để giúp cho anh em mới học front-end có thể hiểu về thuật toán là gì, cách viết một số giải thuật cơ bản bằng Javascript và rèn luyện tư duy logic.

Không để mọi người chờ lâu, cùng bắt đầu nào!

1. Thuật toán là gì?

• Khi mà giải quyết một bài toán thì thuật toán giúp giải quyết bài toán một cách tốt và hiệu quả nhất.
• Ví dụ: như khi làm việc với lượng dữ liệu lớn, cần thuật toán để tối ưu tốc độ xử lý dữ liệu.
• Cơ bản thường gặp thuật toán tìm kiếm và sắp xếp:
  • Thuật toán tìm kiếm một phần tử thỏa mãn điều kiện nào đó trong mảng nhiều phần tử.
  • Cho một mảng sắp xếp mảng theo thứ tự tăng dần, giảm dần.

2. Big O notation

• Big O notation là độ phức tạp của thuật toán.
• Ví dụ:
  • O(1): thường tương ứng với một lệnh bình thường.
  • O(n): duyệt vòng lặp for.
  • O(n^2): duyệt vòng lặp for lồng vòng lặp for.
  • O(logn): duyệt vòng lặp for và xử lý dữ liệu dạng [].push(item).
  • O(n!): trường hợp tệ nhất, có độ phức tạp cao. Sử dụng đệ quy không hợp lý sẽ gặp trường hợp này.
• Theo thứ tự độ phức tạp tăng dần từ O(1) tới O(n!). Độ phức tạp càng thấp thì thuật toán càng tốt.

3. Thuật toán Bubble Sort

• Sắp xếp nổi bọt sẽ đổi vị trí các phần tử với nhau. Phần tử nào lớn (nhỏ) hơn sẽ nổi bọt (đổi chỗ). Lặp lại cho đến khi các phần tử đúng thứ tự.
• Ví dụ các bước chạy thực tế thuật toán bubble sort.

function bubbleSort(array){
  for(var i = 0; i  array.length; i++){
    for(var j = 0; j  ( array.length - i); j++){
      //array.lenth - i để trừ đi lần chạy trước đó
      if(array[j] > array[j+1]){
        //Đổi chỗ vị trí phần tử theo cặp nếu không đúng vị trí.
        var temp = arr[j];
        array[j] = array[j + 1];
        array[j+1] = temp;
      }
    }
  }
  console.log(arr);
}

var arr = [5, 3, 8, 4, 6];
bubbleSort(arr);

• Cách viết ngắn gọn:

function bubbleSort(array){
  for(var i = 0; i  array.length; i++){
    for(var j = 0; j  ( array.length - i); j++){
      //array.lenth - i để trừ đi lần chạy trước đó
      if(array[j] > array[j+1]){
        //Đổi chỗ vị trí phần tử theo cặp nếu không đúng vị trí.
        [array[j], array[j+1]] = [array[j+1], array[j]];
      }
    }
  }
  console.log(arr);
}

var arr = [5, 3, 8, 4, 6];
bubbleSort(arr);

• Độ phức tạp trường hợp xấu nhất: O(n^2). Khá chậm nếu có nhiều dữ liệu.

4. Đổi chỗ 2 phần tử trong mảng theo vị trí

• arr[] = 5, 3, 8, 4, 6
• Đổi chỗ phần tử ở vị trí 1 và 3
• Kết quả: 5, 4, 8, 3, 6

function swap(array, position1, position2) {
  var temp = array[position1];
  array[position1] = array[position2];
  array[position2] = temp;
  console.log(array);
}

//Cách rút gọn
[array[position1], array[position2]] = [array[position2], array[position1]];

5. Thuật toán selection sort

• Thuật toán Selection Sort sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất (xét theo thứ tự tăng dần) từ phần chưa được sắp xếp và đặt nó ở đầu. Thuật toán duy trì hai mảng con:
  • Mảng con đã được sắp xếp.
  • Mảng con còn lại chưa được sắp xếp.

function selectionSort(array){
  for(let i = 0; i  array.length; i++){
    //Tìm kiếm phần tử bé nhất trong dãy chưa được sắp xếp
    let minIndex = i;
    for(let j = i + 1; j  array.length; j++) {
      if(array[j]  array[minIndex])
        minIndex = j;
    }
    //Đổi chỗ phần tử bé nhất với phần tử đầu tiên
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
}

• Thuật toán Selection Sort là một thuật toán khá đơn giản khi cài đặt. Thuật toán này có độ phức tạp là O(n^2) vì có 2 vòng lặp.

6. Tổng kết

• Vậy là chúng ta đã đi đã đi qua phần 1 tổng quan cơ bản về thuật toán trong Javascript và một vài giải thuật cơ bản. Hy vọng bài viết giúp anh em hiểu hơn về thuật toán và cách code một số giải thuật đơn giản.
• Cảm ơn mọi người đã xem bài viết. Chúc mọi người một cuối tuần vui vẻ.
• Nếu có thắc mắc về các phần trong bài này mọi người có thể inbox qua facebook: https://www.facebook.com/FriendsCode-108096425243996. Mình sẽ giải đáp thắc mắc trong tầm hiểu biết. Cảm ơn mọi người!