>> [MUSIC CHƠI]
DOUG LLOYD: Tất cả các bên phải, vì vậy bubble sort là một thuật toán
bạn có thể sử dụng để sắp xếp một tập các phần tử.
Chúng ta hãy xem làm thế nào nó hoạt động.
>> Vì vậy, ý tưởng cơ bản đằng sau bubble sort này.
Chúng ta thường muốn di chuyển cao hơn yếu tố có giá trị thường sang bên phải,
và giảm các yếu tố có giá trị chung bên trái, như chúng ta mong đợi.
Chúng tôi muốn những điều thấp hơn để được ở đầu, và những điều cao hơn
để được ở cuối.
>> Làm thế nào để chúng tôi làm điều này?
Vâng trong mã giả, chúng ta có thể nói, chúng ta hãy
thiết lập một vùng trao đổi truy cập đến một giá trị khác không.
Chúng ta sẽ thấy lý do tại sao chúng tôi làm điều đó trong một giây.
Và sau đó chúng ta lập lại sau quá trình cho đến quầy trao đổi là 0,
hoặc cho đến khi chúng tôi thực hiện giao dịch hoán đổi không có ở tất cả.
>> Thiết lập lại các truy cập để hoán đổi 0 nếu nó chưa được 0.
Sau đó nhìn vào mỗi cặp liền kề của các yếu tố.
Nếu hai yếu tố này là không theo thứ tự, trao đổi chúng,
và thêm 1 đến quầy trao đổi.
Nếu bạn đang suy nghĩ về này trước khi bạn hình dung nó,
nhận thấy rằng điều này sẽ di chuyển thấp hơn yếu tố có giá trị bên trái
và các yếu tố bên phải cao hơn giá trị, làm hiệu quả những gì chúng tôi muốn làm,
đó là di chuyển những nhóm các yếu tố theo cách đó.
Chúng ta hãy hình dung như thế nào đây có thể nhìn bằng cách sử dụng mảng của chúng tôi
mà chúng tôi sử dụng để kiểm tra ra các thuật toán.
Chúng tôi có một mảng không được phân loại ở đây một lần nữa, chỉ ra bởi tất cả các yếu tố
là màu đỏ.
Và tôi đặt swap truy cập của tôi đến một giá trị khác.
Tôi tùy tiện chọn tiêu cực 1-- nó không phải là 0.
Chúng tôi muốn lặp lại quá trình này cho đến quầy trao đổi là 0.
Đây là lý do tại sao tôi đặt trao đổi của tôi truy cập vào một số giá trị khác không,
bởi vì nếu không trao đổi truy cập sẽ là 0.
Chúng tôi thậm chí sẽ không bắt đầu quá trình của thuật toán.
Vì vậy, một lần nữa, các bước are-- thiết lập lại các truy cập swap
0, sau đó nhìn vào mỗi liền kề cặp, và nếu họ đang trong trật tự,
trao đổi chúng, và thêm 1 đến quầy trao đổi.
Vì vậy, chúng ta hãy bắt đầu quá trình này.
Vì vậy, điều đầu tiên chúng tôi làm là chúng tôi thiết lập các quầy trao đổi để 0,
và sau đó chúng tôi bắt đầu tìm kiếm ở mỗi cặp liền kề.
>> Vì vậy, đầu tiên chúng ta bắt đầu nhìn vào 5 và 2.
Chúng tôi thấy rằng họ đang ra khỏi đặt hàng và vì vậy chúng tôi trao đổi chúng.
Và chúng ta thêm 1 đến quầy trao đổi.
Vì vậy bây giờ truy cập trao đổi của chúng tôi là 1, và 2 và 5 đã được chuyển sang.
Bây giờ chúng ta lặp lại quá trình này một lần nữa.
>> Chúng tôi nhìn vào cặp liền kề, 5 và 1-- họ cũng ra khỏi trật tự,
vì vậy chúng tôi trao đổi chúng và thêm 1 đến quầy trao đổi.
Sau đó, chúng ta nhìn vào 5 và 3.
Họ là trong trật tự, vì vậy chúng tôi trao đổi họ và chúng tôi thêm 1 đến quầy trao đổi.
Sau đó, chúng ta nhìn vào 5 và 6.
Họ đang ở trong trật tự, vì vậy chúng tôi không thực sự cần phải trao đổi bất cứ điều gì lúc này.
Sau đó, chúng ta nhìn vào 6 và 4.
Họ cũng đang trong trật tự, vì vậy chúng tôi trao đổi họ và chúng tôi thêm 1 đến quầy trao đổi.
>> Bây giờ chú ý những gì đã xảy ra.
Chúng tôi đã chuyển 6 tất cả các cách để kết thúc.
Vì vậy, trong việc lựa chọn loại, nếu bạn đã xem video đó, những gì chúng tôi làm là
chúng tôi đã kết thúc di chuyển yếu tố nhỏ nhất trong xây dựng
các mảng được sắp xếp cơ bản từ trái sang phải, nhỏ nhất đến lớn nhất.
Trong trường hợp của bong bóng sắp xếp, nếu chúng tôi sau thuật toán cụ thể này,
chúng tôi đang thực sự sẽ được xây dựng các mảng được sắp xếp từ bên phải
sang trái, lớn nhất đến nhỏ nhất.
Chúng tôi đã có hiệu quả các bọt khí 6, giá trị lớn nhất, tất cả các cách để kết thúc.
>> Và như vậy chúng ta có thể khai báo rằng đó là sắp xếp,
và trong tương lai iterations-- đi qua mảng again--
chúng ta không cần phải xem xét 6 nữa.
Chúng tôi chỉ phải xem xét các yếu tố không được phân loại
khi chúng ta nhìn vào cặp liền kề.
Vì vậy, chúng tôi đã hoàn thành một đi qua bong bóng sắp xếp.
Vì vậy, bây giờ chúng ta quay trở lại với câu hỏi, lặp lại cho đến quầy trao đổi là 0.
Vâng quầy trao đổi là 4, vì vậy chúng tôi đang đi
để tiếp tục lặp lại quá trình này một lần nữa.
>> Chúng tôi sẽ thiết lập lại các truy cập swap đến 0, và nhìn vào từng cặp liền kề.
Vì vậy, chúng ta bắt đầu với 2 và 1-- họ trong trật tự, vì vậy chúng tôi trao đổi chúng
và chúng tôi thêm 1 đến quầy trao đổi.
2 và 3, họ đang ở trong trật tự.
Chúng tôi không cần phải làm gì cả.
3 và 5 là theo thứ tự.
Chúng tôi không cần phải làm bất cứ điều gì ở đó.
>> 5 và 4, họ đang ra trật tự, và vì vậy chúng tôi
cần trao đổi chúng và thêm 1 đến quầy trao đổi.
Và bây giờ chúng tôi đã chuyển 5, các phần tử lớn nhất tiếp theo,
đến hết phần được phân loại.
Vì vậy, bây giờ chúng ta có thể gọi đó một phần của các phần được sắp xếp.
>> Bây giờ bạn đang nhìn vào màn hình và có lẽ có thể nói,
như tôi có thể, rằng mảng được sắp xếp ngay bây giờ.
Nhưng chúng ta không thể chứng minh rằng chưa.
Chúng tôi không có một đảm bảo mà nó được sắp xếp.
Nhưng đây là nơi trao đổi truy cập sẽ đi vào chơi.
>> Vì vậy, chúng tôi đã hoàn thành một đường chuyền.
Các trao đổi truy cập là 2.
Vì vậy, chúng ta sẽ lặp lại quá trình này một lần nữa,
lặp lại cho đến quầy trao đổi là 0.
Thiết lập lại các truy cập swap 0.
Vì vậy, chúng tôi sẽ thiết lập lại nó.
>> Bây giờ nhìn vào mỗi cặp liền kề.
Đó là theo thứ tự, 1 và 2.
2 và 3 là theo thứ tự.
3 và 4 theo thứ tự.
Vì vậy, tại thời điểm này, nhận thấy chúng ta đã hoàn thành nhìn vào từng cặp liền kề,
nhưng quầy trao đổi vẫn là 0.
>> Nếu chúng ta không cần phải chuyển đổi bất kỳ yếu tố, sau đó họ
phải theo thứ tự, bởi đức của quá trình này.
Và do đó, một hiệu quả của các loại, các nhà khoa học máy tính của chúng ta yêu thương,
bây giờ chúng ta có thể khai báo toàn bộ mảng phải
được sắp xếp, bởi vì chúng tôi đã không phải trao đổi bất kỳ yếu tố.
Đó là khá tốt đẹp.
>> Vì vậy, trường hợp xấu nhất là gì kịch bản với bong bóng sắp xếp?
Trong trường hợp xấu nhất là mảng theo thứ tự ngược lại hoàn toàn,
và vì vậy chúng tôi phải bong bóng mỗi trong những yếu tố lớn tất cả
các cách trên mảng.
Và chúng tôi có hiệu quả cũng phải bong bóng tất cả các yếu tố nhỏ lại
tất cả các cách trên mảng, quá.
Vì vậy, mỗi nguyên tố n có để di chuyển trên tất cả các yếu tố n khác.
Vì vậy, đó là kịch bản trường hợp xấu nhất.
Trong trường hợp tốt nhất kịch bản mặc dù, đây là
hơi khác nhau từ sắp xếp chọn.
Các mảng là đã được sắp xếp khi chúng ta đi vào.
Chúng tôi không có thực hiện bất kỳ giao dịch hoán đổi trên đèo đầu tiên.
Vì vậy, chúng ta có thể phải xem xét vào các yếu tố ít hơn, phải không?
Chúng tôi không cần phải lặp lại điều này xử lý một số lần.
>> Vì vậy, có nghĩa là gì?
Vì vậy, trường hợp xấu nhất là gì cho bong bóng sắp xếp, và những gì
trường hợp kịch bản tốt nhất cho bong bóng sắp xếp?
Bạn đã đoán này?
Trong trường hợp xấu nhất bạn phải lặp trên tất cả các yếu tố n lần n.
Vì vậy, trường hợp xấu nhất là n bình phương.
>> Nếu mảng là hoàn hảo sắp xếp, mặc dù bạn chỉ
phải nhìn vào mỗi của các yếu tố một lần.
Và nếu quầy trao đổi vẫn là 0, bạn có thể nói mảng này được sắp xếp.
Và do đó, trong trường hợp tốt nhất, đây là thực sự tốt hơn so với lựa chọn
sort-- nó omega của n.
>> Tôi Doug Lloyd.
Đây là CS50.