Triển khai sắp xếp bong bóng trong Java

Có khá nhiều thuật toán sắp xếp, nhiều thuật toán trong số đó rất cụ thể và được phát triển để giải quyết một phạm vi hẹp các vấn đề và làm việc với các loại dữ liệu cụ thể. Nhưng trong số tất cả sự đa dạng này, thuật toán đơn giản nhất xứng đáng là sắp xếp bong bóng, có thể được triển khai bằng bất kỳ ngôn ngữ lập trình nào. Mặc dù đơn giản nhưng nó làm nền tảng cho nhiều thuật toán khá phức tạp. Một ưu điểm quan trọng không kém khác là tính đơn giản của nó, do đó, nó có thể được ghi nhớ và thực hiện ngay lập tức mà không cần phải có thêm bất kỳ tài liệu nào trước mặt.

Giới thiệu

Toàn bộ Internet hiện đại bao gồm một số lượng lớn các loại cấu trúc dữ liệu khác nhau được thu thập trong cơ sở dữ liệu. Chúng lưu trữ tất cả các loại thông tin, từ dữ liệu cá nhân của người dùng đến cốt lõi ngữ nghĩa của các hệ thống tự động có độ thông minh cao. Không cần phải nói, việc sắp xếp dữ liệu đóng vai trò cực kỳ quan trọng trong lượng thông tin có cấu trúc khổng lồ này. Sắp xếp có thể là một bước bắt buộc trước khi tìm kiếm bất kỳ thông tin nào trong cơ sở dữ liệu và kiến ​​thức về thuật toán sắp xếp đóng vai trò rất quan trọng trong lập trình.

Phân loại qua mắt máy và mắt người

Hãy tưởng tượng rằng bạn cần sắp xếp 5 cột có chiều cao khác nhau theo thứ tự tăng dần. Các cột này có thể có nghĩa là bất kỳ loại thông tin nào (giá cổ phiếu, băng thông kênh liên lạc, v.v.), bạn có thể trình bày một số phiên bản của riêng mình về nhiệm vụ này để làm rõ hơn. Vâng, để làm ví dụ, chúng tôi sẽ sắp xếp Avengers theo chiều cao: Không giống như chương trình máy tính, việc sắp xếp sẽ không gây khó khăn cho bạn vì bạn có thể nhìn thấy toàn bộ bức tranh và có thể tìm ra ngay anh hùng nào cần được di chuyển đến đâu để hoàn thành thành công việc sắp xếp theo chiều cao. Có lẽ bạn đã đoán được rằng để sắp xếp cấu trúc dữ liệu này theo thứ tự tăng dần, chỉ cần hoán đổi vị trí của Hulk và Iron Man:

Xong!

Và điều này sẽ hoàn thành việc phân loại thành công. Tuy nhiên, máy tính, không giống như bạn, hơi ngu ngốc và không nhìn thấy toàn bộ cấu trúc dữ liệu. Chương trình điều khiển của nó chỉ có thể so sánh hai giá trị cùng một lúc. Để giải quyết vấn đề này, cô ấy sẽ phải đặt hai số vào bộ nhớ của mình và thực hiện thao tác so sánh trên chúng, sau đó chuyển sang một cặp số khác, v.v. cho đến khi tất cả dữ liệu được phân tích. Do đó, bất kỳ thuật toán sắp xếp nào cũng có thể được đơn giản hóa dưới dạng ba bước:

• So sánh hai yếu tố;
• Trao đổi hoặc sao chép một trong số chúng;
• Chuyển đến phần tử tiếp theo;

Các thuật toán khác nhau có thể thực hiện các thao tác này theo những cách khác nhau, nhưng chúng ta sẽ chuyển sang xem xét cách hoạt động của sắp xếp bong bóng.

Thuật toán sắp xếp bong bóng

Sắp xếp bong bóng được coi là đơn giản nhất, nhưng trước khi mô tả thuật toán này, hãy tưởng tượng bạn sẽ sắp xếp Avengers theo chiều cao như thế nào nếu bạn có thể, giống như một cỗ máy, chỉ so sánh hai anh hùng với nhau trong một khoảng thời gian. Rất có thể, bạn sẽ làm như sau (tối ưu nhất):

• Bạn di chuyển đến phần tử số 0 trong mảng của chúng tôi (Black Widow);
• So sánh phần tử số 0 (Black Widow) với phần tử đầu tiên (Hulk);
• Nếu phần tử ở vị trí 0 cao hơn, bạn hoán đổi chúng;
• Mặt khác, nếu phần tử ở vị trí 0 nhỏ hơn, bạn để chúng ở vị trí của chúng;
• Di chuyển sang vị trí bên phải và lặp lại so sánh (so sánh Hulk với Thuyền trưởng)

Sau khi bạn xem qua toàn bộ danh sách trong một lần bằng thuật toán như vậy, việc sắp xếp sẽ không được hoàn thành hoàn toàn. Nhưng mặt khác, phần tử lớn nhất trong danh sách sẽ được chuyển sang vị trí ngoài cùng bên phải. Điều này sẽ luôn xảy ra, bởi vì ngay khi bạn tìm thấy phần tử lớn nhất, bạn sẽ liên tục thay đổi vị trí cho đến khi di chuyển nó đến cuối cùng. Nghĩa là, ngay khi chương trình “tìm thấy” Hulk trong mảng, nó sẽ đưa anh ta tiến xa hơn đến cuối danh sách: Đây là lý do tại sao thuật toán này được gọi là sắp xếp bong bóng, vì do hoạt động của nó, phần tử lớn nhất trong danh sách sẽ ở đầu mảng và tất cả các phần tử nhỏ hơn sẽ được dịch chuyển một vị trí sang trái: Để hoàn thành việc sắp xếp, bạn sẽ cần quay lại phần đầu của mảng và lặp lại năm bước được mô tả ở trên một lần nữa, di chuyển lại từ trái sang phải, so sánh và di chuyển các phần tử nếu cần. Nhưng lần này bạn cần dừng thuật toán một phần tử trước khi kết thúc mảng, vì chúng ta đã biết rằng phần tử lớn nhất (Hulk) hoàn toàn nằm ở vị trí ngoài cùng bên phải: Vì vậy chương trình phải có hai vòng lặp. Để rõ ràng hơn, trước khi chúng ta chuyển sang xem lại mã chương trình, bạn có thể xem hình ảnh trực quan về cách hoạt động của sắp xếp bong bóng tại liên kết này: Hình dung về cách hoạt động của sắp xếp bong bóng

Triển khai sắp xếp bong bóng trong Java

Để giải thích cách sắp xếp hoạt động trong Java, đây là mã chương trình:

• tạo một mảng gồm 5 phần tử;
• tải sự trỗi dậy của những người báo thù vào đó;
• hiển thị nội dung của mảng;
• thực hiện sắp xếp bong bóng;
• hiển thị lại mảng đã sắp xếp.

Bạn có thể xem mã bên dưới và thậm chí tải nó xuống IntelliJ IDE yêu thích của bạn. Nó sẽ được phân tích dưới đây:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

Bất chấp các nhận xét chi tiết trong mã, chúng tôi vẫn cung cấp mô tả về một số phương pháp được trình bày trong chương trình. Các phương thức chính thực hiện công việc chính trong chương trình được viết trong lớp ArrayBubble. Lớp này chứa một hàm tạo và một số phương thức:

• into– phương pháp chèn các phần tử vào mảng;
• printer– hiển thị nội dung của mảng theo từng dòng;

• toSwap– sắp xếp lại các phần tử nếu cần thiết. Để làm điều này, một biến tạm thời được sử dụng dummy, trong đó giá trị của số đầu tiên được ghi và thay cho số đầu tiên, giá trị của số thứ hai được ghi. Nội dung từ biến tạm thời sau đó được ghi vào số thứ hai. Đây là một kỹ thuật tiêu chuẩn để hoán đổi hai phần tử;

  và cuối cùng là phương pháp chính:

• bubbleSorter– làm công việc chính và sắp xếp dữ liệu được lưu trữ trong mảng, chúng tôi sẽ trình bày lại một cách riêng biệt:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

Ở đây bạn nên chú ý đến hai bộ đếm: bên ngoài outvà bên trong in. Bộ đếm bên ngoàiout bắt đầu liệt kê các giá trị từ cuối mảng và giảm dần một giá trị với mỗi lần chuyển mới. outVới mỗi lần truyền mới, biến được dịch chuyển xa hơn về bên trái để không ảnh hưởng đến các giá trị đã được sắp xếp ở bên phải của mảng. Bộ đếm bên trongin bắt đầu liệt kê các giá trị từ đầu mảng và tăng dần từng giá trị trên mỗi lượt mới. Sự gia tăng inxảy ra cho đến khi đạt tới out(phần tử được phân tích cuối cùng trong lượt hiện tại). Vòng lặp bên trong inso sánh hai ô liền kề invà in+1. Nếu inmột số lớn hơn được lưu trữ trong hơn in+1, thì phương thức này được gọi toSwap, hoán đổi vị trí của hai số này.

Phần kết luận

Thuật toán sắp xếp bong bóng là một trong những thuật toán chậm nhất. Nếu mảng bao gồm N phần tử thì N-1 sẽ được thực hiện ở lần đầu tiên, N-2 ở lần thứ hai, sau đó là N-3, v.v. Tức là tổng số lần duyệt sẽ được thực hiện: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Như vậy, khi sắp xếp, thuật toán thực hiện so sánh khoảng 0,5x(N^2). Với N = 5, số lượng so sánh sẽ xấp xỉ 10, với N = 10, số lượng so sánh sẽ tăng lên 45. Do đó, khi số lượng phần tử tăng lên, độ phức tạp của việc sắp xếp tăng lên đáng kể: Tốc độ của thuật toán bị ảnh hưởng không chỉ bởi số lần vượt qua mà còn bởi số lượng hoán vị cần thực hiện. Đối với dữ liệu ngẫu nhiên, số lượng hoán vị trung bình (N^2)/4, bằng khoảng một nửa số lần vượt qua. Tuy nhiên, trong trường hợp xấu nhất, số lượng hoán vị cũng có thể là N^2/2 - trường hợp này xảy ra nếu dữ liệu ban đầu được sắp xếp theo thứ tự ngược lại. Mặc dù thực tế đây là một thuật toán sắp xếp khá chậm nhưng điều quan trọng là phải biết và hiểu cách thức hoạt động của nó và như đã đề cập trước đó, nó là cơ sở cho các thuật toán phức tạp hơn. Ôi trời!