Các thuật toán sắp xếp - P1
Một số phương pháp sắp xếp đơn giản
1.Sắp xếp kiểu lựa chọn (Selection sort)
Nguyên tắc cơ bản của phương pháp sắp xêp này là xét dãy khóa n phần tử K0, K1, …, Kn-1. Ở lần duyệt thứ j (j = 1, 2, 3, ..., n -1) ta sẽ chọn trong dãy khóa Kj-1, Kj, Kj+1, ..., Kn-1 khóa nhỏ nhất và đổi chỗ cho Kj-1 .
Như vậy sau j lượt, j khóa nhỏ hơn đã nằm ở vị trí thứ nhất, thứ hai, ..., thứ j theo thứ tự sắp xếp.
Source: C++
Source: C++
Như vậy sau j lượt, j khóa nhỏ hơn đã nằm ở vị trí thứ nhất, thứ hai, ..., thứ j theo thứ tự sắp xếp.
Giải thuật:
/* Mảng K có n phần tử, giải thuật sắp xếp các phần tử của K theo thứ tự tăng dần */
SELECT_SORT(K, n) {
for(i = 0; i < n; i++) {
min = i;
for(j = i + 1; j < n; j++) {
if(K[j] < K[min];
min = j;
}
if(i < min) { //Nếu khóa nhỏ nhất khác K[i] thì đổi chỗ K[i] và K[min]
temp = K[i];
K[i] = K[min];
K[min] = temp;
}
}
}
SELECT_SORT(K, n) {
for(i = 0; i < n; i++) {
min = i;
for(j = i + 1; j < n; j++) {
if(K[j] < K[min];
min = j;
}
if(i < min) { //Nếu khóa nhỏ nhất khác K[i] thì đổi chỗ K[i] và K[min]
temp = K[i];
K[i] = K[min];
K[min] = temp;
}
}
}
Source: C++
2.Sắp xếp kiểu thêm dần (Insertion sort)
Nguyên tắc sắp xếp ở đây là giả sử có i - 1 khóa đã được sắp xếp. Nếu tiếp tục chèn thêm khóa i vào ta sẽ so sánh khóa i với lần lượt các khóa thứ (i -1), thứ (i - 2), ....để tìm ra vị trí thích hợp và chèn khóa i vào đó.
Xét trên một dãy khóa K n phần tử K0, K1, …, Kn-1. Ban đầu K0 Coi như dãy chỉ có một phần tử đã được sắp xếp. Xét K1, so sánh nó với K0 để xác định vị trí chèn ta sẽ có dãy gồm hai phần tử đã được sắp xếp. Tiếp tục chèn các khóa K2, K3,...,Kn-1. ta được dãy đã được sắp xếp hoàn toàn.
Giải thuật:
// Mảng K có n phần tử, giải thuật sắp xếp các phần tử của K theo thứ tự tăng dần
/* Ta sẽ thực hiện việc sắp xếp ngay trên mảng K mà không chuyển sang một mảng mới. Do đó sẽ không có sẵn chỗ trống vì khóa đang xét và chưa xét đã chiếm hết vị trí đằng sau.
Do đó ta sẽ sử dụng một biện phụ để lưu khóa đang xét và đẩy lại về vị trí của nó khi các khóa cần thiết lùi đúng về vị trí. */
INSERT_SORT(K, n) {
for(i = 1; i < n; i++) {
temp = K[i];
j = i - 1;
while(j >= 0 && K[j] > temp) {
K[j + 1] = K[j];
j--;
}
K[j+1] = temp;
}
}
/* Ta sẽ thực hiện việc sắp xếp ngay trên mảng K mà không chuyển sang một mảng mới. Do đó sẽ không có sẵn chỗ trống vì khóa đang xét và chưa xét đã chiếm hết vị trí đằng sau.
Do đó ta sẽ sử dụng một biện phụ để lưu khóa đang xét và đẩy lại về vị trí của nó khi các khóa cần thiết lùi đúng về vị trí. */
INSERT_SORT(K, n) {
for(i = 1; i < n; i++) {
temp = K[i];
j = i - 1;
while(j >= 0 && K[j] > temp) {
K[j + 1] = K[j];
j--;
}
K[j+1] = temp;
}
}
Source: C++
3.Sắp xếp kiểu đổi chỗ (Exchange sort) - Sắp xếp nổi bọt (Buble sort)
Dãy khóa sẽ được duyệt từ đáy lên đỉnh. Nếu gặp cặp khóa ngược thứ tự thì đổi chỗ chúng, như vậy trong lươt duyệt đầu khóa có giá trị nhỏ nhất sẽ chuyển tới vị trí đầu tiên. Trong lần duyệt thứ hai khóa có giá trị nhỏ thứ hai sẽ chuyển tới vị trí thứ hai....Nếu đặt dãy khóa thẳng đứng thì có thể hình dung các khóa có giá trị nhỏ sẽ dần đân "nổi" lên đỉnh dãy giống như các bọt nước.
Giải thuật:
// Mảng K có n phần tử, giải thuật sắp xếp các phần tử của K theo thứ tự tăng dần
BUBLE_SORT(K, n) {
for(i = 0; i < n; i++) {
for(j = n - 1; j > i; j--) {
if(K[j] < K[j-i]) {
temp = K[j];
K[j] = K[j - 1];
K[j - 1] = temp;
}
}
}
}
BUBLE_SORT(K, n) {
for(i = 0; i < n; i++) {
for(j = n - 1; j > i; j--) {
if(K[j] < K[j-i]) {
temp = K[j];
K[j] = K[j - 1];
K[j - 1] = temp;
}
}
}
}
Source: C++
Đánh giá giải thuật:
Đối với phương pháp sắp xếp kiểu lựa chọn (SELECT_SORT). Ở lần duyệt thứ i = 1, 2, 3, ..., n - 1 để tìm ra khóa nhỏ nhất bao giờ cũng cần (n - i) phép so sánh mà không phụ thuộc vào dữ liệu ban đầu của khóa. Suy ra số phép toán là:
Độ phức tạp của thuật toán là O(n^2).
Đối với phương pháp thêm dần và nổi bọt nổi giả sử các giá trị khóa xuất hiện đồng khả năng và với n lớn thì độ phức tập của thuật toán cũng cho kết quả O(n^2).
Ưu điểm của các thuật toán này là tính đơn giản và dẽ cài đặt nhưng nhược điểm là nếu xử lý bài toàn có dữ liệu lớn thì chi phí rất cao vì độ phức tạp tính theo hệ số mũ.
Ưu điểm của các thuật toán này là tính đơn giản và dẽ cài đặt nhưng nhược điểm là nếu xử lý bài toàn có dữ liệu lớn thì chi phí rất cao vì độ phức tạp tính theo hệ số mũ.
Nhận xét
Đăng nhận xét