Sắp xếp nổi bọt trong C# (Bubble Sort)
Trong bài viết này mình sẽ hướng dẫn các bạn cách sắp xếp các phần tử trong một mảng bằng phương pháp sắp xếp nổi bọt (Bubble Sort) trong C#. Mình sẽ thực hiện hai chương trình sắp xếp giảm dần và tăng dần để các bạn có thể so sánh.
1. Sắp xếp nổi bọt là gì (Bubble Sort)?
Thuật toán sắp xếp nổi bọt (Bubble Sort) là thuật toán thực hiện 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à chúng ta mong muốn.
Ví dụ: Giả sử chúng ta có một tập các số như sau: A = {5; 8; -1; 15; 33}, bây giờ để sắp xếp tăng dần từ phải sang trái thì thuật toán sẽ như sau:
- Bắt đầu với cặp phần tử đầu tiên {5; 8}. Trong cặp phần từ này thì 5 < 8 và vị trí của nó đã đúng, vì vậy ta sẽ giữ nguyên vị trí mà không tráo đổi vị trí.
- Cặp phần tử thứ hai là {8; -1}, ở đây 8 > -1, vì vậy ta tráo đổi vị trí thành {-1, 8}.
- Cứ như vậy sẽ so sánh hết các cặp phần tử cho đến khi các phần tử được sắp xếp đúng theo thứ tự tăng dần. A = {-1; 5; 8; 15; 33}.
*Lưu ý: Phương pháp này được áp dụng cho các tập dữ liệu nhỏ, bởi vì nó thực hiện lặp hết các phần tử trong mảng. Điều này tốn nhiều thời gian và đây là phương pháp chậm nhất trong các phương pháp so sánh khác.
Bài viết này được đăng tại [free tuts .net]
2. Sắp xếp tăng dần bằng Bubble Sort trong C#
Dựa vào thuật toán ở trên, mình đã thực hiện chương trình sắp xếp tăng dần bằng thuật toán Bubble Sort trong C#, các bạn có thể tham khảo nhé.
using System; using System.Linq; using System.Text; using System.Collections.Generic; namespace ConsoleApp5 { class Program { static void Main(string[] args) { //khai báo biến count để đếm số lần lặp khi sắp xếp int count = 0, n; //nhập vào số lượng phần tử của mảng, nếu <= 0 thì nhập lại do { Console.Write("\nNhap vao so luong phan tu cua mang: "); n = int.Parse(Console.ReadLine()); } while (n <= 0); //khai báo mảng intArray int[] intArray = new int[n]; Console.WriteLine("Nhap vao cac phan tu cua mang: "); //sử dụng vòng lặp for để nhập các phần tử cho mảng for (int i = 0; i < intArray.Length; i++) { intArray[i] = int.Parse(Console.ReadLine()); } //sử dụng vòng lặp for đẻ lặp qua các phần tử trong mảng for (int j = 0; j <= intArray.Length - 2; j++) { //sử dụng vòng for thứ hai để lặp qua từng cặp phần tử //thực hiện so sánh và đổi vị trí cho đúng thứ tự for (int i = 0; i <= intArray.Length - 2; i++) { count = count + 1; //so sánh hai phần tử kề nhau và đảo vị trí cho đúng thứ tự sắp xếp if (intArray[i] > intArray[i + 1]) { int temp = intArray[i + 1]; intArray[i + 1] = intArray[i]; intArray[i] = temp; } } } Console.Write("Cac phan tu sau khi sap xep:"); //in các phần tử foreach (int item in intArray) { Console.Write(item + " "); } Console.WriteLine(); //in số vòng lặp trong quá trình sắp xếp Console.Write("So vong lap da thuc hien:" + count); Console.WriteLine("\n----Chuong trinh nay duoc dang tai Freetuts.net----\n"); Console.ReadLine(); } } }
Kết quả:
3. Sắp xếp giảm dần bằng Bubble Sort trong C#
Việc sắp xếp giảm dần sẽ khác một chút so với sắp xếp tăng dần. Cần thay đổi điều kiện so sánh giữa hai phần tử kề nhau. Thay vì so sánh PhanTu1 < PhanTu2
ta sẽ thực hiện so sánh PhanTu1 > PhanTu2
để sắp xếp giảm dần.
using System; using System.Linq; using System.Text; using System.Collections.Generic; namespace ConsoleApp5 { class Program { static void Main(string[] args) { //khai báo biến count để đếm số lần lặp khi sắp xếp int count = 0, n; //nhập vào số lượng phần tử của mảng, nếu <= 0 thì nhập lại do { Console.Write("\nNhap vao so luong phan tu cua mang: "); n = int.Parse(Console.ReadLine()); } while (n <= 0); //khai báo mảng intArray int[] intArray = new int[n]; Console.WriteLine("Nhap vao cac phan tu cua mang: "); //sử dụng vòng lặp for để nhập các phần tử cho mảng for (int i = 0; i < intArray.Length; i++) { intArray[i] = int.Parse(Console.ReadLine()); } //sử dụng vòng lặp for đẻ lặp qua các phần tử trong mảng for (int j = 0; j <= intArray.Length - 2; j++) { //sử dụng vòng for thứ hai để lặp qua từng cặp phần tử //thực hiện so sánh và đổi vị trí cho đúng thứ tự for (int i = 0; i <= intArray.Length - 2; i++) { count = count + 1; //so sánh hai phần tử kề nhau và đảo vị trí cho đúng thứ tự sắp xếp if (intArray[i] < intArray[i + 1]) { int temp = intArray[i + 1]; intArray[i + 1] = intArray[i]; intArray[i] = temp; } } } Console.Write("Cac phan tu sau khi sap xep:"); //in các phần tử foreach (int item in intArray) { Console.Write(item + " "); } Console.WriteLine(); //in số vòng lặp trong quá trình sắp xếp Console.Write("So vong lap da thuc hien:" + count); Console.WriteLine("\n----Chuong trinh nay duoc dang tai Freetuts.net----\n"); Console.ReadLine(); } } }
Kết quả:
Trên đây là hai chương trình dùng để sắp xếp các phần tử trong mảng sử dụng phương pháp Bubble Sort. Chúc các bạn thực hiện thành công !!!