Bubble Sort trong Java

Java Sorting là một trong nhiều khía cạnh của câu hỏi phỏng vấn Java . Trong bài đăng này, chúng ta sẽ xem ví dụ Bubble Sort trong Java và viết một chương trình cho sắp xếp Bubble.

Bubble Sort còn được gọi là sắp xếp trao đổi. Đây là thuật toán đơn giản nhất để sắp xếp các số.

LUYỆN THI CHỨNG CHỈ OCA

Thuật toán Bubble Sort trong Java

• Trong Bubble Sort, mảng các số nguyên được chuyển từ chỉ số 0 đến độ dài-1.
• Giá trị ở vị trí thứ 0 được so sánh với giá trị ở vị trí đầu tiên và nếu giá trị sau đó nhỏ hơn, nó sẽ được hoán đổi.
• So sánh được chuyển từ chỉ mục thứ 0 sang chỉ mục độ dài 1 để sau lần lặp đầu tiên, chỉ mục cuối cùng có giá trị lớn nhất.
• Quá trình tương tự được lặp lại một lần nữa từ chỉ mục thứ 0 đến độ dài-1. Sau lần lặp (độ dài-1), mảng được sắp xếp.
• Trong trường hợp xấu nhất, độ phức tạp của Bubble Sort là O (n2) và trong trường hợp tốt nhất, độ phức tạp của sắp xếp bong bóng là Ω (n).

Bubble Sort trong Java

Đây là cách thực hiện Bubble Sort trong chương trình Java.

import java.util.Arrays;

public class BubbleSort {

	public static void main(String args[]) {
		int arr[] = { 5,4,3,2,1 };
		int arr1[] = { 1,2,3,4,5 };
		System.out.println("Array after sorting in ascending order:"+Arrays.toString(bubbleSortAscending(arr)));
		System.out.println("Array after sorting in descending order:"+Arrays.toString(bubbleSortDescending(arr1)));
	}
	
	public static int[] bubbleSortAscending(int[] arr){
		int temp;
		for(int i=0; i < arr.length-1; i++){
			
			for(int j=1; j < arr.length-i; j++){
				if(arr[j-1] > arr[j]){
					temp=arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = temp;
				}
			}
			//check that last index has highest value in first loop,
			// second last index has second last highest value and so on
			System.out.println("Array after "+(i+1)+"th iteration:"+Arrays.toString(arr));
		}
		return arr;
	}
	
	public static int[] bubbleSortDescending(int[] arr){
		int temp;
		for(int i=0; i < arr.length-1; i++){
			
			for(int j=1; j < arr.length-i; j++){
				if(arr[j-1] < arr[j]){
					temp=arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = temp;
				}
			}
			//check that last index has highest value in first loop,
			// second last index has second last highest value and so on
			System.out.println("Array after "+(i+1)+"th iteration:"+Arrays.toString(arr));
		}
		return arr;
	}

}
Code language: PHP (php)

Chương trình trên dùng để sắp xếp theo thứ tự tăng dần cũng như giảm dần bằng cách sử dụng thuật toán sắp xếp bong bóng.

Output:

Array after 1th iteration:[4, 3, 2, 1, 5]
Array after 2th iteration:[3, 2, 1, 4, 5]
Array after 3th iteration:[2, 1, 3, 4, 5]
Array after 4th iteration:[1, 2, 3, 4, 5]
Array after sorting in ascending order:[1, 2, 3, 4, 5]
Array after 1th iteration:[2, 3, 4, 5, 1]
Array after 2th iteration:[3, 4, 5, 2, 1]
Array after 3th iteration:[4, 5, 3, 2, 1]
Array after 4th iteration:[5, 4, 3, 2, 1]
Array after sorting in descending order:[5, 4, 3, 2, 1]Code language: JavaScript (javascript)

Như chúng ta có thể thấy rằng trong mỗi lần lặp, chỉ mục cuối cùng đang được sắp xếp và cần (độ dài mảng – 1) lần lặp để sắp xếp.

Happy learning!!!

HỌC JAVA CORE~