Lập trình Java - Sắp xếp Shell Sort

Sắp xếp Shell Sort trong Java

Đề bài: Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán Shell Sort.


Lời giải

Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so với phần tử lớn hơn bên trái).

Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval): là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào công thức Knuth như sau:

h = h * 3 + 1

Trong đó:

h là khoảng (interval) với giá trị ban đâu là 1

Dưới đây là chương trình Java để giải bài sắp xếp Shell Sort trong Java:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author ADMIN
 */
public class ShellSort {

    /**
     * @param args the command line arguments
     */
     // ham sap xep
    public void shellSort(int arr[]) {
        int inner, outer;
        int valueToInsert;
        int interval = 1;
        int elements = arr.length;
        int i = 0;
 
        while (interval <= elements / 3) {
            interval = interval * 3 + 1;
        }
 
        while (interval > 0) {
            for (outer = interval; outer < elements; outer++) {
                valueToInsert = arr[outer];
                inner = outer;
 
                while (inner > interval - 1 && arr[inner - interval] >= valueToInsert) {
                    arr[inner] = arr[inner - interval];
                    inner -= interval;
                    System.out.println(" Di chuyen phan tu: " + arr[inner]);
                }
 
                arr[inner] = valueToInsert;
                System.out.println(" Chen phan tu: " + valueToInsert 
                        + ", tai vi tri: " + inner);
            }
 
            interval = (interval - 1) / 3;
            i++;
 
            System.out.print("Vong lap thu " + i + ": ");
            display(arr);
        }
    }
 
    public void display(int arr[]) {
        int i;
        System.out.print("[");
 
        // Duyet qua tat ca phan tu
        for (i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
 
        System.out.print("]\n");
    }
 
    public static void main(String[] args) {
        // TODO code application logic here
        // khoi tao mang arr
        int arr[] = { 6, 7, 0, 2, 8, 1, 3, 9, 4, 5 };
 
        ShellSort shellSort = new ShellSort();
        System.out.println("Mang du lieu dau vao: ");
        shellSort.display(arr);
        System.out.println("-----------------------------");
        shellSort.shellSort(arr);
        System.out.println("-----------------------------");
        System.out.println("\nMang sau khi da sap xep: ");
        shellSort.display(arr);
    }
    
}

Chạy chương trình Java trên cho kết quả như sau: