Thứ Hai, ngày 21 tháng 5 năm 2012

Thuat Toan BubbleSort

Posted by CôĐơn Online Thứ Hai, tháng 5 21, 2012, under |

Ý tưởng:
Sắp xếp nổi bọt (tiếng Anh: 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.
Thuật toán:

Bước 1 : i = 1; // xuất phát từ đầu dãy
 Bước 2 : j = i+1; // tìm các phần tử phía sau i
 Bước 3 :
o While j £ n do
 Nếu a[j]< a[i] Þ Swap(a[i], a[j]);
 j = j+1;
 Bước 4 : i = i+1;
o Nếu i < n: Þ Bước 2
o Ngược lại Þ Kết thúc


Ví dụ:  Cho dãy : 6 , 5 , 3 , 1 , 8 , 7 , 2 , 4



Ví dụ : Cho dãy 5, 1, 12, -5, 16


Ví dụ: Cho dãy :6 , 5 , 3 , 1 , 8 , 7 , 2 , 4
................................................................

Ví dụ: Cho dãy : 3 , 1 , 2 , 4




Cài dặt:
void BubbleSort(float a[],int n)
{
 float temp;
 for(int i=1;i<n;i++)
 for(int j=n;j>i;j--)
 if(a[j]<a[j-1])
  {
   temp=a[j];
   a[j]=a[j-1];
   a[j-1]=temp;
  }
}


Xem Nhiều

Bài đăng phổ biến

Lưu trữ blog

Blog Archive