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 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 làm việ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 những 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" thứu tự theo gót trật tự tất cả chúng ta mong ước (từ trái khoáy 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, ...).

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

1. Ý tưởng

Ý tưởng thuật toán cũng tương tự 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 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 sản phẩm, nếu khách hàng phía bên phải thấp rộng lớn các bạn phía trái thì thay đổi điểm $2$ các bạn lẫn nhau.

Xem thêm: các câu đố hack nã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 hạn chế kể từ trái khoáy qua chuyện 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 sản phẩm (ngoài nằm trong mặt mũi phải).
Bắt đầu từ vựng trí số $1$ , xét thứu 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 điểm $2$ thành phần này, còn nếu không, xét tiếp cặp tiếp theo 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.
Khi kết giục vòng loại nhất, tao tiếp tục fake được thành phần lớn số 1 về cuối sản phẩm. Sang vòng loại nhị, tao kế tiếp chính thức ở địa điểm thứ nhất vì vậy và fake đượ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 họa minh họa thuật toán:

Xem thêm: điểm chuẩn đại học thăng long 2022

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ở nên 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 chú ý 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, thích hợp cho 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 lưu giữ.

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 ngoan 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 tê liệt số tối đa những đợt đối chiếu và thay đổi điểm nhập giải thuật là: $(n-1)+(n-2)+...+2+1=\frac{(n-1)n}{2}$ Do tê liệt tao có tính phúc tạp là $O(n^2)$ .