Sắp xếp bong bóng - Short

Question 1

> > Vì vậy, ý tưởng cơ bản đằng sau sắp xếp bong bóng là thế này.
0:13
Chúng tôi thường muốn di chuyển các phần tử có giá trị cao hơn nói chung sang bên phải,
0:17
và các phần tử có giá trị thấp hơn thường ở bên trái, như chúng ta mong đợi.

Answer 1

Sắp xếp lựa chọn là sắp xếp từ trái sang phải , tương đương với từ nhỏ đến lớn
Sắp xếp bong bóng là sắp xếp từ phải sang trái, tương đương với từ lớn đến nhỏ

Question 2

Hãy hình dung nó trông như thế nào bằng cách sử dụng mảng của chúng ta
1:07
mà chúng tôi đã sử dụng để kiểm tra các thuật toán này.

Question 3

> > Bây giờ bạn đang nhìn vào màn hình và có thể nói,
3:47
như tôi có thể, rằng mảng được sắp xếp ngay bây giờ.
3:50
Nhưng chúng ta chưa thể chứng minh điều đó.
3:51
Chúng tôi không đảm bảo rằng nó đã được sắp xếp.
3:54
Nhưng đây là lúc bộ đếm hoán đổi sẽ phát huy tác dụng.

Question 4

> > Nếu chúng ta không phải chuyển đổi bất kỳ phần tử nào, thì chúng
4:25
phải theo thứ tự, nhờ quá trình này.

Question 5

Trong sắp xếp bong bóng, ý tưởng của thuật toán là di chuyển các phần tử có giá trị cao hơn thường về bên phải và các phần tử có giá trị thấp hơn thường về bên trái.

Mã giả:
Set swap counter to a non-zero value
Repeat until the swap counter is 0:
Reset swap counter to 0
Look at each adjacent pair
If two adjacent elements are not in order, swap them and add one to the swap counter

Answer 5

Mã giả:
Đặt bộ đếm trao đổi thành giá trị khác không
Lặp lại cho đến khi bộ đếm hoán đổi bằng 0:
Đặt lại bộ đếm trao đổi thành 0
Nhìn vào từng cặp liền kề
Nếu hai phần tử liền kề không theo thứ tự, hãy hoán đổi chúng và thêm một phần tử vào bộ đếm hoán đổi

Question 6

Trường hợp xấu nhất: Mảng có thứ tự ngược lại; chúng ta phải “bong bóng” từng phần tử trong số n phần tử trên toàn bộ mảng và vì chúng ta chỉ có thể tạo bong bóng hoàn toàn một phần tử vào vị trí mỗi lần, nên chúng ta phải thực hiện việc này n lần.
Trường hợp tốt nhất: Mảng đã được sắp xếp hoàn hảo và chúng tôi không thực hiện hoán đổi trong lần vượt qua đầu tiên.

Question 7

Trong sắp xếp bong bóng họ xem xét thời gian chạy dựa trên phép so sánh hai phần tử liền kề

Question 8

trong trường hợp tốt nhất, điều này thực sự tốt hơn so với lựa chọn
5:45
sắp xếp– đó là omega của n.

Question 9

O(n^2)
Ω(n)