Thuật toán sắp xếp nổi bọt (BubbleSort)

Để tiếp tục chủ để các  thuật toán sắp xếp của lập trình C/C++ hôm nay chúng ta sẽ tìm hiểu thêm một thuật toán nữa sau hai thuật toán đã giới thiệu đến các bạn là  Sắp xếp chọn trực tiếp và Đổi chỗ trực tiếp. Thuật toán này sẽ giải quyết vấn đề tài nguyên khi số lần so sánh của bài toán được giảm rất nhiều cũng như số lần gán. Chúng ta hãy bắt đầu nhé.

Ý tưởng

Ý chính của thuật toán là xuất phát từ cuối (hoặc đầu) dãy, đổi chổ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đó về vị trí đúng đầu (cuối) dãy hiện hành, sau đó sẽ không xét đến nó ở vị trí tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

Giải thuật

Bước 1: i=0; //Phần tử đầu tiên

Bước 2:Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ a[n] đến a[i]. với biến gán j=n-i. và lặp lại khi j>i.

Bước 3: i=i+1

Bước 4: 

Nếu i < n, quay lại Bước 2.

Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.

Ví dụ

Cho dãy A gồm các phần tử: 4 5 0 11 8 6 9. Hãy dùng giải thuật sắp xếp nổi bọt để sắp xếp lại dãy đã cho.

Đầu tiên i=0 và j= 6.

Xét a_j-1 và a_j tức là a₆ và a₅ . Do 6<9 nên không đổi chỗ và j=j-1;

Xét tiếp a₅ và a₅ . Do 8>6 nên đổi chỗ 6 và 8 được dãy 4 5 0 11 6 8 9. Sau đó j=j-1;

Xét tiếp a₄ và a₃ . Do 11>6 nên đổi chỗ 11 và 6 được dãy 4 5 0 6 11 8 9. Sau đó tiếp tục giảm j=j-1;

Xét tiếp a₃ và a₂ . Do 0<6 nên không đổi chỗ và Sau đó  giảm j=j-1;

Xét tiếp a₂ và a₁ . Do 5>0 nên đổi chỗ 5 và 0 được dãy 4 0 5 6 11 8 9. Sau đó tiếp tục giảm j=j-1;

Xét tiếp a₁ và a₀ . Do 4>0 nên đổi chỗ 4 và 0 được dãy 0 4 5 6 11 8 9. Sau đó tiếp tục giảm j=j-1;

Do j=i=0 nên tăng biến i lên i=i+1=1;

j=6.

Xét a₆ và a₅ . Do 9>8 nên không đổi chỗ và giữ nguyên dãy 0 4 5 6 11 8 9. Sau đó giảm j=j-1;

Xét a₅ và a₄ . Do 11>8 nên đổi chỗ 11 và 8 được dãy 0 4 5 6 8 11 9. Sau đó tiếp tục giảm j=j-1;

Tương tự như trên, giảm j dần về 1. Dãy vẫn giữ nguyên như vậy. Sau đó tăng i lên ;

j=6.

Xét a₆ và a₅ . Do 11>9 nên đổi chỗ 11 và 9 được dãy  0 4 5 6  8 9 11. Sau đó giảm j=j-1;

Do lúc này i>n nên dừng giải thuật và nhận dãy 0 4 5 6 8 9 11.

Code C/C++

Hàm sắp xếp theo giải thuật 2 vòng lập

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

Hàm swap

void swap(int &a, int &b)
{
	int c = a;
	a = b;
	b = c;
}

Hàm main

void main()
{
	int A[100]; int N;
	NhapMang(A, N);
	XuatMang(A, N);
	Sapxep(A, N);
	printf("\nMang sau khi sap xep la: ");
	XuatMang(A, N);
	getch();
}

 Trước khi chạy hàm main các bạn phải có hàm nhập và xuất mảng 1 chiều. Các bạn có thể xem tại đây.

Kết quà:

Cho biet so phan tu cua mang: 7

Gia tri phan tu a[0]=4

Gia tri phan tu a[1]=5

Gia tri phan tu a[2]=0

Gia tri phan tu a[3]=11

Gia tri phan tu a[4]=8

Gia tri phan tu a[5]=6

Gia tri phan tu a[6]=9

   4   5   0  11   8   6   9

Mang sau khi sap xep la:    0   4   5   6   8   9  11

Ngoài ra các bạn có thể giảm bớt vòng lập bằng cách dùng hàm sau :

void Sapxep1for(int a[], int n)
{
	int x = 1;
	int j = 0;
	int b;
	while (x == 1)
	{
		x = 0;
		j++;
		for (int i = 0; i < n - j; i++)
		{
			if (a[i] > a[i + 1])
			{
				b = a[i];
				a[i] = a[i + 1];
				a[i + 1] = b;
				x = true;
			}
		}
	}
}

Trên đây là trình bày về thuật toán sắp xếp nổi bọt hay còn gọi là Bubble Sort. Hẹn gặp lại các bạn ở các thuật toán sắp xếp tiếp theo. Chúc các bạn thành công