Ứng dụng về sắp xếp có ở khắp mọi nơi:
Thuật toán sắp xếp cũng được dùng kết hợp với những thuật toán khác, như tìm kiếm nhị phân, thuật toán Kruskal để tìm cây khung nhỏ nhất của đồ thị.
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.
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 sẽ thấy những cách tiếp cận khác nhau sẽ có thời gian nhanh chậm khác nhau. Các thuật toán sắp xếp cũng vậy. Có rất nhiều cách tiếp cận, với ưu, nhược điểm khác nhau.
Khi so sánh giữa các thuật toán này với nhau, có nhiều vấn đề phải quan tâm.
Trong bài viết này, ta giả sử cần sắp xếp tăng dần các phần tử. Để sắp xếp giảm dần, ta có nhiều cách:
Đây là thuật toán cơ bản nhất cho việc sắp xếp.
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]);
}
Bạn có thể vào VisuAlgo.
Create
ở phía dưới trang để tạo một dãy mớiSort
, rồi Go
để chạy thuật toán.Ý 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, ..., phần tử.
Giả sử ta đã sắp xếp xong phần tử của mảng. Để sắp xếp phần tử đầu tiên, ta tìm vị trí phù hợp của phần tử thứ và "chèn" nó vào đó.
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;
}
Bạn có thể vào VisuAlgo.
Create
ở phía dưới trang để tạo một dãy mớiSort
, rồi Go
để chạy thuật toán.Sắp xếp trộn hoạt động kiểu đệ quy:
int a[MAXN]; // mảng trung gian cho việc sắp xếp
// Sắp xếp các phần tử có chỉ số từ left đến right của mảng data.
void mergeSort(int data[MAXN], int left, int right) {
if (data.length == 1) {
// Dãy chỉ gồm 1 phần tử, ta không cần sắp xếp.
return ;
}
int mid = (left + right) / 2;
// Sắp xếp 2 phần
mergeSort(data, left, mid);
mergeSort(data, mid+1, right);
// Trộn 2 phần đã sắp xếp lại
int i = left, j = mid + 1; // phần tử đang xét của mỗi nửa
int cur = 0; // chỉ số trên mảng a
while (i <= mid || j <= right) { // chừng nào còn 1 phần chưa hết phần tử.
if (i > mid) {
// bên trái không còn phần tử nào
a[cur++] = data[j++];
} else if (j > right) {
// bên phải không còn phần tử nào
a[cur++] = data[i++];
} else if (data[i] < data[j]) {
// phần tử bên trái nhỏ hơn
a[cur++] = data[i++];
} else {
a[cur++] = data[j++];
}
}
// copy mảng a về mảng data
for (int i = 0; i < cur; i++)
data[left + i] = a[i];
}
Bạn có thể vào VisuAlgo.
Create
ở phía dưới trang để tạo một dãy mớiSort
, rồi Go
để chạy thuật toán.Ta lưu mảng vào CTDL Heap.
Ở mỗi bước, ta lấy ra phần tử nhỏ nhất trong heap, cho vào mảng đã sắp xếp.
Heap h = Heap();
for (int i = 0; i < n; i++) {
// thêm phần tử vào heap
h.push(data[i]);
}
int a[MAXN];
for (int i = 0; i < n; i++) {
// lấy phần tử nhỏ nhất và cho vào mảng đã sắp xếp
a[i] = h.pop();
}
sort
của C++ dùng Intro sort, là kết hợp của Quicksort và Insertion Sort).void quickSort(int a[], int left, int right) {
int i = left, j = right;
int pivot = a[left + rand() % (right - left)];
// chia dãy thành 2 phần
while (i <= j) {
while (a[i] < pivot) ++i;
while (a[j] > pivot) --j;
if (i <= j) {
swap(a[i], a[j]);
++i;
--j;
}
}
// Gọi đệ quy để sắp xếp các nửa
if (left < j) quickSort(a, left, j);
if (i < right) quickSort(a, i, right);
}
Bạn có thể vào VisuAlgo.
Create
ở phía dưới trang để tạo một dãy mớiSort
, rồi Go
để chạy thuật toán.Khác với tất cả các thuật toán nêu trên, RadixSort không sử dụng việc so sánh 2 phần tử.
Bạn có thể vào VisuAlgo.
Create
ở phía dưới trang để tạo một dãy mớiSort
, rồi Go
để chạy thuật toán.