Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) - Freetuts

Lập trình WordPress Hosting Thủ thuật Tin học Môn học C / C++ Giải thuật HTML / CSS Javascript jQuery Bootstrap PHP Java Python C# SQL Server MySQL NodeJS SẮP XẾP & TÌM KIẾM Sắp xếp và tìm kiếm là gì? Tìm kiếm tuyến tính Tìm kiếm nhị phân Tìm kiếm nội suy Sắp xếp nổi bọt Sắp xếp chèn Sắp xếp chọn Sắp xếp trộn Sắp xếp nhanh CÁC CHỦ ĐỀ Thuật toán căn bản Sắp xếp & tìm kiếm Giải thuật đệ quy Danh sách liên kết đơn Danh sách liên kết đôi Cấu trúc cây Ngăn xếp Stack Hàng đợi Queue BÀI MỚI NHẤT Các kiểu dữ liệu trong C ( int - float - double - char ...) Thuật toán tìm ước chung lớn nhất trong C/C++ Thuật toán tính lũy thừa nhanh trong C/C++ Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) ComboBox - ListBox trong lập trình C# winforms Random trong Python: Tạo số random ngẫu nhiên Cách kết nối SQL Server trong C# Winforms Lệnh cin và cout trong C++ MỚI CẬP NHẬT Cách khai báo biến trong PHP, các loại biến thường gặp Download và cài đặt Vertrigo Server Thẻ li trong HTML Thẻ nav trong HTML5 Thẻ article trong HTML5 Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên Cách dùng thẻ img trong HTML và các thuộc tính của img Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Home > Giải thuật > Sắp xếp & tìm kiếm > 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)

Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp nổi bọt (Bubble Sort). Đây là một thuật toán sắp xếp khá đơn giản và dễ hiểu.

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau tìm hiểu về khái niệm sắp xếp nổi bọt (Bubble Sort), thuật toán sắp xếp và cách triển khai. Sau đó mình sẽ có một ví dụ đơn giản áp dụng thuật toán (mình sẽ sử dụng ngôn ngữ C++ để viết).

1. Sắp xếp nổi bọt (Bubble Sort) là gì?

Sắp xếp nổi bọt được hiểu đơn giản như sau:

Thuật toán sắp xếp nổi bọt (Bubble Sort) sẽ tiến hành việc so sánh các cặp phần tử liền kề nhau và tráo đổi vị trí của nó cho đúng thứ tự mà người dùng mong muốn.

Bài viết này được đăng tại [free tuts .net]

Ví dụ:

Chúng ta có một tập các số như sau: A = {20; 5; 25; 30; 22; 40}. Giả sử chúng ta muốn sắp xếp theo chiều tăng dần từ trái sang phải, thì thuật toán sẽ hoạt động như sau:

• Thuật toán sẽ bắt đầu với cặp phần tử đầu tiên là {20; 5}. Trong cặp phần tử này 20 > 5 vì vậy thuật toán sẽ hoán đổi vị trí số 20 cho vị trí số 5. Sau khi hoán đổi được cặp phần tử mới là {5; 20}.
• Tiếp đến thuật toán sẽ so sánh cặp phần tử {20;25}. Trong trường hợp này vị trí của hai phần tử đã đúng, vì vậy thuật toán sẽ giữ nguyên vị trí của nó.
• Cứ như vậy thuật toán sẽ so sánh đến hết các cặp phần tử của tập A. Sau khi so sánh đến hết sẽ được kết quả như sau: A = {5; 20; 22; 25; 30; 40}.

Thuật toán này được áp dụng cho các tập dữ liệu nhỏ, vì nó lặp hết tất cả các phần tử có trong tập. Điều này tốn rất nhiều thời gian, đầy là một thuật toán được xem là chậm nhất trong số các thuật toán sắp xếp.

2. Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++

Giả sử:

• Chúng ta có arr là một mảng chứa n phần tử.
• Một hàm Swap() để tráo đổi các phần tử (hàm này mình sẽ viết ở bên dưới).

Giải thích thuật toán

• Trong thuật toán chúng ta cần tạo một biến 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.
• Sử dụng vòng lặp for để lặp tất cả các phần tử có trong mảng. Nếu phần tử thứ J > J + 1 thì tiến hành gọi hàm Swap() để tráo đổi vị trí. Sau đó gán haveSwap = true và ngược lại.
• Nếu không có Swap nào được thực hiện thì mảng đã được sắp xếp. Khi đó chúng ta sẽ thoát khỏi vòng lặp và không cần lặp thêm nữa.

Thuật toán sắp xếp nổi bọt C++

void bubbleSort(int arr[], int n) { int i, j; bool haveSwap = false; for (i = 0; i < n-1; i++){ // i phần tử cuối cùng đã được sắp xếp haveSwap = false; for (j = 0; j < n-i-1; j++){ if (arr[j] > arr[j+1]){ swap(arr[j], arr[j+1]); haveSwap = true; // Kiểm tra lần lặp này có swap không } } // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm if(haveSwap == false){ break; } } }

3. Ví dụ sắp xếp nổi bọt áp dụng với mảng

Chúng ta sẽ áp dụng thuật toán trên để làm một bài toán đơn giản. Cụ thể chúng ta sẽ sắp xếp các phần tử có trong một mảng được nhập tử bàn phím.

Gợi ý:

• Việc đầu tiên chúng ta cần tạo hàm Swap() để thực hiện tráo đổi vị trí các phần tử.
• Tiếp theo cần tạo hàm bubbleSort() để thực hiện sắp xếp các phần tử.
• Cuối cùng chỉ cần tạo hàm main và yêu cầu người dùng nhập vào các phần tử cho mảng. Sau đó gọi hàm bubbleSort() để sắp xếp là xong.

Code Mẫu:

#include <iostream> #include <stdio.h> using namespace std; void swap(int &x, int &y) { int temp = x; x = y; y = temp; } // Hàm sắp xếp bubble sort void bubbleSort(int arr[], int n) { int i, j; bool haveSwap = false; for (i = 0; i < n-1; i++){ // i phần tử cuối cùng đã được sắp xếp haveSwap = false; for (j = 0; j < n-i-1; j++){ if (arr[j] > arr[j+1]){ swap(arr[j], arr[j+1]); haveSwap = true; // Kiểm tra lần lặp này có swap không } } // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm if(haveSwap == false){ break; } } } /* Hàm xuất mảng */ void printArray(int arr[], int size) { int i; for (i=0; i < size; i++){ cout << arr[i]; cout<<"\t"; } } int main() { int n; do{ cout << "\nNhập vào số lượng phần tử có trong mảng: "; cin >> n; }while(n <= 0); int a[n]; for(int i = 0;i < n;i++){ cout<<"a["<<i<<"]="; cin >> a[i]; }; bubbleSort(a, n); cout<<"Mảng sau khi được sắp xếp: \n"; printArray(a, n); cout<<"\n---------------------------------------\n"; cout<<"Chương trình này được đăng tại Freetuts.net"; }

Kết quả:

Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử có trong mảng. Cũng như kết thúc hướng dẫn thuật toán sắp xếp nổi bọt (Bubble Sort) trong C++. Chúc các bạn thực hiện thành công!!!.

Bài trước Bài tiếp

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

WORDPRESS HTML Templates Theme WordPress Plugin WordPress Lập trình WordPress Thủ thuật WordPress WEB HOSTING Quản trị Linux Thủ thuật Hosting Kiến thức Domain WEB FRONTEND Javascript AngularJS jQuery jQuery Mobile HTML & CSS Bootstrap TypeScript SASS CSS VueJS NestJS Học ReactJS Tailwind CSS WEB BACKEND PHP Codeigniter Laravel Phalcon OpenCart NodeJS Blogspot DATABASE Học MySQL Học MongoDB CSDL căn bản Học Oracle Học SQL Server Học SQLite TinyDB MariaDB PROGRAMMING Python Java Pascal Học C# Học Ruby Học Swift C / C++ Kotlin Golang Giải thuật Visual Basic ASP .NET R Tutorial AI (Machine Learning) MOBILE DEV React Native Học iOS Android Flutter CÔNG CỤ Học Git Testing Control Panel Dev Tool FFmpeg TIN HỌC Excel Word PowerPoint Access Photoshop MÔN HỌC Tiếng Anh Toán Tiếng Nhật Văn học VIDEO CSS Lab PHP Lab

Giới thiệu

Giới thiệu Liên hệ Chính sách Điều khoản

Thủ thuật

Máy tính Game Điện thoại Ứng dụng

Link hay

Học PHP Học Javascript Học Python Học Java

Liên kết

Tiếng Anh Văn học Toán

Copyright © 2021. Phát triển bởi Freetuts Team. Top