Giải Thích Về Bubble Sorting - Kiểu Sắp Xếp Nổi Bọt So Sánh Trực Tiếp

Bubble Sorting (Sắp xếp nổi bọt) là một thuật toán sắp xếp đơn giản và trực quan, thích hợp cho người mới bắt đầu học lập trình. Bubble Sort có thể được sử dụng để sắp xếp các tập dữ liệu đơn giản như danh sách tên, danh sách số điểm, v.v. Nó có thể được sử dụng để thực hiện việc sắp xếp này cho các tập dữ liệu nhỏ. Bubble Sort thường được nhúng vào các thuật toán sắp xếp phức tạp hơn như Quick Sort hoặc Merge Sort để cải thiện hiệu suất cho các trường hợp dữ liệu đặc biệt.

Bubble Sorting _ Sắp xếp nổi bọt

Môn: Cấu trúc dữ liệu và thuật giải

Code: Dev C++
​

1. Khái niệm

Bubble Sorting là kiểu sắp xếp bằng cách so sánh các cặp phần tử liền kề trong mảng và hoán đổi vị trí của chúng nếu chúng không theo thứ tự mong muốn. Quá trình này được lặp lại cho đến khi toàn bộ mảng được sắp xếp hoàn chỉnh.

Ý tưởng thuật toán cũng giống như việc xếp hàng trong giờ thể dục. Thầy giáo thể dục muốn xếp các bạn trong lớp thành một hàng theo thứ tự từ thấp đến cao, thầy so sánh chiều cao của 2 bạn học sinh đứng cạnh nhau trong hàng, nếu bạn bên phải thấp hơn bạn bên trái thì đổi chỗ 2 bạn cho nhau.

2. Cách thức hoạt động:

Giả sử ta có dãy số ngẫu nhiên:

{1,3,2,40,0} tương đương vị trí được quy định [0,1,2,3,4]

​

Quy trình 1: Bắt đầu từ đầu danh sách, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu phần tử sau nhỏ hơn phần tử trước.

{1,3,2,40,0} xét [0,1] <-> {1,3} =>{1,3,2,40,0}

{1,3,2,40,0} xét [1,2] <-> {3,2} =>{1,2,3,40,0}

{1,2,3,40,0} xét [2,3] <-> {3,40} =>{1,2,3,40,0}

{1,2,3,40,0} xét [3,4] <-> {40,0} =>{1,2,3,0,40}

Quy trình 2: Lặp lại quá trình này cho đến khi không còn cặp phần tử nào cần hoán đổi nữa.

Kiểm tra dãy số đã sắp xếp đúng vị trí chưa?

{1,2,3,0,40} => Tình trạng chưa sắp xếp hết. Quay lại vòng lặp

{1,2,3,0,40} xét [0,1] <->{1,2} =>{1,2,3,0,40}

{1,2,3,0,40} xét [1,2] <->{2,3} =>{1,2,3,0,40}

{1,2,3,0,40} xét [2,3] <->{3,0} =>{1,2,0,3,40}

{1,2,3,0,40} xét [3,4] <->{3,40) =>{1,2,0,3,40}

Kiểm tra dãy số đã sắp xếp đúng vị trí chưa?

{1,2,0,3,40} => Tình trạng chưa sắp xếp hết. Quay về vòng lặp cho đến khi vị trí được sắp xếp từ nhỏ đến lớn đúng như trên {0,1,2,3,40} Thì nó mới dừng vòng lặp và xuất kết quả.

3 điều kiện để hình thành kiểu sắp xếp nổi bọt:

1. _ for(int i = 0; i<n; i++) _ Bộ đếm cho các vị trí

Ví dụ: {1,3,2,40,0} sẽ được bộ đếm rà soát từ vị trí tương ứng là [0,1,2,3,4]

n là số phần tử có trong dãy số {1,3,2,40,0}, ở đây có 5 số tương đương 5 phần tử.

​

Vì là vòng lặp ngoài, song song for(int i = 0; i<n; i++) cũng là điều kiện chính đảm bảo rằng Bubble Sort sẽ lặp lại cho đến khi tất cả các phần tử được sắp xếp đúng vị trí.

2. _ for(int j=0; j<n-i-1; j++) _

Trong điều kiện j<n-i-1, giúp tối ưu hóa thuật toán bằng cách giảm số lần so sánh không cần thiết và đảm bảo rằng các phần tử đã được sắp xếp sẽ không bị so sánh lại.

_ if(a[j]>a[j+1]) _ So sánh các giá trị trong vị trí phần tử liền kề nhau

​

_ tmp = a[j+1];

a[j+1] = a[j];

a[j] = tmp;

Hoán đổi vị trí sau khi so sánh các giá trị trong vị trí phần tử liền kề nhau _ if(a[j]>a[j+1]) _ Nếu a[0] lớn hơn a[1], vị trí đứng trước hơn vị trí đứng sau, thì sẽ cả hai sẽ đổi lại vị trí cho nhau.

​

3. for( int i=0; i<n; i++){

Cout<<" "<<a; }

- Rà soát lại từng vị trí và xuất giá trị -

Đoạn code hoàn chỉnh của Dev C++:

​

#include<iostream>
using namespace std;
void BubleSorting (int a[], int n) {
int tmp;
for (int i = 0; i<n; i++) {
for (int j=0; j<n-i-1; j++) {
if (a[j] >a[j+1] ) {
tmp = a[j+1] ;
a[j+1] = a[j] ;
a[j] = tmp;
}
}
}
}

void Show (int a[], int n) {
for (int i= 0; i<n; i++) {
cout<<" "<<a;
}
}

int main () {
int a[] = {9, 4, 7, 7, 1, 6, 87};
int n = sizeof (a) / sizeof (a[0] ) ;
BubleSorting (a, n) ;
cout<<" Bien duoc sap xep:";
Show (a, n) ;
return 0;
}