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 Gockhampha.edu.vn.COM.VN sẽ giúp bạn hiểu rõ hơn về Bubble sort nhé!
Bạn đang đọc: Bubble sort là gì? Thuật toán sắp xếp nổi bọt bubble sort C/C++
Contents
Sắp xếp nổi bọt – Bubble sort là gì?
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.
Ý 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.
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]
Chạy cho đến khi j
- 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.
Cách viết thuật toán sắp xếp nổi bọt – Bubble Sort
Code minh họa
- Code: Thuật toán sắp xếp nổi bọt bubble sort
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.
Tìm hiểu thêm: Cinematic là gì? Yếu tố tạo thành một bức ảnh Cinematic
>>>>>Xem thêm: ATEEZ profile | Thông tin, tiểu sử về các thành viên trong nhóm
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!
