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

Đã đă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ó Khi chúng ta cũng tưởng tượng sơ sơ về cách thức thao tá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 ước muốn (từ ngược quý phái nê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 miêu tả về thuật toán

1. Ý tưởng

Ý tưởng thuật toán cũng như việc xếp mặt hàng nhập giờ thể dục thể thao. Thầy giáo thể dục thể thao ham muốn xếp chúng ta nhập lớp trở thành một mặt hàng theo dõi trật tự kể từ thấp cho tới cao, thầy đối chiếu độ cao của $2$ các bạn học viên đứng cạnh nhau nhập mặt hàng, nếu như khách hàng 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 khu vực $2$ các bạn lẫn nhau.

Xem thêm: sơ đồ tư duy bài người lái đò sông đà

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

Xét một mảng bao gồm $n$ số nguyên: $a_1, a_2, a_3, ..., a_n$

Với cơ hội bố trí ko tách kể từ ngược qua quýt nên, mục tiêu của tất cả chúng ta là fake dần dần những số lớn số 1 về cuối mặt hàng (ngoài nằm trong mặt mũi phải).
Bắt đầu từ vựng trí số $1$ , xét theo lần lượt từng cặp $2$ 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 triển khai thay đổi khu vực $2$ thành phần này, còn nếu như không, xét tiếp cặp tiếp sau. Với phương thức như thế, 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 cổ động vòng loại nhất, tao tiếp tục fake được thành phần lớn số 1 về cuối mặt hàng. Sang vòng loại nhì, tao kế tiếp chính thức ở địa điểm trước tiên như thế và fake được thành phần rộng lớn loại nhì về địa điểm loại nhì ở cuối mặt hàng ...
Hình hình ảnh minh họa thuật toán:

Xem thêm: g là gì trong vật lý

Thuật toán C++ tham ô khảo:

// hàm bố trí nổi lớp bọt (bubble sort)
void BubbleSort(int a[], int n){
    int temp; // đổi thay 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 ô 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 ô 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ễ 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 cụt gọn gàng, dễ dàng ghi nhớ.

2. Nhược điểm

Hiệu suất muộn nhất trong số 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 lừa lọc tính và chừng phức tạp

Với từng $i = 1,2,..,n-1$ tao cần thiết $n-i$ phép tắc đối chiếu. Do cơ số tối đa những chuyến đối chiếu và thay đổi khu vực nhập giải thuật là: $(n-1)+(n-2)+...+2+1=\frac{(n-1)n}{2}$ Do cơ tao có tính phúc tạp là $O(n^2)$ .