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ó 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 $2$ 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í $2$ các bạn lẫn nhau.

Xem thêm: việc giải quyết vấn đề năng lượng ở bắc trung bộ chủ yếu dựa vào

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 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ố $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 tiến hành thay đổi vị trí $2$ 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: vai trò của không khí

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,..,n-1$ tao cần thiết $n-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à: $(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)$ .