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

1
4848

Để 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Đổ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 aj-1 và aj tức là a6 và a5 . Do 6<9 nên không đổi chỗ và j=j-1;

Xét tiếp a5 và a5 . 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 a4 và a3 . 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 a3 và a2 . Do 0<6 nên không đổi chỗ và Sau đó  giảm j=j-1;

Xét tiếp a2 và a1 . 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 a1 và a0 . 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 a6 và a5 . 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 a5 và a4 . 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 a6 và a5 . 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

1 COMMENT

  1. 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 a[i + 1])
    {
    b = a[i];
    a[i] = a[i + 1];
    a[i + 1] = b;
    x = true;
    }
    }
    }
    }

    chỗ x=true hình như sai phải không bạn.
    x=1 mới đúng chứ

This site uses Akismet to reduce spam. Learn how your comment data is processed.