Các giải thuật sắp xếp trong lập trình (Sort)


Việc sắp xếp để cho ra một kết quả đúng không khó nhưng để có một chương trình chạy nhanh, tốn ít tài nguyên thì đó mới chính là vấn đề mà IT cần đến .

Nếu chúng ta viết một chương trình và chỉ sử dụng 1, 2 lần thì chúng ta có thể thiết kế chương trình đơn giản và có thể bỏ qua tốc độ của chương trình. Ở đây chúng ta quan tâm đến tốc độ thực thi.

Có hai kiểu sắp xếp: Sắp xếp trong và sắp xếp ngoài.
+ Sắp xếp trong: Dữ liệu được lưu trữ trong bộ nhớ và việc truy xuất ngẫu nhiên sẽ là cho chương trình thực hiện rất nhanh.

+ Sắp xếp ngoài: Chúng ta sắp xếp những tập dữ liệu lớn, được lưu trữ bên ngoài bộ nhớ trong (trong các tập tin). Ở đây tôi sẽ đề cập đến sắp xếp trong và sẽ đưa ra ví dụ về sắp xếp ngoài trong phần cuối của bài viết này.

1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Quick Sort
5. Heap Sort
6. Bin Sort

Mình sẽ lần lược đi qua từng giải thuật. Mỗi phần sẽ có giải thích và ví dụ minh họa. Hy vọng bài viết này sẽ giúp các bạn nhiều hơn trong vấn đề sắp xếp.

1. Selection Sort :
+ Chọn một phần từ lớn nhất trong n phần tử: a[0], a[1], …, a[n-1], sau đó hoán vị với phần tử a[0].
+ Chọn phần tử lớn nhất trong n – 1 phần tử từ: a[1], a[2], …, a[n-1], sau đó hoán vị với phẩn tử a[1].
+ Tổng quát: Ta thấy ở lần thứ i, ta sẽ tìm phần tử lớn nhất trong n – i phần tử từ: a[i], a[i+1],…,a[n-1], sau đó hoán vị no với a[i].
Ta có chương trình minh họa:

public class SelectionSort {
// Sort by descending
public static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int max = array[i]; // Lưu phần tử lớn nhất
int index = i; // lưu vị trí chứa phần tử lớn nhất
for (int j = i + 1; j < array.length; j++) {
if(max < array[j]){
max = array[j];
index = j;
}
}
// Nếu chỉ số đã thay đổi, ta sẽ hoán vị
if(index != i){
int temp = array[i];
array[i] = array[index];
array[index] = temp;
}
}

}
}

Ví dụ ta có một mảng giá trị sau:
Array:
10 6 3 7 12 4 4 16 8 0 12 12 12 45 2 41 65 2 1 34
—————————–

–> Sau khi sắp xếp ta được:
Array Sorted:
65 45 41 34 16 12 12 12 12 10 8 7 6 4 4 3 2 2 1 0
—————————–

2. Insertion sort:
với giải thuật này, ta xem 1 mảng với 1 phần tử a[0] như là một mảng đã sắp xếp (có thứ tự).
+ Bước 1 ta chèn phần tử a[1] vào mảng có thứ tự a[0], sao cho nó trở thành mảng có thứ tự.
+ Bước 2 ta chèn phần tử a[2] vào mảng có thứ tự a[1], a[0] sao cho nó trở thành mảng có thứ tự.
+ Tổng quát: Ở bước thứ i, ta chèn phân tử a[i] vào mảng có thứ tự a[i -1], a[i -2], …, a[0] để được mảng có thứ tự.
Ta thấy rằng a[i] sẽ được xen vào vị trí thích hợp trong mảng a[i-1],..,a[0]. Chúng ta so sánh: a[i], a[i-1] …

public static void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
int index = i;
while (index > 0 && array[index – 1] < array[index]) {
// swap
int temp = array[index];
array[index] = array[index – 1];
array[index – 1] = temp;
index–;
}
}
}

3. Bubble Sort :
Đây là giải thuật mà các bạn thường sử dụng vì tính dễ hiểu và dễ cài đặt của nó. Chúng ta sẽ cho những phần tử nhỏ sẽ nổi lên trên, nên thường gọi là giải thuật sắp xếp nổi bọt.
Giải thuật này tôi không bàn nhiều:

for(int i = 0; i< array.length; i++){
for (int j = array.length – 1; j > 0; j–) {
if(array[j] < array[j-1]){
int temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}

Ví dụ ta có một mảng giá trị sau:
Array:
10  61  3  7  12  4  4  16  8  0  12  12  12  45  2  41  65  2  1  34
—————————–

–> Sau khi sắp xếp ta được:
Array:
0  1  2  2  3  4  4  7  8  10  12  12  12  12  16  34  41  45  61  65
—————————–

4. Quick sort :
Đây là giả thuật sắp xếp nhanh, chỉ tốn O(nlogn). Cài đặt của giả thuật tương đối phức tạp. Chúng ta cần chú ý đến:

Pivot: ta gọi là chốt
Partition: Gọi là điểm phân hoạch

Đối với giải thuật này, chúng ta xem 1 mảng 1 phần tử hay mảng có tất cả phần tử giống nhau là một mảng có thứ tự. Ta sẽ chi mảng thành 2 mảng con: Trái và phải. Sắp xếp 2 mảng con, và cứ như thế cho đến khi mảng còn 1 phần tử. Nếu mảng Trái đã có thứ tự và mảng phải cũng có thứ tự thì mảng của chúng ta đã là mảng có thứ tự.

A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }

Bước 1: Tìm chốt: Chốt là phần tử lớn nhất trong 2 phần tử khác nhau đầu tiên của mảng. Nếu mảng có 1 phần tử tất cả phần tử bằng nhau sẽ không có chốt:
Chốt của mảng trên la 59 (vị trí 0).
VD:
+ 1, 1, 5, 3, 2 -> chốt sẽ là 5
+ 5, 5, 5, 3, 1, 2, 3 -> chốt là 5
+ 6 -> không có chốt
+ 7, 7, 7, 7 -> không có chốt

Bước 2: Tìm điểm phân hoạch:
+ Dùng 2 cờ: L (trái) và R (Phải)
+ L chạy từ trái qua, dừng lại khi gặp phần tử >= pivot
+ R chạy từ phải qua, dừng lại khi gặp phần tử < pivot
+ Tại điểm dùng: Nếu L < R : Chúng ta sẽ swap A[L] và A[R]
+ Dừng lại khi L > R
+ Partition sẽ là L. Đây sẽ là chỉ số đầu tiên của mảng bên phải
VD: với mảng A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }
PivotLey = 59
L = 0, R = 9:
b1. L dừng lại tại vị trí 0: vì A[L] >= pivot, R dừng lại tại vị trí 8, vì A[R] = 18 < pivot.
Swap: 18, 31, 12, 33, 27, 97, 91, 19, 59, 63
b2, tiếp tục cho đến khi L > R

Bước 3: Lặp lại như thế (Dùng đệ qui)

Xem code demo nha:
// Tìm chốt
public int findPivot(int i, int j, int[] array) {
if (array.length == 1) {
return -1;
}
int k = i + 1;
int pivot = array[i];

while ((k <= j) && (array[k] == pivot)) {
k++;
}
if (k > j) {
return -1;
}
if (array[k] > pivot) {
return k;
} else {
return i;
}
}

// Tìm partition
public int pointPartition(int i, int j, int pivotKey, int[] array) {
int partition = -1;

int L = i;
int R = j;
while (L <= R) {
while (array[L] < pivotKey)
L++;
while (array[R] >= pivotKey)
R–;
if (L < R) {
int temp = array[L];
array[L] = array[R];
array[R] = temp;
}
}
partition = L;
return partition;

}

// Sắp xếp
public void quickSort(int i, int j, int[] array) {
int pivot = findPivot(i, j, array);
if (pivot == -1)
return;
int partition = pointPartition(i, j, array[pivot], array);
quickSort(i, partition – 1, array);
quickSort(partition, j, array);
}

// Test:

quickSort(0, array.length – 1, array);

Ví dụ ta có một mảng giá trị sau:
Array:
59 31 12 33 27 97 91 19 18 63
———————-

–> Sau khi sắp xếp ta được:
Array sorted:
12 18 19 27 31 33 59 63 91 97

Khi bộ dữ liệu lớn (trên 1000) thì chúng ta cần quan tâm về tốc độ chương trình. Việc tính độ phức tạp giải thuật, chúng ta luôn tính trong trường hợp xấu nhất. Nếu dữ liệu quá ít thì chẳng cần phải quan tâm.
Quick sort sẽ luôn nhanh hơn Insertion, Selection và Bubble.

Gửi phản hồi

Please log in using one of these methods to post your comment:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s