Thuật toán sắp xếp nổi bọt là gì? GIới thiệu thuật toán sắp xếp nổi bọt bubble sort C/C++. Hướng dẫn cách viết giải thuật nổi bọt bubble sort chi tiết. Xem thêm
Tóm Tắt
Bubble sort là một thuật toán sắp xếp được sử dụng khá phổ biến trong
C
/
C++
. Bài viết này sẽ giúp bạn hiểu rõ hơn về Bubble sort nhé!
Bubble Sort là gì? Thuật toán sắp xếp Bubble Sort trong C/C++
I. Sắp xếp nổi bọt – Bubble sort là gì?
1. Khái niệm
Bubble sort hay thuật toán sắp xếp nổi bọt là thuật toán giúp người dùng hoán đổi vị trí các cặp phần tử liền kề nhau cho đúng thứ tự bằng cách so sánh chúng với nhau, từ đó hoán đổi vị trí và sắp xếp lại thành một chuỗi theo thứ tự nhất định.
Thuật toán sắp xếp sẽ bắt đầu với 2 chữ số đầu tiên là a[0] và a[1]. Nếu a[0]>a[1], ta sẽ hoán vị chúng với nhau. Cứ như vậy lần lượt ta sẽ so sánh số thứ hai và thứ ba và chạy cho đến hết mảng hoặc đến vị trí trước vị trị đã sắp xếp trước đó thì hoàn thành.
Ví dụ về thuật toán sắp xếp Bubble Sort trong C/C++
2. Ý tưởng
Bắt đầu từ đầu mảng, ta so sánh 2 phần tử cạnh nhau để đưa phần tử nhỏ lên trước, sau đó tiến hành so sánh cặp tiếp theo và thực hiện tương tự cho đến cuối đầu chuỗi bên kia. Từ đó suy ra ở lần xử lý thứ i sẽ tìm được phần tử ở vị trí đầu chuỗi là i.
3. Giải thuật
Bước 1: Gán i=0 (lần xử lý đầu tiên)
Bước 2: Lần lượt so sánh các giá trị từ phải sang trái. Nếu giá trị phía trước lớn hơn giá trị phía sau thì ta tiến hành hoán vị.
- j=n (duyệt từ cuối dây trở về vị trí cần tìm)
- Nếu a[j]<a[j+1]: hoán vị a[j] và a[j-1]
- Chạy cho đến khi j < n-1
Bước 3: Tiếp tục rà soát tiếp cho đến hết hết chuỗi.
- i=i+1 (lần xử lý tiếp theo)
- Nếu i > n thì dừng vòng lặp
- Nếu i ≤ n-1 thì lặp lại bước 2.
II. Cách viết thuật toán sắp xếp nổi bọt – Bubble Sort
1. Code minh họa
Code: Thuật toán sắp xếp nổi bọt bubble sort
2. Gợi ý
- Tạo biến hoán vị haveSwap để kiểm tra xem tại lần lặp hiện tại có xảy ra việc trao đổi hai số hay không.
- Dụng vòng lặp for để kiểm tra và hoán vị tất cả các phần tử có trong mảng. Nếu phần tử thứ j > j + 1 thì dùng hàm Swap() để tráo đổi vị trí. Sau đó gán haveSwap = true và ngược lại.
- Nếu không có hoán vị nào được thực hiện nghĩa là mảng đã được sắp xếp đúng thứ tự. Khi đó chúng ta sẽ thoát khỏi vòng lặp.
Ví dụ minh họa
Hy vọng bài viết này sẽ giúp bạn làm chủ được Bubble sort để ứng dụng vào công việc một cách hiệu quả nhất nhé. Chúc các bạn thực hiện thành công!
Nguồn tham khảo: Freetus.net
Trung tâm chuyên sửa chữa thay thế, bảo hành miễn phí, nhượng quyền thương hiệu trungtambaohanh.com + marketing.
Trung tâm chuyên sửa chữa thay thế, bảo hành miễn phí, nhượng quyền thương hiệu trungtambaohanh.com + marketing.
