Mô phỏng thuật toán sắp xếp Bubble Sort
Mô phỏng thuật toán sắp xếp Bubble Sort
- Sắp xếp nổi bọt (Bubble Sort) dựa trên ý tưởng trong tuyển quặng:”Quặng nặng thì chìm xuống dưới còn tạp chất nhẹ thì nổi lên trên”.
- Các phần tử có giá trị lớn hơn sẽ bị đẩy về cuối và nhở hơn sẽ đẩy lên trên (trong trường hợp xếp tang dần).
- Bubble sort có 2 cách sắp xếp:
+ Sắp xếp từ trên xuống: Xuất phát từ đầu dãy, ta so sánh và đổi chỗ các cặp nghịch thế đến cuối dãy để đưa phần tử lớn nhất về cuối dãy. Khi đó chỉ việc xét các phần tử còn lại trong dãy và lặp lại các bước để sắp xếp.
+ Sắp xếp từ dưới lên: Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử nghịch thế để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
2.Thuật Toán Bubble Sort:
2.1. Bài toán:
- Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2.2.Ý tưởng:
- Đối với Bubble Sort, ta chọn cặp bằng cách xét hai phần tử kế cận nhau.
*****************************
*********************************************
Nhận xét