Sắp xếp chèn trong Java

Sắp xếp mảng là một trong những thao tác phổ biến nhất mà người mới bắt đầu sử dụng Java nên biết cách thực hiện. Mặc dù mảng không phải lúc nào cũng là cách thuận tiện nhất để sắp xếp dữ liệu và điều này chủ yếu áp dụng cho các số nhỏ, nhưng khái niệm đằng sau việc sắp xếp mảng có rất nhiều ứng dụng trong khoa học dữ liệu và phần mềm phức tạp. Trong bài đăng này, chúng ta sẽ xem xét kỹ hơn về sắp xếp chèn là gì. Chúng tôi đã bao gồm một số ví dụ và bài toán thực hành để giúp bạn hoàn toàn nắm bắt được khái niệm này.

Sắp xếp chèn là gì?

Về cơ bản, sắp xếp chèn là một thuật toán mà các nhà phát triển sử dụng để tổ chức các chuỗi số nhỏ. Nó chia tất cả các giá trị thành hai ngăn xếp - một ngăn xếp được sắp xếp và một ngăn xếp chưa được sắp xếp. Lần lượt, các số trong ngăn xếp “chưa sắp xếp” được chọn ra và sắp xếp theo đúng thứ tự. Chúng ta hãy xem xét kỹ hơn đầu vào và đầu ra của sắp xếp chèn:

• Đầu vào: một mảng A với các phần tử số chưa được sắp xếp: A[0,1, n, n-2...].
• Đầu ra: một mảng chứa các số giống nhau nhưng được sắp xếp đầy đủ. Cái này thường được gọi là B: B[0]B[1]...B[n-1].

Có một số cách để sử dụng sắp xếp chèn - đây là những cách phổ biến nhất:

• Sắp xếp theo số (thứ tự tăng dần): [1, 2, 3, 4, 5]
• Sắp xếp theo số (thứ tự giảm dần): [5, 4, 3, 2, 1]
• Sắp xếp theo thứ tự chữ cái: [a, b, c, d]

Lưu ý: nếu bạn có một mảng trống hoặc một singleton, chúng được coi là được sắp xếp theo mặc định.

Hiểu lý thuyết về sắp xếp chèn

Trước khi khám phá mã đằng sau sắp xếp chèn, hãy chia nhỏ thuật toán bằng cách sử dụng ngôn ngữ phi kỹ thuật. Bởi vì chúng tôi sẽ hiển thị mã để sắp xếp theo thứ tự tăng dần, nên việc giải thích thuật toán từng bước trong bài đăng này là điều hợp lý. Bước 1. Lặp lại giữa arr[1]và arr[n]ở đâu nlà một giá trị số thường nhỏ hơn 10. Bước 2. So sánh phần tử bạn đã chọn (được gọi là key) với số trước đó trong chuỗi bằng sort()phương pháp. Bước 3. Nếu tất cả các phần tử đều nhỏ hơn phần tử kế tiếp, hãy lặp lại phép so sánh cho đến khi bạn tìm thấy giá trị lớn hơn. Bước 4. Hoán đổi giá trị lớn hơn một vị trí so với giá trị nhỏ hơn để tạo một chuỗi có thứ tự. Bước 5. Lặp lại quy trình cho đến khi bạn nhận được chuỗi ký tự đã sắp xếp

Sắp xếp mảng nguyên thủy

Vì thuật toán là một trong những thao tác Java đơn giản nhất nên ngay cả những người mới bắt đầu hoàn chỉnh cũng không gặp nhiều khó khăn khi thực hiện nó. Dưới đây là hướng dẫn từng bước để sắp xếp một mảng

1. Khai báo một mảng để sắp xếp

Để bắt đầu, hãy tạo một chuỗi giá trị mà sau này chúng ta sẽ hiển thị bằng Java. Để sử dụng sắp xếp chèn, bạn cần tạo một mảng. Đối với điều đó, sử dụngint[]

int[] arrayA = {10, 14, 20, 30};

2. Sử dụng sort_arr để thực hiện thuật toán

Phương thức sort_arr là một trong những cách phổ biến nhất để triển khai sắp xếp chèn. Trong thực tế, nó trông như thế này:

for(int i=0; i< sort_arr.length; ++i){
        int j = i;

3. Tạo vòng lặp và trình vòng lặp

Bằng cách sử dụng một vòng lặp trong thuật toán sắp xếp chèn, các nhà phát triển không phải lặp lại logic cho mọi phần tử. Mặc dù việc tạo các vòng lặp có vẻ phức tạp, nhưng nó khá đơn giản - đây là một ví dụ:

for(int i=0; i< sort_arr.length; ++i){

Bây giờ bạn đã có một vòng lặp hoạt động, đã đến lúc tạo một trình vòng lặp sẽ sắp xếp tất cả các phần tử theo thứ tự mong muốn. Từ giờ trở đi, chúng ta sẽ gọi iterator là " j".

        int j = i;

4. Tạo "vòng lặp while"

Khi nói đến sắp xếp chèn, một vòng lặp "trong khi" là điều cần thiết cho một mảng mới được sắp xếp. Để thiết lập nó cho sắp xếp chèn theo thứ tự tăng dần, nhà phát triển cần tuân thủ hai điều kiện:

• Giá trị được gán cho j phải lớn hơn 0
• Giá trị được gán cho j-1cần phải lớn hơn jchỉ mục

Ngay khi cả hai điều kiện trong vòng lặp while đều đúng, giá trị khóa của mảng sẽ bằng chỉ jmục.

5. Sắp xếp mảng

Sau khi bạn thiết lập vòng lặp while, các giá trị jvà j-1sẽ được hoán đổi cho đến khi một hoặc cả hai điều kiện trong vòng lặp while không thành công. Tương tự, việc sắp xếp sẽ được lặp lại cho mọi giá trị trong vòng lặp for cho đến khi các điều kiện của vòng lặp for cũng không thành công. Đây là cách quá trình sắp xếp chèn hoạt động trong thực tế:

int key = sort_arr[j];
          sort_arr[j] = sort_arr[j-1];
          sort_arr[j-1] = key;
          j = j-1;

Sắp xếp một ArrayList

Mặc dù việc hiểu toán học đằng sau sắp xếp chèn là rất quan trọng, nhưng khi nói đến phát triển phần mềm thực tế, bạn sẽ sắp xếp ArrayLists nhiều hơn so với trình tự trong các mảng nguyên thủy. Dưới đây là hướng dẫn từng bước để sắp xếp một ArrayList:

1. Tạo một Elementlớp mới cho các mục thuộc bộ sưu tập.

   
   public class Element {
       private int id;
   
       public Element(int id) {
           this.id = id;
       }
   

2. Trong một bộ sưu tập, có một compareTo()phương thức - chúng tôi sẽ sử dụng phương thức này để so sánh id của hai phần tử.

   
       public int compareTo(Element element) {
           int res = 0;
           if (this.id < element.getId()) {
               res = -1;
           }
           if (this.id > element.getId()) {
               res = 1;
           }
           return res;
       }
   }
   

3. Áp dụng thuật toán và tạo một số vòng lặp để sắp xếp các đối tượng ArrayListthay vì so sánh chúng.

   
   public static void insertionSortArrayList(List<element> list) {
       for (int j = 1; j < list.size(); j++) {
           Element current = list.get(j);
           int i = j-1;
           while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
               list.set(i+1, list.get(i));
               i--;
           }
           list.set(i+1, current);
       }
   }
   

4. ArrayListBạn cũng có thể thêm nhiều yếu tố hơn vào , như được hiển thị bên dưới:

   
   List<element> list = new ArrayList<>();
   
   // Create elements w/ IDs 0-24
   for (int i = 0; i < 25; i++) {
       list.add(new Element(i));
   }
   
   // To use insertion sort, shuffle the values
   Collections.shuffle(list);
   

5. Bây giờ là lúc để sắp xếp:

   
   // This helps print values before sorting
   list.forEach(e -> System.out.print(e.getId() + ", "));
   
   // Sort the list
   insertionSortArrayList(list);
   
   System.out.println();
   
   // Display a sorted array 
   list.forEach(e -> System.out.print(e.getId() + ", "));
   

6. Bây giờ hãy so sánh đầu vào và đầu ra để đảm bảo chúng tôi không mắc lỗi nào. Đây là so sánh của chuỗi chúng tôi đã sử dụng làm ví dụ.

   
   4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
   

Bài tập thực hành sắp xếp chèn

Bây giờ bạn đã hiểu rõ về thuật toán sắp xếp này, đã đến lúc kiểm tra các kỹ năng lý thuyết và thực hành của bạn. Bài kiểm tra lý thuyết số 1 Bạn được cho một mảng [1, 4, 6, 8] và đang thêm một phần tử mới n = 7 vào mảng đó. Bạn cần thực hiện bao nhiêu phép so sánh để có được một dãy số đã sắp xếp? Cho biết giá trị cuối cùng của chỉ số n trong mảng. Bài kiểm tra lý thuyết số 2 Tại một cuộc phỏng vấn xin việc, trưởng nhóm yêu cầu bạn chứng minh rằng chèn sắp xếp là một phương pháp không hiệu quả. Cho trước một chuỗi số [0, 3, 6, 8, 9], thứ tự của chuỗi đầu vào của bạn sẽ là bao nhiêu để tối đa hóa thời gian chạy cần thiết để sắp xếp? Bài tập thực hành Sắp xếp mảng [0, 1, 4, 5, 2, 3, 7, 9, 8] theo thứ tự tăng dần bằng cách sử dụng sắp xếp chèn cho Java.

Phần kết luận

Thách thức lớn nhất trong việc nắm bắt sắp xếp chèn là hiểu quy trình hoạt động như thế nào. Khi bạn đã hiểu rõ về nó, việc biến mẫu thành mã là một miếng bánh. Miễn là bạn thực hành và xem lại các vấn đề thực hành có liên quan theo thời gian, bạn sẽ nhanh chóng cải thiện tốc độ sắp xếp chèn của mình.