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

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ông thức thao tác của thuật toán rồi chứ. Sắp xếp nổi váng bọt (bubble sort) là 1 trong thuật toán bố trí cơ bạn dạng, 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 thứ tự theo gót trật tự tất cả chúng ta mong ước (từ trái ngược lịch sự 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, ...).

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

II. Miêu mô 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ở nên một mặt hàng theo gót 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ư bạn phía bên phải thấp rộng lớn các bạn phía trái thì thay đổi khu vực $2$ các bạn lẫn nhau.

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ừ trái ngược qua loa nên, mục tiêu của tất cả chúng ta là trả 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ày phải).
Bắt đầu từ vựng trí số $1$ , xét theo thứ 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 trái, tao tiếp tục triển khai thay đổi khu vực $2$ thành phần này, nếu như không, xét tiếp cặp tiếp sau. Với cách thứ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.
Xem thêm: chu kì tế bào là gì
Khi kết thúc đẩy vòng loại nhất, tao tiếp tục trả đượ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 vì vậy và trả đượ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 họa minh họa thuật toán:
Xem thêm: soạn bài số phận con người
Thuật toán C++ tham lam khảo:

// hàm bố trí nổi váng bọt (bubble sort)
void BubbleSort(int a[], int n){
    int temp; // trở thành 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 cảnh báo của thuật toán

1. Ưu điểm

Là thuật toán cơ bạn dạng, dễ nắm bắt, tương thích 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ủn 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 gian tham 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 bại liệt số tối đa những phiê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 bại liệt tao có tính phúc tạp là $O(n^2)$ .