Các thuật toán trong javascript

Chắc hẳn ai từng theo học ngành công nghệ thông tin đều từng ngán ngẩm môn “cấu trúc dữ liệu và giải thuật“. Không biết mọi người thế nào, chứ bản thân mình thì môn này trượt lên trượt xuống.

Rồi thời gian trôi nhanh như pet chạy ngoài đồng. Nhìn lại cũng đã đi làm được vài năm, cũng phải va vấp vào thuật toán. Đúng là ghét của nào trời trao của ấy.

Có bạn nào đi phỏng vấn mà bị nhà tuyển dụng hỏi về thuật toán không? Chắc là có đúng không!

Hầu như ai làm về phần mềm thì đều phải làm việc với thuật toán. Bất kể phần mềm lớn hay nhỏ thì đều phải vận dụng thuật toán.

Bài viết này, mình sẽ tổng hợp 5 thuật toán phổ biến nhất mà mọi lập trình viên nên biết.

Cùng bắt đầu nhé.

Chờ chút: Nếu bạn chưa biết thuật toán, đọc lại bài viết này nhé: Thuật toán là gì?

Nội dung chính của bài viết

• 5 thuật toán phổ biến nhất
  • 1. Thuật toán sắp xếp nhanh [Quick Sort]
  • 2. Thuật toán sắp xếp nổi bọt [Bubble Sort]
  • 3. Thuật toán tìm kiếm nhị phân [Binary search]
  • 4. Thuật toán Dijkstra – tìm đường đi ngắn nhất
  • 5. Hashing
  • Tạm kết

5 thuật toán phổ biến nhất

Để các bạn dễ theo dõi, mình sẽ sắp xếp theo mức độ phổ biến của thuật toán.

1. Thuật toán sắp xếp nhanh [Quick Sort]

Thuật toán Quick Sort được phát triển bởi C.A.R

Đúng như tên gọi, thuật toán sắp xếp nhanh là một thuật toán cho kết qua nhanh, gọn, nhẹ. Thuật toán này dựa trên việc chia một mảng thành các mảng nhỏ hơn.

Nếu so với các thuật toán sắp xếp khác như Insertion Sort hay sắp xếp nổi bọt [Bubble Sort], thì thuật toán sắp xếp nhanh cho tốc độ nhanh hơn đáng kể.

Thuật toán Quick sort là một thuật toán chia để trị [divide and Conquer Algorithm]. Nó sẽ chọn một phần tử trong mảng làm điểm đánh dấu [pivot]. Sau khi lựa chọn được điểm pivot, bước tiếp theo sẽ chia mảng thành nhiều mảng con dựa vào pivot đã chọn. Và lặp đi lặp lại như vậy cho đến khi kết thúc.

Tốc độ của thuật toán bị ảnh hưởng bởi việc chọn pivot. Có nhiều cách chọn pivot, dưới đây là một số cách:

• Luôn chọn phần tử đầu tiên của mảng làm pivot.
• Luôn chọn phần tử cuối cùng của mảng.
• Chọn ngẫu nhiên 1 phần tử trong mảng.
• Chọn phần tử có giá trị nằm giữa mảng [median element].

Để mình họa cho thuật toán sắp xếp nhanh, chúng ta cùng thực hành một bài toán: Sắp xếp mảng sau theo thứ tự tăng dần: [10, 7, 8, 9, 1, 5]

Quicksort example program in c++:
#include
#include
 
using namespace std;
 
// Swapping two values.
void swap[int *a, int *b]
{
    int temp; 
    temp = *a;
    *a = *b;
    *b = temp;
}
 
// Partitioning the array on the basis of values at high as pivot value.
int Partition[int a[], int low, int high]
{
    int pivot, index, i;
    index = low;
    pivot = high;
 
    // Getting index of the pivot.
    for[i=low; i < high; i++]
    {
        if[a[i] < a[pivot]]
        {
            swap[&a[i], &a[index]];
            index++;
        }
    }
    // Swapping value at high and at the index obtained.
    swap[&a[pivot], &a[index]];
 
    return index;
}
 
// Random selection of pivot.
int RandomPivotPartition[int a[], int low, int high]
{
    int pvt, n, temp;
    n = rand[];
    // Randomizing the pivot value in the given subpart of array.
    pvt = low + n%[high-low+1];
 
    // Swapping pivot value from high, so pivot value will be taken as a pivot while partitioning.
    swap[&a[high], &a[pvt]];
 
    return Partition[a, low, high];
}
 
int QuickSort[int a[], int low, int high]
{
    int pindex;
    if[low < high]
    {
        // Partitioning array using randomized pivot.
        pindex = RandomPivotPartition[a, low, high];
        // Recursively implementing QuickSort.
        QuickSort[a, low, pindex-1];
        QuickSort[a, pindex+1, high];
    }
    return 0;
}
 
int main[]
{
    int n, i;
    coutn;
 
    int arr[n];
    for[i = 0; i < n; i++]
    {
        cout