Shell sort - Deft Blog

Mục lục

1 Minh hoạ
2 Implementation

Shell sort được xem là một thuật toán tổng quát của bubble sort hoặc insertion sort. Shell sort hoạt động bằng cách sắp xếp các phần tử nằm xa nhau, sau đó dần rút ngắn khoảng cách sắp xếp(gap), đều này giúp di chuyển các phần tử đi một khoảng cách xa có thể giúp các phần tử đi về vị trí chính xác của mình hiệu quả hơn so với việc di chuyển qua từng phần tử liền kề.

Thời gian chạy của shell sort phụ thuộc rất nhiều vào khoảng cách sắp xếp(gap) giữa hai phần tử, việc xác định thời gian chạy của shell sort hiện vẫn là một vấn đề mở, các bạn có thể tham khảo thêm tại wiki.

Ở bài viết này, mình sẽ chọn gap = n/2, n là số lượng phần tử của mảng, với gap = n/2 thì thời gian chạy của shell sort là θ(n²).

Minh hoạ

Khi GAP = 1, shell sort bây giờ cũng chính là insertion sort, tuy nhiên vì đã thực hiện insertion trên các đoạn con mà các phần tử cách xa nhau một đoạn GAP, nên ở lần insertion này ta sẽ giảm thiểu đáng kể số lần dịch chuyển phần tử.

Implementation

public static<T extends Comparable<T>> void sort(T[] arr, int n)
    {
        for (int gap = n / 2; gap > 0; gap /= 2)
        {
            for (int i = gap; i < n; i += 1)
            {
                T temp = arr[i];

                int j;
                /*
                 * use codition for arr[j - gap] with temp
                 * Sort by ASC => Compare ">"
                 * Sort by DESC => Compare "<"
                 */
                for (j = i; j >= gap && arr[j - gap].compareTo(temp) > 0; j -= gap)
                    arr[j] = arr[j - gap];

                arr[j] = temp;
            }
        }
    }

Link source code: Shell sort