0%
Loading...

Các thuật toán sắp xếp hay trong lập trình

Time: 07:32 19/05/2023 | Cao Văn Vinh

---------------------------------

Vì sao chúng ta phải học nhiều thuật toán sắp xếp? Khi code, bạn chỉ cần biết cài một thuật toán sắp xếp là đủ. Hoặc nếu bạn code C++ hay Java, bạn chỉ cần biết cách gọi thư viện. Tuy nhiên, các thuật toán sắp xếp khác nhau cho ta nhiều ý tưởng hay và độc đáo - điều này vô cùng hữu ích khi các bạn học các thuật toán khác.

Vậy, sắp xếp là gì? Hãy thử tưởng tượng bạn có một bộ bài đã được xáo, và bạn muốn sắp xếp lại các lá bài theo thứ tự tăng dần. Bạn sẽ làm như nào? Có rất nhiều cách tiếp cận khác nhau. Bạn có thể trải bài ra và xếp chúng, hoặc chia bộ bài thành những nhóm nhỏ rồi gộp lại... Bạn sẽ thấy những cách này có độ nhanh chậm khác nhau!

Ứng dụng về sắp xếp có ở khắp mọi nơi:
- Một danh sách lớp với các học sinh được sắp xếp theo thứ tự bảng chữ cái.
- Một danh bạ điện thoại.
- Danh sách các truy vấn được tìm kiếm nhiều nhất trên Google. .

Trong bài viết này, mình giả sử cần sắp xếp tăng dần các phần tử. Mình giới thiệu cho các bạn 3 thuật toán dễ hiểu nhất, những thuật toán khó hiểu hơn bạn có thể tự tìm hiểu thêm trên internet nhé!

1. Sắp xếp nổi bọt (Bubble sort):

for (int i = 0; i < n; i++)
for (int j = 0; j < n - 1; j++)
if (a[j] > a[j+1]) {
swap(a[j], a[j+1]);
}

Giải thích:
- Xét lần lượt các cặp 2 phần tử liên tiếp. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước, ta đổi chỗ 2 phần tử. Nói cách khác, phần tử nhỏ nhất sẽ nổi lên trên.
- Lặp lại đến khi không còn 2 phần tử nào thỏa mãn. Có thể chứng minh được số lần lặp không quá N−1 , do một phần tử chỉ có thể nổi lên trên không quá N−1 lần.
- Mình đánh giá code này rất dễ hiểu!

2. Sắp xếp chèn (Insertion Sort)

for (int i = 1; i < n; i++) {
// Tìm vị trí phù hợp cho i
int j = i;
while (j > 0 && data[i] < data[j-1]) --j;
// Đưa i về đúng vị trí
int tmp = data[i];
for (int k = i; k > j; k--)
data[k] = data[k-1];
data[j] = tmp;
}

Giải thích:
- Ý tưởng chính của thuật toán là ta sẽ sắp xếp lần lượt từng đoạn gồm 1 phần tử đầu tiên, 2 phần tử đầu tiên, …, N phần tử.
- Giả sử ta đã sắp xếp xong phần tử của mảng. Để sắp xếp i+1 phần tử đầu tiên, ta tìm vị trí phù hợp của phần tử thứ i+1 và "chèn" nó vào đó.
- Mình đánh giá code này không đủ nhanh để thực hiện với dữ liệu lớn!

3. Sắp xếp lựa chọn (Selection Sort)

void selectionSort(int a[], int n){
int i, j, min, temp;
for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++){
if (a[j] < a[min]) min = j;
}
swap(a[i], a[min]);
}
}

Giải thích:
- Ý tưởng chính của thuật toán là sắp xếp phần tử nhỏ nhất vào vị trí 0,1,2,3...
- Tìm phần tử nhỏ nhất đưa vào vị trí 1
- Tìm phần tử nhỏ tiếp theo đưa vào vị trí 2
- Tìm phần tử nhỏ tiếp theo đưa vào vị trí 3
...

Có thể bạn quan tâm


Instagram YouTube Discord Github Facebook Contact Phone
Check Internet Connection