thuật toán sắp xếp nổi bọt

Đã đăng nhập thg 8 25, 2021 7:57 SA

3 phút đọc

Bạn đang xem: thuật toán sắp xếp nổi bọt

I. Làm thân quen với thuật toán

Nghe cho tới tên thường gọi thú vị của thuật toán bố trí này còn có Lúc chúng ta cũng tưởng tượng sơ sơ về cách thức thao tác làm việc của thuật toán rồi chứ. Sắp xếp nổi lớp bọt (bubble sort) là 1 trong thuật toán bố trí cơ phiên bản, tất cả chúng ta tiếp tục thao tác tài liệu cần thiết bố trí "nổi bọt" theo lần lượt theo dõi trật tự tất cả chúng ta mong ước (từ trái khoáy quý phái cần, kể từ bên dưới lên bên trên, kể từ bên trên xuống bên dưới, ...).

II. Miêu mô tả về thuật toán

1. Ý tưởng

Ý tưởng thuật toán tương tự như việc xếp sản phẩm nhập giờ thể thao. Thầy giáo thể thao ham muốn xếp chúng ta nhập lớp trở nên một sản phẩm theo dõi trật tự kể từ thấp cho tới cao, thầy đối chiếu độ cao của 22 các bạn học viên đứng cạnh nhau nhập sản phẩm, nếu như bạn phía bên phải thấp rộng lớn các bạn phía bên trái thì thay đổi vị trí 22 các bạn lẫn nhau.

Xem thêm: học phí đại học tài chính marketing

2. Chi tiết thuật toán

Xét một mảng bao gồm nn số nguyên: a1,a2,a3,...,ana_1, a_2, a_3, ..., a_n

  • Với cơ hội bố trí ko rời kể từ trái khoáy qua chuyện cần, mục tiêu của tất cả chúng ta là đem dần dần những số lớn số 1 về cuối sản phẩm (ngoài nằm trong mặt mày phải).
  • Bắt đầu từ vựng trí số 11, xét theo lần lượt từng cặp 22 thành phần, nếu như thành phần phía bên phải nhỏ rộng lớn thành phần phía bên trái, tao tiếp tục tiến hành thay đổi vị trí 22 thành phần này, còn nếu không, xét tiếp cặp tiếp sau. Với thủ tục vì vậy, thành phần nhỏ rộng lớn tiếp tục "nổi" lên, còn thành phần to hơn tiếp tục "chìm" dần dần và về phía bên phải.
  • Khi kết thúc đẩy vòng loại nhất, tao tiếp tục đem được thành phần lớn số 1 về cuối sản phẩm. Sang vòng loại nhị, tao nối tiếp chính thức ở địa điểm trước tiên vì vậy và đem được thành phần rộng lớn loại nhị về địa điểm loại nhị ở cuối sản phẩm ...
  • Hình hình ảnh minh họa thuật toán:

Xem thêm: biện pháp tu từ ẩn dụ

  • Thuật toán C++ tham lam khảo:
// hàm bố trí nổi lớp bọt (bubble sort)
void BubbleSort(int a[], int n){
    int temp; // biến đổi tạm thời temp
    for (int i = 0; i < n; i++){
	for (int j = i + 1; j < n; j++){
		if (a[j] > a[j+1]){
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
			}
		}
	}
}
  • Thuật toán Java tham lam khảo:
private static void bubbleSort(int[] unsortedArray, int length) {
        int temp, counter, index;
        
        for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array.
            for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter.
                if(unsortedArray[index] > unsortedArray[index+1]) { //Test if need a swap or not.
                    temp = unsortedArray[index]; //These three lines just swap the two elements:
                    unsortedArray[index] = unsortedArray[index+1];
                    unsortedArray[index+1] = temp;
                }
            }
        }
    }
  • Thuật toán PHP tham lam khảo:
$arr = [...];
$arr_count = count($arr);

//loop
for ($i = 0; $i < $arr_count; $i++)
{
    for ($j = 1; $j < $arr_count - $i; $j++)
    {
        if ($arr[$j-1] > $arr[$j])
        {
            $tmp = $arr[$j-1];
            $arr[$j-1] = $arr[$j];
            $arr[$j] = $tmp;
        }
    }
}


for($i=0;$i<$arr_count;$i++){
    echo $arr[$i]."<br>";
}

III. Những điều Note của thuật toán

1. Ưu điểm

  • Là thuật toán cơ phiên bản, dễ dàng nắm bắt, thích hợp cho tất cả những người chính thức học tập về bố trí.
  • Đoạn code ngắn ngủi gọn gàng, dễ dàng ghi nhớ.

2. Nhược điểm

  • Hiệu suất muộn nhất trong những thuật toán bố trí.
  • Không hiệu suất cao với những tài liệu rộng lớn.

3. Thời gian trá tính và chừng phức tạp

Với từng i=1,2,..,n1i = 1,2,..,n-1 tao cần thiết nin-i luật lệ đối chiếu. Do cơ số tối đa những thứ tự đối chiếu và thay đổi vị trí nhập giải thuật là: (n1)+(n2)+...+2+1=(n1)n2(n-1)+(n-2)+...+2+1=\frac{(n-1)n}{2} Do cơ tao có tính phúc tạp là O(n2)O(n^2).

IV. Tài liệu tham lam khảo

  • https://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_n%E1%BB%95i_b%E1%BB%8Dt
  • https://en.wikipedia.org/wiki/Bubble_sort

©️ Tác giả: Lê Ngọc Hoa kể từ Viblo

All rights reserved