Bubble Sort

1.Ý tưởng

Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.

2.      Thuật toán:

Algorithm bubleSort(A)

            Input: Một mảng n phần tử số A

            Output: Mảng A đã được sắp xếp tăng dần.

             ForA i ← 1 to n-1 do

                        For j ← n downto i+1 do

                                    if A[j] < A[j-1] then

                                                swap(A,j-1,j)

            Return array A

3.      mã nguồn bằng C:

#include<stdio.h>   

#include<conio.h>

      

void bubble(int a[],int n)   

  {   

        int i,j,t;   

         for(i=n-2;i>=0;i--)   

         {   

            for(j=0;j<=i;j++)  

              {   

                    if(a[j]>a[j+1])   

                                    {   

                                      t=a[j];   

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

                                     a[j+1]=t;   

                           }   

                   }    

           }   

  }    

  void main()   

  {   

      int a[100],n,i;   

      clrscr();      

      scanf("%d",&n);   

        for( i=0;i<=n-1;i++)   

            { printf("\n\n Enter integer value for element no.%d : ",i+1);   

              scanf("%d",&a[i]);   

            }   

         bubble(a,n);    

       for( i=0;i<=n-1;i++)   

       printf("%3d",a[i]);   

    }