Trong lập trình C++, các thuật toán sắp xếp là nhóm kiến thức nền tảng mà bất kỳ người học nào cũng phải nắm vững. Hãy cùng Code Dream tìm hiểu nguyên lý hoạt động, đặc điểm của 7+ các thuật toán sắp xếp trong C++ ngay ở bài viết dưới đây nhé!
Sắp xếp nổi bọt (Bubble Sort)
Bubble Sort là thuật toán sắp xếp đơn giản nhất, thường dùng để làm quen với tư duy thuật toán.
Nguyên lý hoạt động
So sánh từng cặp phần tử liền kề trong mảng. Nếu hai phần tử đang đứng sai thứ tự, chúng sẽ được hoán đổi vị trí cho nhau. Quá trình này được lặp đi lặp lại nhiều lần cho đến khi mảng được sắp xếp hoàn toàn.
Đặc điểm
- Dễ hiểu, dễ cài đặt
- Tốc độ chậm với dữ liệu lớn
- Phù hợp cho người mới học C++
Độ phức tạp
- Tốt nhất: O(n)
- Trung bình: O(n²)
- Tệ nhất: O(n²)
Khi nào nên sử dụng
- Khi học thuật toán cơ bản
- Khi dữ liệu nhỏ
- Khi cần hiểu rõ cơ chế so sánh và hoán đổi
Ví dụ mã ban đầu: 5 3 2 4
Code:
#include <iostream>
using namespace std;
void bubbleSort(int a[], int n){
for(int i = 0; i < n-1; i++){
for(int j = 0; j < n-i-1; j++){
if(a[j] > a[j+1]){
swap(a[j], a[j+1]);
}
}
}
}
int main(){
int a[] = {5, 3, 2, 4};
int n = 4;
bubbleSort(a, n);
for(int i = 0; i < n; i++)
cout << a[i] << " ";
}
=> Kết quả: 2 3 4 5
Sắp xếp chọn (Selection Sort)
Selection Sort hoạt động bằng cách chọn phần tử nhỏ nhất và đưa về đúng vị trí.
Nguyên lý hoạt động
Selection Sort hoạt động theo nguyên tắc chọn phần tử nhỏ nhất và đưa về đúng vị trí.
Cách làm cụ thể:
- Chia mảng thành hai phần: phần đã sắp xếp (ban đầu rỗng) và phần chưa sắp xếp
- Trong phần chưa sắp xếp, tìm giá trị nhỏ nhất
- Đổi chỗ giá trị nhỏ nhất đó với phần tử đầu tiên của phần chưa sắp xếp
- Mở rộng phần đã sắp xếp thêm 1 phần tử
Thuật toán lặp lại quá trình này cho đến khi toàn bộ mảng được sắp xếp.
Đặc điểm
- Ít hoán đổi hơn Bubble Sort
- Dễ hiểu nhưng chưa tối ưu
- Phù hợp để học tư duy chọn lọc
Độ phức tạp
- Tốt nhất: O(n²)
- Trung bình: O(n²)
- Tệ nhất: O(n²)
Khi nào nên sử dụng
- Khi muốn giảm số lần hoán đổi phần tử
- Khi học cách tìm giá trị nhỏ nhất hoặc lớn nhất trong mảng
Ví dụ mã ban đầu: 6 4 2 5
Code:
void selectionSort(int a[], int n){
for(int i = 0; i < n-1; i++){
int min = i;
for(int j = i+1; j < n; j++){
if(a[j] < a[min])
min = j;
}
swap(a[i], a[min]);
}
}
=> Kết quả: 2 4 5 6
Sắp xếp chèn (Insertion Sort)
Insertion Sort mô phỏng cách sắp xếp bài trên tay.
Nguyên lý hoạt động
- Giả sử phần tử đầu tiên đã được sắp xếp
- Lấy từng phần tử tiếp theo trong mảng
- So sánh phần tử đó với các phần tử trước nó
- Dịch chuyển các phần tử lớn hơn sang phải
- Chèn phần tử đang xét vào vị trí phù hợp
Quá trình này tiếp tục cho đến khi tất cả phần tử đều được chèn đúng chỗ.
Đặc điểm
- Hoạt động rất tốt với mảng nhỏ
- Hiệu quả khi dữ liệu gần như đã sắp xếp
- Được sử dụng trong nhiều thuật toán nâng cao
Độ phức tạp
- Tốt nhất: O(n)
- Trung bình: O(n²)
- Tệ nhất: O(n²)
Khi nào nên sử dụng
- Khi dữ liệu gần như đã sắp xếp
- Khi kích thước mảng nhỏ
- Khi cần thuật toán đơn giản nhưng hiệu quả
Ví dụ mảng ban đầu: 4 1 3 2
Code :
void insertionSort(int a[], int n){
for(int i = 1; i < n; i++){
int key = a[i];
int j = i - 1;
while(j >= 0 && a[j] > key){
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}
=> Kết quả: 1 2 3 4
Sắp xếp nhanh (Quick Sort)
Quick Sort là một trong những thuật toán sắp xếp nhanh nhất và được sử dụng rộng rãi.
Nguyên lý hoạt động
Quick Sort hoạt động theo tư duy chia để trị, tập trung vào việc chia nhỏ bài toán.
Cụ thể:
- Chọn một phần tử làm pivot
- Sắp xếp lại mảng sao cho:
- Các phần tử nhỏ hơn pivot nằm bên trái
- Các phần tử lớn hơn pivot nằm bên phải
- Pivot lúc này đã ở đúng vị trí
- Áp dụng đệ quy Quick Sort cho hai mảng con bên trái và bên phải pivot
Quá trình chia nhỏ tiếp diễn cho đến khi các mảng con chỉ còn 0 hoặc 1 phần tử.
Cách chọn Pivot
- Chọn phần tử đầu tiên
- Pivot = a[left]
- Ưu điểm: Dễ cài đặt
- Nhược điểm: Rất dễ rơi vào O(n²) nếu mảng gần như đã sắp xếp
- Chọn phần tử cuối cùng
- Pivot = a[right]
- Ưu điểm: Phổ biến, dễ dùng
- Nhược điểm: Giống phần tử đầu → dễ bị worst-case nếu dữ liệu có thứ tự
- Chọn phần tử giữa
- Pivot = a[(left + right) / 2]
- Ưu điểm: Tránh được một phần trường hợp xấu
- Nhược điểm: Không đảm bảo luôn tốt
- Chọn pivot ngẫu nhiên (Random pivot)
- Pivot = phần tử random trong đoạn
- Ưu điểm:
- Giảm khả năng gặp worst-case
- Hiệu năng trung bình tốt O(n log n)
- Nhược điểm: Cần random
Đặc điểm của thuật toán sắp xếp nhanh
- Tốc độ rất nhanh trong thực tế
- Tư duy chia để trị
- Dễ sai nếu không hiểu rõ đệ quy
Độ phức tạp
- Tốt nhất: O(n log n)
- Trung bình: O(n log n)
- Tệ nhất: O(n²)
Khi nào nên sử dụng
- Khi cần tốc độ sắp xếp nhanh
- Khi làm việc với mảng lớn
- Khi hiểu rõ về đệ quy
Sắp xếp trộn (Merge Sort)
Merge Sort là thuật toán sắp xếp ổn định và hiệu quả, đặc biệt với dữ liệu lớn.
Nguyên lý hoạt động
Merge Sort cũng sử dụng chia để trị, nhưng xử lý dữ liệu theo cách ổn định hơn.
- Chia mảng ban đầu thành hai nửa bằng nhau
- Tiếp tục chia nhỏ cho đến khi mỗi mảng con chỉ còn 1 phần tử
- Bắt đầu trộn các mảng con lại với nhau theo thứ tự tăng dần
- Mỗi lần trộn đều đảm bảo mảng kết quả được sắp xếp đúng
Quá trình trộn diễn ra từ các mảng nhỏ đến mảng lớn cho đến khi hoàn tất.
Đặc điểm
- Độ phức tạp ổn định O(n log n)
- Tốn thêm bộ nhớ
- Rất quan trọng trong học thuật
Độ phức tạp
- Tốt nhất: O(n log n)
- Trung bình: O(n log n)
- Tệ nhất: O(n log n)
Khi nào nên sử dụng
- Khi xử lý dữ liệu lớn
- Khi cần thuật toán ổn định
- Khi làm việc với dữ liệu ngoài bộ nhớ
Sắp xếp vun đống (Heap Sort)
Heap Sort dựa trên cấu trúc dữ liệu Heap.
Nguyên lý hoạt động
Heap Sort dựa trên cấu trúc dữ liệu Heap, thường là Max Heap.
Cách hoạt động:
- Chuyển mảng ban đầu thành một Heap hợp lệ
- Phần tử lớn nhất luôn nằm ở đỉnh Heap
- Đưa phần tử lớn nhất về cuối mảng
- Giảm kích thước Heap và điều chỉnh lại Heap
- Lặp lại cho đến khi Heap rỗng.
Nhờ đó, các phần tử được đưa về đúng vị trí theo thứ tự.
Đặc điểm
- Không dùng đệ quy nhiều
- Không cần bộ nhớ phụ
- Tốc độ ổn định
Độ phức tạp
- Tốt nhất: O(n log n)
- Trung bình: O(n log n)
- Tệ nhất: O(n log n)
Khi nào nên sử dụng
- Khi cần thuật toán ổn định về hiệu suất
- Khi không muốn sử dụng nhiều bộ nhớ phụ
Sắp xếp đếm (Counting Sort)
Counting Sort là thuật toán không so sánh, phù hợp với dữ liệu có giá trị giới hạn.
Nguyên lý hoạt động
Counting Sort không sử dụng so sánh giữa các phần tử.
Nguyên lý:
- Xác định giá trị lớn nhất và nhỏ nhất trong mảng
- Tạo một mảng đếm để lưu số lần xuất hiện của từng giá trị
- Duyệt mảng ban đầu và tăng biến đếm tương ứng
- Dựa vào mảng đếm, xây dựng lại mảng đã sắp xếp
Thuật toán hoạt động rất nhanh khi phạm vi giá trị nhỏ và xác định trước.
Đặc điểm
- Rất nhanh với dữ liệu nhỏ, giới hạn rõ
- Không phù hợp với giá trị quá lớn
- Hay dùng trong bài toán đặc thù
Độ phức tạp
- O(n + k)
(k là phạm vi giá trị)
Khi nào nên sử dụng
- Khi giá trị phần tử giới hạn và nhỏ
- Khi cần tốc độ sắp xếp rất nhanh
- Trong các bài toán xử lý dữ liệu dạng số nguyên
Khi nào nên dùng thuật toán nào?
Dưới đây là bảng tổng hợp khi nào nên dùng thuật toán sắp xếp nào, cùng tham khảo nhé!
| Thuật toán | Khi nên dùng |
| Sắp xếp nổi bọt (Bubble Sort) | Dữ liệu rất nhỏ, học cơ bản |
| Sắp xếp chọn (Selection Sort) | Khi muốn giảm số lần đổi chỗ |
| Sắp xếp chèn (Insertion Sort) | Mảng gần như đã sắp xếp |
| Sắp xếp nhanh (Quick Sort) | Tổng quát, nhanh trong thực tế |
| Sắp xếp trộn (Merge Sort) | Cần ổn định, giữ liệu lớn |
| Sắp xếp vun đống (Heap Sort) | Khi cần không dùng thêm bộ nhớ |
| Sắp xếp đếm (Counting Sort) | Số nguyên nhỏ, phạm vi hẹp |
Học thuật toán uy tín tại Code Dream
Để hiểu sâu các thuật toán sắp xếp trong C++, việc chỉ đọc lý thuyết hoặc xem code mẫu trên mạng thường chưa đủ. Nhiều người tự học dễ rơi vào tình trạng học thuộc thuật toán nhưng không hiểu bản chất, nhầm lẫn giữa các cách sắp xếp hoặc không biết áp dụng thuật toán nào cho từng bài toán cụ thể.
Tại Code Dream, các thuật toán sắp xếp trong C++ được giảng dạy theo phương pháp bài bản và có hệ thống. Học viên không chỉ học “thuật toán là gì” mà còn được giải thích từng bước hoạt động bằng ví dụ trực quan, giúp hình dung rõ quá trình sắp xếp diễn ra như thế nào trên mảng dữ liệu. Bên cạnh đó, các thuật toán luôn được đặt lên bàn cân so sánh, từ đó hiểu rõ ưu – nhược điểm và biết khi nào nên dùng Bubble Sort, khi nào Quick Sort hay Merge Sort là lựa chọn phù hợp.
Điểm nổi bật trong chương trình học tại Code Dream là việc kết hợp chặt chẽ giữa code C++ và phân tích độ phức tạp thuật toán. Học viên được hướng dẫn cách đọc, viết và tối ưu code, đồng thời hiểu rõ ý nghĩa của các ký hiệu Big-O trong thực tế. Lộ trình học được thiết kế từ cơ bản đến nâng cao, đi kèm nhiều bài tập thực hành giúp củng cố tư duy thuật toán.
Trên đây là tổng hợp chi tiết các thuật toán sắp xếp trong C++ phổ biến nhất. Hy vọng qua bài viết này, bạn đã có cái nhìn tổng quan và dễ hiểu về thuật toán sắp xếp trong C++, đồng thời biết cách lựa chọn thuật toán phù hợp cho từng bài toán cụ thể. Đăng ký ngay với Code Dream để chi phục các lập trình thuật toán sắp ngay trong hôm nay bạn nhé!
