[Powered by Google Translate] [BUBBLE SORT]
[JACKSON STEINKAMP ĐẠI HỌC HARVARD]
[Đây là CS50. CS50TV]
Sắp xếp bong bóng là một ví dụ về một thuật toán phân loại -
có nghĩa là, một thủ tục để sắp xếp một tập hợp các yếu tố trong
tăng dần hoặc giảm dần.
Ví dụ, nếu bạn muốn sắp xếp một mảng bao gồm các con số
[3, 5, 2, 9], thực hiện đúng loại Bubble sẽ trả lại
sắp xếp mảng [2, 3, 5, 9] theo thứ tự tăng dần.
Bây giờ, tôi sẽ giải thích trong giả thuật toán làm việc như thế nào.
>> Hãy nói rằng chúng tôi đang phân loại một danh sách gồm 5 số nguyên - 3, 2, 9, 6, và 5.
Thuật toán bắt đầu bằng cách nhìn vào hai yếu tố đầu tiên, 3 và 2,
và kiểm tra nếu họ đang ra khỏi thứ tự tương đối với nhau.
Họ là 3 là lớn hơn 2.
Để có thứ tự tăng dần, họ sẽ có cách khác xung quanh.
Vì vậy, chúng tôi trao đổi chúng.
Bây giờ danh sách trông như thế này: [2, 3, 9, 6, 5].
>> Tiếp theo, chúng ta nhìn vào các yếu tố thứ hai và thứ ba, 3 và 9.
Họ đang ở trong thứ tự chính xác tương đối với nhau.
Đó là, 3 là ít hơn 9 do đó, các thuật toán không trao đổi chúng.
Tiếp theo, chúng ta nhìn vào 9 và 6. Họ đang ra khỏi trật tự.
>> Vì vậy, chúng ta cần trao đổi chúng vì 9 là lớn hơn 6.
Cuối cùng, chúng ta nhìn vào hai số nguyên, 9 và 5.
Họ đang ra khỏi trật tự, vì vậy họ phải được trao đổi.
Sau khi vượt qua hoàn chỉnh đầu tiên thông qua danh sách,
nó trông như thế này: [2, 3, 6, 5, 9].
Không phải là xấu. Nó gần như được sắp xếp.
Nhưng chúng ta cần phải chạy qua danh sách một lần nữa để có được nó hoàn toàn được sắp xếp.
Hai là ít hơn 3, nên chúng tôi không trao đổi chúng.
>> Ba là ít hơn 6, vì vậy chúng tôi không trao đổi chúng.
Sáu là lớn hơn 5. Chúng tôi đổi chỗ.
Sáu là ít hơn 9. Chúng tôi không trao đổi.
Sau khi vượt qua thứ hai thông qua, nó trông như thế này: [2, 3, 5, 6, 9]. Hoàn hảo.
Bây giờ, hãy viết nó trong giả.
Về cơ bản, cho mỗi phần tử trong danh sách, chúng ta cần phải nhìn vào nó
và yếu tố trực tiếp bên phải của nó.
Nếu họ ra khỏi trật tự tương đối với nhau - đó là, nếu các yếu tố trên bên trái
là lớn hơn so với cái bên phải - chúng ta nên trao đổi hai yếu tố.
>> Chúng tôi làm điều này cho tất cả các phần tử của danh sách, và chúng tôi đã thực hiện một đi qua.
Bây giờ chúng ta chỉ cần có để làm pass-through đủ thời gian để đảm bảo danh sách
đầy đủ, đúng cách sắp xếp.
Nhưng bao nhiêu lần chúng ta phải vượt qua thông qua danh sách để
đảm bảo rằng chúng tôi đang thực hiện?
Vâng, trường hợp xấu nhất là nếu chúng ta có một danh sách hoàn toàn ngược.
Sau đó, nó có một số vượt qua-throughs bằng số
các yếu tố n-1.
Nếu điều này không có ý nghĩa trực giác, suy nghĩ của một trường hợp đơn giản - danh sách [2, 1].
>> Điều này sẽ mất một pass-thông qua để sắp xếp một cách chính xác.
[3, 2, 1] - Trường hợp xấu nhất là với 3 yếu tố được sắp xếp ngược,
nó sẽ mất 2 lặp đi lặp lại để sắp xếp.
Sau một lặp đi lặp lại, đó là [2, 1, 3].
Thứ hai sản lượng mảng được sắp xếp [1, 2, 3].
Vì vậy, bạn biết bạn không bao giờ phải đi qua mảng, nói chung,
hơn n-1 lần, trong đó n là số phần tử trong mảng.
Nó được gọi là bong bóng sắp xếp bởi vì các yếu tố lớn nhất có xu hướng 'bong bóng'
bên phải khá nhanh chóng.
Trong thực tế, thuật toán này có hành vi rất thú vị.
>> Sau khi lặp đi lặp lại m thông qua toàn bộ mảng,
được đảm bảo các yếu tố ngoài cùng bên phải m
được sắp xếp vào vị trí chính xác của họ.
Nếu bạn muốn xem này cho chính mình,
chúng ta có thể thử nó trên một danh sách hoàn toàn ngược [9, 6, 5, 3, 2].
Sau khi đi qua toàn bộ danh sách,
[Âm thanh của văn bản]
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]
các yếu tố ngoài cùng bên phải 9 là ở vị trí thích hợp của nó.
Sau khi pass-through, 6 sẽ có bọt khí-up '.
2 vị trí ngoài cùng bên phải.
Hai yếu tố trên quyền - 6 và 9 - sẽ được địa điểm chính xác của họ
sau khi hai pass-throughs.
>> Vì vậy, làm thế nào chúng ta có thể sử dụng điều này để tối ưu hóa các thuật toán?
Vâng, sau khi một lặp đi lặp lại thông qua các mảng
chúng tôi không thực sự cần phải kiểm tra các yếu tố ngoài cùng bên phải
bởi vì chúng ta biết nó được sắp xếp.
Sau hai lặp đi lặp lại, chúng ta biết chắc chắn rằng hai yếu tố cuối cùng bên phải được đưa ra.
Vì vậy, nói chung, sau khi lặp đi lặp lại k qua mảng đầy đủ,
kiểm tra các yếu tố k cuối cùng là không cần thiết vì chúng ta biết
họ đang ở trong vị trí chính xác rồi.
>> Vì vậy, nếu bạn đang phân loại một mảng n phần tử,
phiên đầu tiên - bạn sẽ phải sắp xếp tất cả các yếu tố đầu tiên n-0.
Trên lặp thứ hai, bạn sẽ phải xem xét tất cả các yếu tố, nhưng cuối cùng -
n-1 đầu tiên.
Một tối ưu hóa có thể là để kiểm tra xem danh sách đã được sắp xếp
sau mỗi lần lặp.
Nếu nó đã được sắp xếp, chúng ta không cần phải thực hiện lặp đi lặp lại nữa
thông qua danh sách.
Làm thế nào chúng ta có thể làm điều này?
Vâng, nếu chúng ta không thực hiện bất kỳ giao dịch hoán đổi trên một pass-thông qua danh sách,
thì rõ ràng rằng danh sách đã được sắp xếp bởi vì chúng tôi đã không trao đổi bất cứ điều gì.
Vì vậy, chúng tôi chắc chắn không phải sắp xếp lại.
>> Có lẽ bạn có thể khởi tạo một biến cờ được gọi là 'không được sắp xếp'
sai và thay đổi nó để thực sự nếu bạn phải trao đổi bất kỳ yếu tố trên
một lặp đi lặp lại thông qua các mảng.
Hoặc tương tự như vậy, làm cho một truy cập để đếm có bao nhiêu giao dịch hoán đổi bạn thực hiện
trên bất kỳ lặp đi lặp lại nhất định.
Vào cuối của sự lặp lại, nếu bạn không trao đổi bất kỳ của các yếu tố,
bạn biết danh sách đã được sắp xếp và bạn đang làm.
Bubble Phân loại, như các thuật toán phân loại khác, có thể là
tinh chỉnh để làm việc cho bất kỳ yếu tố trong đó có một phương pháp đặt hàng.
>> Tức là, với hai yếu tố bạn có một cách để nói nếu một trong những người đầu tiên
lớn hơn, bằng hoặc nhỏ hơn lần thứ hai.
Ví dụ, bạn có thể sắp xếp các chữ cái trong bảng chữ cái bằng cách nói
a <b, b <c, vv
Hoặc bạn có thể sắp xếp các ngày trong tuần chủ nhật là ít hơn so với thứ hai
đó là ít hơn thứ ba.
>> Sắp xếp bong bóng không có nghĩa là một thuật toán sắp xếp rất hiệu quả nhanh chóng.
Trường hợp xấu nhất thời gian chạy là Big O n ²
bởi vì bạn phải thực hiện lặp đi lặp lại n thông qua một danh sách
kiểm tra tất cả các yếu tố n mỗi pass-through, nxn = n ².
Thời gian chạy này có nghĩa rằng, cũng như số lượng của các yếu tố bạn đang phân loại tăng,
tăng thời gian chạy bình phương.
>> Nhưng nếu hiệu quả không phải là một mối quan tâm chính của chương trình của bạn
hoặc nếu bạn chỉ sắp xếp một số lượng nhỏ các nguyên tố,
bạn có thể tìm thấy Sắp xếp Bubble hữu ích bởi vì
nó là một trong những thuật toán sắp xếp đơn giản để hiểu
và mã.
Nó cũng là một cách tuyệt vời để có được kinh nghiệm với dịch một lý thuyết
thuật toán vào mã hoạt động thực tế.
Vâng, đó là bong bóng sắp xếp cho bạn. Cảm ơn bạn đã cho xem.
CS50.TV