CTDL và giải thuật - Sắp xếp nổi bọt (Bubble Sort).

Nhập vào số nguyên dương n, tiếp theo là n số nguyên của dãy số a.
Hãy sắp xếp dãy số a thành dãy không giảm (số sau không bé hơn số trước) và in dãy đó ra màn hình, sau mỗi phần tử có đúng một khoảng trắng.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    5
    1 3 2 5 2

    1 2 2 3 5

    Với a = [1, 3, 2, 5, 2] thì kết quả mong muốn là:
    "1 2 2 3 5 ".
     
  • Test mẫu 2:
     
    Input Output

    4
    3 2 1 4

    1 2 3 4

    Với a = [3, 2, 1, 4] thì kết quả mong muốn là:
    "1 2 3 4 ".

Lý thuyết.

Giới thiệu sắp xếp nổi bọt (Bubble Sort).

Sắp xếp nổi bọt là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.

Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.

Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.

 

Cách Bubble Sort hoạt động:

Thuật toán cho cách sắp xếp này sẽ lần lượt đưa các số lớn nhất về ví trí cuối dãy bằng cách so sánh các cặp số kề nhau.

Ví dụ sắp xếp dãy a = [4, 1, 3, 2] thành dãy tăng dần.

 

Đầu tiên ta so sánh 2 phần tử kề nhau là a[0] và a[1].

Nếu a[0] > a[1] thì ta tráo đổi vị trí của chúng.

Tiếp tục so sánh a[1] và a[2]:

Nếu a[1] > a[2], thì ta tráo đổi vị trí giữa chúng.

Tiếp tục so sánh a[2] và a[3].

Nếu a[2] > a[3], thì ta tráo đổi vị trí giữa chúng:

Lúc này ta nhận thấy rằng phần tử lớn nhất đã được đưa đến vị trí cuối cùng của dãy a, kết thúc một bước sắp xếp.

Như vậy ta thấy rằng: mỗi bước sắp xếp ta sẽ lần lượt đưa được phần tử lớn nhất về cuối dãy.

Với bước sắp xếp tiếp theo ta chỉ cần xét các cặp phần tử a[0] và a[1]a[1] và a[2], không xét cặp a[2] và a[3] nữa, vì a[3] đã ở đúng vị trí rồi.

Sau khi đổi cho a[1] và a[2] dãy sẽ thành:

Ta thấy rằng phần tử a[2] đã được đưa về đúng vị trí. Tuy dãy đã được sắp xếp đúng yêu cầu, nhưng ta vẫn phải thực hiện bược sắp xếp tiếp theo là so sánh a[0] và a[1].

Code C++ mẫu:

void bubbleSort(int a[], int n){
	for (int i = n-1; i >= 1; i--){
		for (int j = 0; j < i; j++){
			if (a[j] > a[j+1]){
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}
} 

 

Chúng ta thấy rằng giải thuật sắp xếp nổi bọt so sánh mỗi cặp phần tử trong mảng trừ khi cả toàn bộ mảng đó đã hoàn toàn được sắp xếp theo thứ tự tăng dần. Điều này có thể làm tăng độ phức tạp, tức là tăng các thao tác so sánh và tráo đổi không cần thiết nếu như mảng này không cần sự tráo đổi nào nữa khi tất cả các phần tử đã được sắp xếp theo thứ tự tăng dần rồi.

Để tránh việc này xảy ra, chúng ta có thể sử dụng một biến swapped chẳng hạn để giúp chúng ta biết có cần thực hiện thao tác tráo đổi thứ tự hay không. Nếu không cần thiết thì thoát khỏi vòng lặp.

Code C++ mẫu:

void bubbleSort(int a[], int n){
	for (int i = n-1; i >= 1; i--){
		bool swapped= true;
		for (int j = 0; j < i; j++){
			if (a[j] > a[j+1]){
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				swapped = false;
			}
		}
		if (swapped){
			break;
		}
	}
}

 

Hướng dẫn bài tập.

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

void printArray(int a[], int n){
	for (int i = 0; i < n; i++){
		cout << a[i] << " ";
	}
}
void bubbleSort(int a[], int n){
	for (int i = n-1; i >= 1; i--){
		bool swapped= true;
		for (int j = 0; j < i; j++){
			if (a[j] > a[j+1]){
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				swapped = false;
			}
		}
		if (swapped){
			break;
		}
	}
}
int a[100001];
int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	bubbleSort(a, n);
	printArray(a, n);
	
	return 0;
}