Home > Algorithm > Algorithm Basic – Thuật toán sắp xếp nổi bọt – Bubble Sort

Algorithm Basic – Thuật toán sắp xếp nổi bọt – Bubble Sort

1. Giải thuật :

Tưởng tượng rằng các mẩu tin được lưu trong một mảng dọc, qua quá trình sắp xếp, mẩu tin nào có khóa “nhẹ” sẽ được “nổi” lên trên. Tư tưởng của thuật toán là có 2 vòng lặp lồng nhau. Tại mỗi vòng lặp con sẽ duyệt từ dưới lên trên, tại mỗi bước sẽ so sánh 2 phần tử kế cận nhau, nếu phần tử nào “nhẹ hợn” thì cho nó “nổi lên” bằng cách đổi chỗ 2 phần tử này cho nhau.

Cụ thể :

  • Bước 1: Xét các phần tử từ a[n] đến a[2], với mỗi phần tử a[j], so sánh khóa của nó với khóa của phần tử a[j-1] đứng ngay trước nó. Nếu khóa của a[j] nhỏ hơn khóa của a[j-1] thì hoán đổi a[j] và a[j-1] cho nhau.
  • Bước 2: Xét các phần tử từ a[n] đến a[3], và làm tương tự như trên.
  • Sau n-1 bước thì kết thúc.

So sánh với phương pháp sắp xếp chọn :

  • Với thuật toán sắp xếp chọn, ta thấy rằng sau mỗi vòng lặp lựa chọn được một phần tử nhỏ nhất đưa về đầu dãy, các phần tử còn lại hầu như không ảnh hưởng, kết quả của vòng lặp trước không ảnh hưởng đến vòng lặp sau.
  • Đặc điểm của thuật toán sắp xếp nổi bọt tối ưu hơn so với sắp xếp chọn là tại mỗi vòng lặp con do có quá trình tráo đổi phần tử nhỏ về đầu dãy nên các phần tử lớn dần được đưa về cuối dãy, các phần tử nhỏ hơn dần được đưa về đầu dãy.
  • Đối với phương pháp sắp xếp chọn có tối đa n-1 lần tráo đổi, còn sắp xếp nổi bọt thì tối đa n*(n-1) lần tráo đổi ( trường hợp danh sách sắp xếp theo thứ tự ngược lại). Nhưng ưu điểm của phương pháp nổi bọt là sau mỗi bước thì danh sách dần ổn định hơn nên có thể không cần chạy hết vòng lặp thì danh sách đã được sắp theo thứ tự.

2. Cài đặt :

public static int[] BubbleSort(int[] array)
 {
     int temp;
     for (int i = 0; i < array.Length-1; i++)
     {
         for (int j = array.Length-1; j >i ; j--)
         {
             if (array[j]<array[j-1])
             {
                 temp = array[j];
                 array[j] = array[j - 1];
                 array[j - 1] = temp;
             }
         }
      }
      return array;
 }

3. Đánh giá độ phức tạp thuật toán :

  • Tốt nhất – O(n)
  • Trung bình – O(n^2)
  • Xấu nhất – O(n^2)
  • Tính ổn định – ổn định
Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: