Viết chương trình sắp xếp tăng dần các phần tử trong mảng bằng phương pháp nổi bọt (Bubble sort).
Bài giải
-------------------- ######## --------------------
Trong phần bài học, tôi đã hướng dẫn các bạn phương pháp phương pháp sắp xếp thông qua phép đổi chỗ trực tiếp (Exchange sort). Ngoài ra, chúng ta còn một phương pháp sắp xếp cũng khá phổ biến mà tôi sẽ sử dụng trong bài tập này đó là phương pháp nổi bọt (Bubble sort). Ý tưởng chính của phương pháp nổi bọt là các phần tử trong mảng sẽ được duyệt từ đáy lên đỉnh. Trên đường duyệt, nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau. Do đó, trong lần duyệt đầu tiên, phần tử có giá trị nhỏ nhất sẽ được chuyển lên đỉnh. Lần duyệt thứ 2, khóa có giá trị nhỏ thứ 2 được chuyển lên vị trí thứ 2... Và cứ tiếp tục như thế cho đến khi toàn bộ mảng các phần tử đã được sắp xếp theo thứ tự tăng dần.
public static void main(String[] args) {
int n, tempSort; // số phần tử của mảng
Scanner scanner = new Scanner(System.in);
// nếu n < 0 thì phải nhập lại
do {
System.out.println("Nhập vào số phần tử của mảng: ");
n = scanner.nextInt();
} while (n < 0);
// khai báo và cấp phát bộ nhớ cho mảng
int array[] = new int[n];
// nhập giá trị các phần tử cho mảng
for (int i = 0; i < n; i++) {
System.out.print("Nhập phần tử thứ " + i + ": ");
array[i] = scanner.nextInt();
}
// hiển thị mảng ban đầu
System.out.println("\nMảng ban đầu: ");
for (int i = 0; i < n; i++) {
System.out.print(array[i] + "\t");
}
// sắp xếp mảng sử dụng phương pháp Bubble sort
// duyệt i từ 0 đến n - 2
// sau mỗi lần duyệt j = n - 1 đến j >= 1
// thì sẽ tìm được phần tử nhỏ nhất
// sau đó tăng i lên 1 và quay lại duyệt j
// khi i > n - 1 thì ngừng vòng lặp
for (int i = 0; i < n - 1; i++) {
for (int j = n - 1; j >= 1; j--) {
// nếu phần tử đứng sau nhỏ hơn phần tử đứng trước
// thì đổi chỗ 2 phần tử đó cho nhau
// với cách sắp xếp này thì trong lần duyệt đầu tiên
// phần tử nhỏ nhất sẽ được chuyển lên trên cùng.
if (array[j] < array[j - 1]) {
tempSort = array[j];
array[j] = array[j-1];
array[j-1] = tempSort;
}
}
}
System.out.println("\nMảng sau khi sắp xếp: ");
for (int i = 0; i < n; i++) {
System.out.print(array[i] + "\t");
}
}
Kết quả sau khi biên dịch chương trình:
Nguồn: freetuts.net
