Sắp xếp bong bóng Java

Nếu bạn đã từng nghe nói về các phương pháp sắp xếp trong lập trình, rất có thể đó là thuật toán sắp xếp bong bóng. Nó là một trong những nổi tiếng. Mọi lập trình viên đều biết sắp xếp bong bóng (hoặc ít nhất là nghe nói về nó khi học) không phải vì nó là thuật toán sắp xếp tốt nhất trên thế giới, mà là thuật toán dễ nhất. Thuật toán này thường được sử dụng cho mục đích học tập hoặc bạn có thể lấy nó làm nhiệm vụ trong Cuộc phỏng vấn Java Junior của mình. Thuật toán sắp xếp bong bóng của Java rất dễ hiểu, tuy nhiên nó không phải là một thuật toán hiệu quả. Dù sao, chúng ta hãy tìm ra nó.

sắp xếp là gì

Trước hết, bạn cần hiểu sắp xếp nói chung là gì và chúng ta có thể sắp xếp những gì trong chương trình Java. Nếu chúng ta có thể so sánh hai hoặc nhiều phần tử hoặc đối tượng theo bất kỳ thuộc tính nào của chúng, điều đó có nghĩa là chúng có thể được sắp xếp theo thuộc tính này. Ví dụ: các số theo thứ tự tăng dần hoặc giảm dần hoặc các từ theo bảng chữ cái. Do đó, các yếu tố phải được so sánh với nhau. Nhân tiện, các yếu tố của cái gì? Trong Java, chúng ta có thể so sánh các phần tử của Collections. Ví dụ: chúng ta có thể sắp xếp Array hoặc ArrayList của số nguyên, Chuỗi, v.v.

Sắp xếp bong bóng hoạt động như thế nào

Giả sử, chúng ta cần sắp xếp một mảng các số nguyên theo thứ tự tăng dần, tức là từ số nhỏ nhất đến số lớn nhất. Đầu tiên, chúng ta sẽ đi dọc theo toàn bộ mảng và so sánh từng 2 phần tử lân cận. Nếu chúng sai thứ tự (hàng xóm bên trái lớn hơn hàng xóm bên phải), chúng tôi đổi chỗ cho chúng. Ở lần vượt qua đầu tiên ở cuối sẽ xuất hiện phần tử lớn nhất (nếu ta sắp xếp theo thứ tự tăng dần). Bạn có thể nói, yếu tố lớn nhất “bật lên”. Đó là lý do của tên thuật toán sắp xếp bong bóng. Chúng tôi lặp lại bước đầu tiên từ phần tử đầu tiên đến phần tử tiếp theo. Chúng tôi đã có yếu tố lớn thứ hai ở vị trí tiếp theo đến cuối cùng. Và như thế. Chúng ta có thể cải thiện thuật toán một chút bằng cách kiểm tra xem có ít nhất một trao đổi ở bước trước được thực hiện hay không. Nếu không, chúng tôi dừng chạy dọc theo mảng.

Ví dụ sắp xếp bong bóng

Hãy sắp xếp mảng các số nguyên, một, bạn có thể thấy hình bên dưới. Bước 1: chúng ta đang đi qua mảng. Thuật toán bắt đầu với hai phần tử đầu tiên (có chỉ số 0 và 1), 8 và 7, và kiểm tra xem chúng có đúng thứ tự không. Rõ ràng, 8 > 7, vì vậy chúng tôi trao đổi chúng. Tiếp theo, chúng tôi xem xét các yếu tố thứ hai và thứ ba (chỉ số 1 và 2), bây giờ đây là 8 và 1. Vì những lý do tương tự, chúng tôi hoán đổi chúng. Lần thứ ba, chúng tôi so sánh 8 và 2 và, ít nhất là 8 và 5. Tổng cộng chúng tôi đã thực hiện bốn lần đổi chỗ: (8, 7), (8, 1), (8, 2) và (8, 5). Giá trị 8, giá trị lớn nhất trong mảng này, xuất hiện ở cuối danh sách ở đúng vị trí. Kết quả của bước đầu tiên của thuật toán sắp xếp bong bóng hoạt động là mảng tiếp theo: Bước 2. Làm tương tự với (7,1), (7,2) và (7,5). 7 giờ đã ở vị trí áp chót, và chúng ta không cần so sánh với "đuôi" của danh sách, nó đã được sắp xếp sẵn. Kết quả của bước thứ hai của thuật toán Sắp xếp bong bóng hoạt động là mảng tiếp theo: Như bạn có thể thấy, mảng này đã được sắp xếp. Dù sao thì thuật toán Sắp xếp bong bóng sẽ hoạt động ít nhất một lần nữa. Bước 3. Chúng ta sẽ xem qua mảng một lần nữa. Không có gì để trao đổi ở đây, vì vậy nếu chúng ta đang sử dụng thuật toán Sắp xếp bong bóng “cải tiến” (với việc kiểm tra xem có ít nhất một lần trao đổi ở bước trước đó được thực hiện hay không) thì bước này là bước cuối cùng.

Mã Java sắp xếp bong bóng

Thực hiện Java sắp xếp bong bóng

Hãy tạo hai phương thức để sắp xếp bong bóng. Cái đầu tiên, bubbleSort(int[] myArray) là một mặt phẳng. Nó chạy qua mảng mọi lúc. Cái thứ hai, OptimBubbleSort(int myArray[]) đượ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ỳ hoán đổi nào. Bộ đếm cho bạn biết bạn đã thực hiện bao nhiêu bước trong khi sắp xếp. Ở đây chúng tôi đã nhận ra Java sắp xếp bong bóng:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array  
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

Kết quả của thuật toán Java sắp xếp bong bóng hoạt động:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

Làm thế nào hiệu quả là sắp xếp bong bóng?

Sắp xếp bong bóng là một trong những thuật toán dễ thực hiện nhất nhưng không hiệu quả. Nó yêu cầu một cặp vòng lặp lồng nhau. Ngay cả trong phiên bản thuật toán được tối ưu hóa trong trường hợp xấu nhất (mỗi phần tử của tập dữ liệu có thứ tự ngược lại với thứ tự mong muốn), vòng lặp bên ngoài lặp lại một lần cho từng phần tử trong số n phần tử của tập dữ liệu. Vòng lặp bên trong lặp lại n lần lần đầu tiên, ( n-1 ) lần thứ hai, v.v. Do đó, để có được tất cả n , các phần tử được sắp xếp, các vòng lặp cần được thực hiện n*(n-1)/2 lần. Nó gọi O(n ² )độ phức tạp về thời gian và có nghĩa là thuật toán thực hiện khoảng 500 000 phép so sánh cho 1000 phần tử của một mảng. Tuy nhiên, thuật toán sắp xếp bong bóng khá hiệu quả trong việc sử dụng bộ nhớ (độ phức tạp của bộ nhớ là O(n) ) và thực sự tốt cho các tập dữ liệu nhỏ được sắp xếp gần hết.