Bubble Sort Là Gì

Để bắt đầu với Series bài học về thuật toán, hôm nay chúng ta cùng tìm hiểu một thuật toán đơn giản đó là thuật toán Bubble sort.
*
Thuật toán Bubble sort (Sắp xếp nổi bọt)
Bubble Sort (Sắp xếp nổi bọt) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap).Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang).Sắp xếp nổi bọt còn có tên gọi khác là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.

Bạn đang xem: Bubble sort là gì

Sắp xếp từ trái sang(Từ trên xuống)
*
Thuật toán sắp xếp nổi bọt: Từ trái sang
Giả sử dãy cần sắp xếp có n phần tử.Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu ở bên trái mảng.Nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau.Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu.Nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n - 1 với phần tử thứ n.Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n - 2....Lưu ý: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì danh sách đã được sắp xếp xong.Sắp xếp từ phải sang(Từ bên dưới lên)
*
Thuật toán sắp xếp nổi bọt: Từ phải sang
Sắp xếp từ phải sang so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n - 1 và n.Tiếp theo là so sánh cặp phần tử thứ n - 2 và n - 1,... cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai.Sau bước này phần tử nhỏ nhất đã được nổi lên vị trí trên cùng.Việc này giống như hình ảnh của các "bọt" khí nhẹ hơn được nổi lên trên.Chính vì thế, đây được gọi là thuật toán sắp xếp nổi bọt.Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.Độ phức tạp của giải thuật : O(n2)
Ví dụ ta có một mảng các số không theo thứ tự 5 1 4 2 8 thì sử dụng thuật toán Bubble Sort để tiến hành việc sắp xếp sẽ như thế nào?
*
Ví dụ thuật toán Bubble sort
Hãy xem phần mô tả thô bên dưới.Tại lần lặp thứ 1:Thuật toán so sánh hai phần tử đầu tiên và hoán đổi vị trí cho nhau vì 5 > 1
*

So sánh 2 phần tử cuối thấy 8 > 5 nên không thay đổi vị tríTại lần lặp thứ 2:Lần lặp thứ 2, so sánh 2 phần tử đầu tiên thấy 1 nên không hoán đổi vị trí của chúng.Hoán đổi vị trí của 4 và 2 cho nhau vì 4 > 2.
Tiếp theo, so sánh thấy 4 nên không thay đổi vị tríSo sánh thấy 5 nên không thay đổi vị tríBây giờ, mảng đã được sắp xếp, nhưng thuật toán của chúng ta không biết liệu nó đã hoàn thành hay chưa.Thuật toán cần một lần lặp qua toàn bộ mà không có bất kỳ sự hoán đổi nào để biết nó được là đã sắp xếp thành công.

Xem thêm: Cách Xóa Nick Fb Vĩnh Viễn Hoặc Tạm Thời, Cách Nhanh Nhất Để Xoá Nick Facebook Vĩnh Viễn

Tại lần lặp thứ 3:
Như bạn thấy ở hình minh họa trên. Lần lặp thứ 3 này, chương trìnhkiểm tra 2 phần tử liền kề của mảng nhưngkhông cần phải thay đổi vị trí lần nào.
Bạn đã hiểu về ý tưởng của thuật toán Bubble sort. Bây giờ, chúng ta hãy cùng nhau triển khai ý tưởng đó thành code xem như thế nào nhé.
Phần code bên trên (tức hàm bubbleSort) luôn chạy với thời gian làO(n^2)ngay cả khi mảng được sắp xếp.Nó có thể được tối ưu hóa bằng cách dừng thuật toán nếu vòng lặp bên trong mà không gây ra bất kỳ sự hoán đổi nào.
Do tính đơn giản của nó, sắp xếp nổi bọt thường được sử dụng để giới thiệu khái niệm về thuật toán sắp xếp.Mặc dù là giải thuật khá chậm trong số các thuật toán sắp xếp nhưng thuật toán Bubble Sort vẫn luôn có chỗ đứng trong việc giải quyết các vấn đề thực tế.Chẳng hạn như việc phát hiện một lỗi rất nhỏ (như hoán đổi chỉ hai phần tử) trong các mảng gần như được sắp xếp và sửa nó chỉ với độ phức tạp tuyến tính (2n) trong đồ hoạ máy tính.Đây là thuật toán mở đầu cho phần chia sẻ của mình trong Series này.Hy vọng nó mang đến hứng thú và hữu ích với các bạn trong quá trình tìm hiểu về thuật toán, đặc biệt là với những bạn đang học Java.> Nếu bạn đang tự học Java mà cảm thấy khó khăn thì KHÓA HỌC JAVA WEB (Full Stack) này có lẽ sẽ giúp bạn học tốt hơn. Tham khảo ngay nhé.---
#niit #phukienotocaocap.com #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #java #php #python
6260+ học viên đã theo học tại NIIT - ICT Hà Nội và có việc làm tốt trong ngành lập trình. Nắm lấy cơ hội ngay hôm nay!
Khóa học Java Full stack (IJFD) Khóa học PHP Full stack <2021> cho người mới bắt đầu Khóa học lập trình Java Web 4.0 Khóa học Lập trình Android tại Hà Nội CHƯƠNG TRÌNH ĐÀO TẠO THEO CÔNG NGHỆ KHÓA HỌC LẬP TRÌNH FRONT END VỚI REACT.JS FRONT-END VỚI REACTJS VÀ REACT NATIVE Lập trình PHP với Laravel Framework Khóa học PYTHON cho người mới bắt đầu (IPD2021) KHÓA HỌC ANGULAR & TYPESCRIPT (FRONT END) Lập trình Java Web Nâng cao Lập trình Android Nâng cao CHƯƠNG TRÌNH ĐÀO TẠO ỨNG DỤNG CÔNG NGHỆ VBA Excel Toàn Tập (Cơ Bản - Nâng Cao) Khóa học Tiền lương & Phúc lợi (C&B Excel) tại Hà Nội CHƯƠNG TRÌNH ĐÀO TẠO CHO DOANH NGHIỆP Khóa học Magento: Làm chủ CMS TMĐT lớn nhất Khóa học BIG DATA với Hadoop và Spark Khóa học IOT: Xây dựng Sản phẩm IOT với Raspberry Pi