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

Đã đăng vô 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 quen thuộc 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 váng bọt (bubble sort) là một 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 lần lượt theo gót trật tự tất cả chúng ta ước muốn (từ trái 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 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 vô giờ thể thao. Thầy giáo thể thao ham muốn xếp chúng ta vô lớp trở thành 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$ chúng ta học viên đứng cạnh nhau vô mặt hàng, nếu như bạn ở bên phải thấp rộng lớn chúng ta phía bên trái thì thay đổi vị trí $2$ chúng ta lẫn nhau.

Xem thêm: muốn tính chu vi hình bình hành

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 quýt nê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 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 lần lượt từng cặp $2$ thành phần, nếu như thành phần ở 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í $2$ thành phần này, nếu như 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ề ở bên phải.
Khi kết đôn đốc vòng loại nhất, tao tiếp tục đem được thành phần lớn số 1 về cuối mặt hàng. 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 mặt hàng ...
Hình hình ảnh minh họa thuật toán:

Xem thêm: trong quá trình dịch mã

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

// hàm bố trí nổi váng bọt (bubble sort)
void BubbleSort(int a[], int n){
    int temp; // biến hóa 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 chú ý của thuật toán

1. Ưu điểm

Là thuật toán cơ bạn dạng, dễ dàng nắm bắt, tương thích cho 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 lưu giữ.

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 dối 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$ luật lệ đối chiếu. Do cơ số tối đa những lượt đối chiếu và thay đổi vị trí vô 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)$ .