[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