Tìm hiểu thuật toán sắp xếp nổi bọt trong lập trình với ví dụ lập trình c++ Trong bài viết này Stanford sẽ chia sẻ cho các bạn học lập trình về thuật toán sắp xếp nổi bọt (bubble sort) trong lập trình và ví dụ cài đặt thuật toán sắp xếp nổi bọt bằng lập trình c++. Thuật toán sắp xếp nổi bọt (bubble sort) Thuật toán sắp xếp nổi bọt (bubble sort) là thuật toán sắp xếp đơn giản nhất hoạt động bằng cách hoán đổi liên tục các phần tử liền kề nếu chúng không đúng thứ tự. Thuật toán này thường được sử dụng để giới thiệu khái niệm sắp xếp và đặc biệt phù hợp để sắp xếp các tập dữ liệu nhỏ. Sau khi hiểu cách thức hoạt động của thuật toán, chúng ta sẽ tìm hiểu cách triển khai thuật toán sắp xếp nổi bọt trong lập trình C++. Ý tưởng của thuật toán sắp xếp nổi bọt Để sắp xếp một tập dữ liệu bằng thuật toán sắp xếp nổi bọt, hãy làm theo các bước dưới đây: Bắt đầu bằng cách so sánh hai phần tử đầu tiên . Nếu chúng không đúng thứ tự, hãy hoán đổi chúng. Tiếp tục quá trình này cho tất cả các phần tử di chuyển từ trái sang phải . Sau lần di chuyển đầu tiên, phần tử lớn nhất sẽ ở cuối. Trong lần chạy tiếp theo, bỏ qua phần tử cuối cùng vì nó đã được sắp xếp và lặp lại các bước trên. Phần tử lớn thứ hai sẽ di chuyển đến vị trí thứ hai từ dưới lên. Lặp lại các bước cho đến khi toàn bộ mảng được sắp xếp. Thuật toán này dùng để tăng thứ tự nhưng chỉ cần thay đổi nhỏ là có thể triển khai được bất kỳ thứ tự mong muốn nào. Chương trình C++ để triển khai sắp xếp nổi bọt Chương trình bên dưới sắp xếp một vector bằng thuật toán sắp xếp nổi bọt bằng lập trình c++: // C++ program for the implementation of Bubble sort #include <vector> using namespace std; void bubbleSort(vector<int>& v) { int n = v.size(); // Sử dụng vòng lặp để sắp xếp các phần tử for (int i = 0; i < n - 1; i++) { // Nếu tìm phần tử thỏa mãn thì hoán đổi for (int j = 0; j < n - i - 1; j++) { //So sánh nếu thỏa mãn if (v[j] > v[j + 1]) //Thực hiện hoán đổi vị trí 2 phần tử swap(v[j], v[j + 1]); } } } int main() { vector<int> v = {-2, 0, -9, 11, 45}; //Sorting the vector v bubbleSort(v); for (auto i : v) cout << i << " "; return 0; } Minh họa thuật toán qua ví dụ dưới hình sau: Phân tích độ phức tạp của sắp xếp bong bóng Độ phức tạp thời gian: O(n^2) Độ phức tạp của không gian: O (1) Tối ưu hóa Chúng ta có thể nhận thấy trong thuật toán trên rằng nếu vòng lặp bên trong không gây ra bất kỳ sự hoán đổi nào, mảng đã được sắp xếp, nhưng nó vẫn sẽ chạy với thời gian O(n^2). Điều này 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 không gây ra bất kỳ sự hoán đổi nào. Chúng ta có thể sử dụng biến cờ để chỉ ra sự hoán đổi đã xảy ra hay chưa. // C++ program for the implementation of Bubble sort #include <vector> using namespace std; void bubbleSort(vector<int>& v) { int n = v.size(); // Sử dụng vòng lặp để sắp xếp các phần tử for (int i = 0; i < n - 1; i++) { bool flag = false; // Nếu tìm phần tử thỏa mãn thì hoán đổi for (int j = 0; j < n - i - 1; j++) { //So sánh nếu thỏa mãn if (v[j] > v[j + 1]){ //Thực hiện hoán đổi vị trí 2 phần tử swap(v[j], v[j + 1]); flag = true; } } if (!flag) break; } } int main() { vector<int> v = {-2, 0, -9, 11, 45}; //Sorting the vector v bubbleSort(v); for (auto i : v) cout << i << " "; return 0; } Đầu ra -9 -2 0 11 45 Độ phức tạp thời gian: O(n^2) Độ phức tạp không gian: O(1) Như vậy qua bài viết này, Stanford đã giúp các bạn học lập trình hiểu hơn về thuật toán sắp nổi bọt (bubble sort) cũng như cài đặt thuật toán bằng lập trình c++. Để hiểu rõ hơn thuật toán này bạn có thể lập trình theo hướng dẫn trong bài viết này nhé. Bạn có thể tìm hiểu các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công ! Bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé. ==========🎬 🎬 🎬========== ☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ Hotline: 0963 723 236 - 0866 586 366 Website: https://stanford.com.vn Facebook: https://www.facebook.com/Stanford.com.vn Youtube: http://bit.ly/2TkKT7I Tags: thuật toán sắp xếp nổi bọt bubble sort