Một số thuật toán sắp xếp đơn giản (phần 1)

1. Một số thuật toán sắp xếp đơn giản (phần 2)

Chắc hẳn ngồi trên ghế giảng đường đại học thì ai cũng sẽ được làm quen với thuật toán. Nghe thì thật là trừu tượng và mơ hồ, nhưng để tối ưu hóa những bài toán đặt ra thì bắt buộc các bạn phải học đến nó. Mình xin chia sẻ 1 chút lí thuyết mà mình học được về các thuật toán sắp xếp đơn giản, mong là có thể giúp các bạn áp dụng vào bài toán thực tế của mình!

Ý tưởng

Đây có lẽ là loại sắp xếp quen thuộc nhất với mọi người. Ý tưởng của thuật toán sắp xếp nổi bọt như sau: cho chỉ số i chạy từ 0, 1, ..., n-1, nếu hai phần tử kề nhau không đúng trật tự, có nghĩa là A[i].key > A[i+1].key thì ta tráo đổi hai phần tử A[i] và A[i+1]. Cứ tiếp tục làm như vậy thì ta sẽ đẩy dữ liệu có khóa lớn nhất lên vị trí sau cùng là A[n-1].

Ví dụ

Giả sử ta có mảng số nguyên A[0..4] = (7, 2, 8, 4, 6). Kết quả thực hiện việc tráo đổi sẽ được thực hiện trong bảng sau:

Lặp lại quá trình trên với mảng A[0, ..., n-2] để đẩy phần tử lớn nhất lên vị trí A[n-2], khi đó ta có A[n-2].key <= A[n-1].key. Tiếp tục lặp như vậy với các đoạn đầu A[0..i], với i = n-3, ...., 1, ta sẽ thu được mảng được sắp.

Thuật toán

1void BubbleSort (int A[], int n) {
2	for (int i = n-1; i > 0; i--) {
3		for (int k = 0; k < i; k++) {
4			if (A[k].key > A[k+1].key) {
5				Swap(A[k], A[k+1]); //doi vi tri A[k] và A[k+1]
6			}
7		}
8	}
9}

Ta sẽ dễ thấy thời gian chạy của thuật toán này là O(n2) Tuy nhiên giờ ta cũng có thể cải tiến thuật toán sắp xếp nổi bọt bằng cách thêm 1 biến booblean là check, biến này trả về true nếu A[0..i] đã được sắp xếp và ngược lại. Nếu check nhận giá trị true thì vòng for đầu tiên sẽ dừng lại. Mục đích là ở lện lặp đầu tiên, nếu đến chỉ số i nào đó mà đoạn đầu A[0..i] đã được sắp xếp thì ta có thể dừng không lặp nữa, giảm thiểu được thời gian chạy.

void BubbleSort (int A[], int n) {
	for (int i = n-1; i > 0; i--) {
		bool check = true;
		for (int k = 0; k < i; k++) {
			if (A[k].key > A[k+1].key) {
				Swap(A[k], A[k+1]);
				check = false;
			}
		}
		if (check) {
			break;
		}
	}
}

Ý tưởng

Ý tưởng của thuật toán này cũng đơn giản không kém sắp xếp nổi bọt: Giả sử ta chọn được thành phần có khóa nhỏ nhất trên mảng là A[k]. Tráo đổi A[0] với A[k], vậy thì lúc này ta sẽ nhận được A[0] là phần tử có khóa nhỏ nhất. Giả sử đến bước thứ i ta đã có A[0].key <= A[1].key <= ... <= A[i-1].key. Bây giờ ta cần tìm thành phần có khóa nhỏ nhất trong các phần tử từ A[i] đến A[n-1]. Giả sử thành phần đó là A[k] sao cho i <= k <= n-1. Ta lại tráo đổi A[i] với A[k], ta có A[0].key <= A[1].key <= ... <= A[i-1].key <= A[i].key. Lặp lại cho tới i = n-1, ta có mảng A được sắp xếp

Ví dụ

Ta lại xét mảng A ở ví dụ trên A[0..4] = [7, 2, 8, 4, 6]. Kết quả được thể hiện trong bảng sau: Chọn phần tử có khóa nhỏ nhất là A[0]

Ok vậy là bài toán có thể giải quyết nhanh gọn