Tóm Tắt
Thuật toán sắp xếp
####### Ứ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.
####### 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:
####### Chia bộ bài theo giá trị: 2, 3, 4… Rồi gộp lại.
####### Trải tất cả các lá bài ra, rồi lần lượt lấy lá bài nhỏ nhất.
####### Chia bộ bài ra thành nhiều nhóm nhỏ. Với mỗi nhóm, sắp xếp lại, sau đó gộp các nhóm lại với
####### nhau theo thứ tự tăng dần.
####### 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.
####### 1. Thời gian chạy. Đối với các dữ liệu rất lớn, các thuật toán không hiệu quả sẽ chạy rất chậm và
####### không thể ứng dụng trong thực tế.
####### 2. Bộ nhớ. Các thuật toán nhanh đòi hỏi đệ quy sẽ có thể phải tạo ra các bản copy của dữ liệu đang
####### xử lí. Với những hệ thống mà bộ nhớ có giới hạn (ví dụ embedded system), một vài thuật toán sẽ
####### không thể chạy được.
Giới thiệu
Những điểm cần chú ý
####### 3. Độ ổn định ( stability ). Độ ổn định được định nghĩa dựa trên điều gì sẽ xảy ra với các phần tử có
####### giá trị giống nhau.
####### Đối với thuật toán sắp xếp ổn định, các phần tử bằng với giá trị bằng nhau sẽ giữ nguyên thứ
####### tự trong mảng trước khi sắp xếp.
####### Đối với thuật toán sắp xếp không ổn định, các phần tử có giá trị bằng nhau sẽ có thể có thứ
####### tự bất kỳ.
####### 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:
####### Sửa đổi thuật toán một cách phù hợp.
####### Sắp xếp, sau đó đảo ngược thứ tự các phần tử.
####### Định nghĩa lại việc so sánh nhỏ hơn.
####### Đây là thuật toán cơ bản nhất cho việc sắp xếp.
####### 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á
####### , do một phần tử chỉ có thể nổi lên trên không quá lần.
####### Code đơn giản, dễ hiểu
####### Không tốn thêm bộ nhớ
####### Độ phức tạp , không đủ nhanh với dữ liệu lớn.
for ( int i = 0 ; i < n; i ++ )
for ( int j = 0 ; j < n – 1 ; j ++ )
if (a[j] > a[j + 1 ]) {
Sắp xếp nổi bọt (Bubble sort)
Ý tưởng
N−1 N−
Ưu điểm
Nhược điểm
O()N 2
Code
data[k] = data[k – 1 ];
data[j] = tmp;
}
####### Bạn có thể vào VisuAlgo.
####### Chọn Insert ở thanh menu bên trên.
####### Ấn vào nút Create ở phía dưới trang để tạo một dãy mới
####### Ấn vào Sort, rồi Go để chạy thuật toán.
####### Sắp xếp trộn hoạt động kiểu đệ quy:
####### Đầu tiên chia dữ liệu thành 2 phần, và sắp xếp từng phần.
####### Sau đó gộp 2 phần lại với nhau. Để gộp 2 phần, ta làm như sau:
####### Tạo một dãy mới để chứa các phần tử đã sắp xếp.
####### So sánh 2 phần tử đầu tiên của 2 phần. Phần tử nhỏ hơn ta cho vào và xóa khỏi phần
####### tương ứng.
####### Tiếp tục như vậy đến khi ta cho hết các phần tử vào dãy.
####### Chạy nhanh, độ phức tạp.
####### Ổn định
####### Cần dùng thêm bộ nhớ để lưu mảng A.
int a[MAXN]; // mảng trung gian cho việc sắp xếp
Minh họa
Sắp xếp trộn (Merge sort)
Ý tưởng
A
A
A
Ưu điểm
O(N∗logN)
Nhược điểm
Code
// 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 == 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.
####### Chọn Merge ở thanh menu bên trên.
####### Ấn vào nút Create ở phía dưới trang để tạo một dãy mới
####### Ấn vào Sort, rồi Go để chạy thuật toán.
Minh họa
Sắp xếp vun đống (HeapSort)
Ý tưởng
####### Chạy nhanh (nhanh nhất trong các thuật toán sắp xếp dựa trên việc só sánh các phần tử). Do đó
####### quicksort được sử dụng trong nhiều thư viện của các ngôn ngữ như Java, C++ (hàm sort của
####### C++ dùng Intro sort, là kết hợp của Quicksort và Insertion Sort).
####### Tùy thuộc vào cách chia thành 2 phần, nếu chia không tốt, độ phức tạp trong trường hợp xấu
####### nhất có thể là. Nếu ta chọn pivot ngẫu nhiên, thuật toán chạy với độ phức tạp trung bình
####### là (trong trường hợp xấu nhất vẫn là , nhưng ta sẽ không bao giờ gặp phải
####### trường hợp đó).
####### Không ổn định.
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.
####### Chọn Quick ở thanh menu bên trên.
####### Ấn vào nút Create ở phía dưới trang để tạo một dãy mới
####### Ấn vào Sort, rồi Go để chạy thuật toán.
Nhược điểm
O()N 2
O(N∗logN) O()N 2
Code
Minh họa
Sắp xếp cơ số (RadixSort)
####### 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ử.
####### Đầu tiên, thuật toán sẽ chia các phần tử thành các nhóm, dựa trên chữ số cuối cùng (hoặc dựa
####### theo bit cuối cùng, hoặc vài bit cuối cùng).
####### Sau đó ta đưa các nhóm lại với nhau, và được danh sách sắp xếp theo chữ số cuối của các phần
####### tử. Quá trình này lặp đi lặp lại với chữ số át cuối cho tới khi tất cả vị trí chữ số đã sắp xếp.
####### Có thể chạy nhanh hơn các thuật toán sắp xếp sử dụng so sánh. Ví dụ nếu ta sắp xếp các số
####### nguyên 32 bit, và chia nhóm theo 1 bit, thì độ phức tạp là. Trong trường hợp tổng quát, độ
####### phức tạp là
####### Không thể sắp xếp số thực.
####### Bạn có thể vào VisuAlgo.
####### Chọn Radix ở thanh menu bên trên.
####### Ấn vào nút Create ở phía dưới trang để tạo một dãy mới
####### Ấn vào Sort, rồi Go để chạy thuật toán.
####### Topcoder
####### VisuAlgo
####### Wikipedia
Ý tưởng
Ưu điểm
O(N)
O(N∗log(max()))ai
Nhược điểm
Minh họa
Nguồn tham khảo
Like 0 Share Save to Facebook
Đừng quên đăng ký kênh Youtube Khiêm Lê để ủng hộ mình nha!
Sắp xếp chọn (Selection Sort)
Sắp xếp chọn hay selection sort sẽ là thuật toán thứ hai mà mình giới thiệu đến các bạn, ý
tưởng của thuật toán này như sau: duyệt từ đầu đến phần tử kề cuối danh sách, duyệt tìm
phần tử nhỏ nhất từ vị trí kế phần tử đang duyệt đến hết, sau đó đổi vị trí của phần tử nhỏ
nhất đó với phần tử đang duyệt và cứ tiếp tục như vậy.
Cho mảng A có n phần tử chưa được sắp xếp. Cụ thể các bước của giải thuật này áp dụng
trên mảng A như sau:
-
Gán i = 0
-
Gán j = i + 1 và min = A[i]
-
Nếu j < n:
Nếu A[j] < A[min] thì min = j
j = j + 1
Quay lại bước 3
- Đổi chỗ A[min] và A[i]
- Nếu i < n – 1:
Đúng thì i = i + 1 và quay lại bước 2
Sai thì dừng lại
Ý tưởng và từng bước giải cụ thể đã có, bây giờ mình sẽ sử dụng thuật toán này trong C++:
Đối với thuật toán sắp xếp chọn, do sử dụng 2 vòng lặp lồng vào nhau, độ phức tạp thời
gian trung bình của thuật toán này là O(n ). Thuật toán sắp xếp chọn mình cài đặt là thuật
toán sắp xếp không ổn định, nó còn có một phiên bản khác cải tiến là thuật toán sắp xếp
chọn ổn định.
Giải thích ý tưởng thuật toán:
Thuật toán sắp xếp chọn | Khiêm Lê
Xem tiếp…
void SelectionSort ( int A[], int n)
{
int min;
for ( int i = 0 ; i < n – 1 ; i++)
{
min=i; // tạm thời xem A[i] là nhỏ nhất
2
Sắp xếp chèn (Insertion Sort)
Sắp xếp chèn hay insertion sort là thuật toán tiếp theo mà mình giới thiệu, ý tưởng của
thuật toán này như sau: ta có mảng ban đầu gồm phần tử A[0] xem như đã sắp xếp, ta sẽ
duyệt từ phần tử 1 đến n – 1, tìm cách chèn những phần tử đó vào vị trí thích hợp trong
mảng ban đầu đã được sắp xếp.
Giả sử cho mảng A có n phần tử chưa được sắp xếp. Các bước thực hiện của thuật toán áp
dụng trên mảng A như sau:
-
Gán i = 1
-
Gán x = A[i] và pos = i – 1
-
Nếu pos >= 0 và A[pos] > x:
A[pos + 1] = A[pos]
pos = pos – 1
Quay lại bước 3
4. A[pos + 1] = x
- Nếu i < n:
Đúng thì i = i + 1 và quay lại bước 2
Sai thì dừng lại
Bây giờ thì áp dụng nó vào trong C++ thôi!
Cũng tương tự như sắp xếp chọn, thuật toán sắp xếp chèn cũng có độ phức tạp thời gian
trung bình là O(n ) do có hai vòng lặp lồng vào nhau.
Video giải thích ý tưởng thuật toán:
Thuật toán sắp xếp chèn | Khiêm Lê
Sắp xếp trộn (Merge Sort)
Sắp xếp trộn (merge sort) là một thuật toán dựa trên kỹ thuật chia để trị, ý tưởng của thuật
toán này như sau: chia đôi mảng thành hai mảng con, sắp xếp hai mảng con đó và trộn lại
Xem tiếp…
void InsertionSort ( int A[], int n)
{
int pos, x;
for ( int i = 1 ; i < n; i++)
{
x=A[i]; // lưu lại giá trị của x tránh bị ghi đè khi dịch chuyển các p
2
-
Chọn một phần tử làm chốt
-
Sắp xếp phần tử bên trái nhỏ hơn chốt
-
Sắp xếp phần tử bên phải nhỏ hơn chốt
-
Sắp xếp hai mảng con bên trái và bên phải pivot
Phần tử được chọn làm chốt rất quan trọng, nó quyết định thời gian thực thi của thuật toán.
Phần tử được chọn làm chốt tối ưu nhất là phần tử trung vị, phần tử này làm cho số phần tử
nhỏ hơn trong dãy bằng hoặc sấp xỉ số phần tử lớn hơn trong dãy. Tuy nhiên, việc tìm phần
tử này rất tốn kém, phải có thuật toán tìm riêng, từ đó làm giảm hiệu suất của thuật toán
tìm kiếm nhanh, do đó, để đơn giản, người ta thường sử dụng phần tử chính giữa làm chốt.
Trong bài viết này, mình cũng sẽ sử dụng phần tử chính giữa làm chốt, thuật toán cài đặt
trong C++ như sau:
Thuật toán sắp xếp nhanh không phải là thuật toán sắp xếp ổn định, tuy nhiên vẫn có thể
cải tiến nó thành thuật toán sắp xếp ổn định. Độ phức tạp thời gian trung bình của thuật
toán này là O(nlog(n)).
Thuật toán sắp xếp nhanh | Khiêm Lê
Một số thuật toán sắp xếp khác
Ngoài các thuật toán trên (được in đậm bên dưới), bạn có thể tìm hiểu thêm một số thuật
toán sắp xếp khác bên dưới:
Xem tiếp…
void Partition ( int A[], int left, int right)
{
// Kiểm tra xem nếu mảng có 1 phần tử thì không cần sắp xếp
if (left >= right)
return ;
