Shell Sort

Code

C language code:

#include <stdio.h>

void shell_sort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {  // Initial gap is n/2, halved each time
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    shell_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Code Explanation

1. Initialization: The array arr is the array to be sorted, and n is the length of the array.
2. Gap control: Uses a for loop to control the gap, starting from n/2, halved each time until the gap is 1.
3. Main sorting loop:
   • Traverses the array starting from the current gap position.
   • Stores the current element in temp.
   • Uses the inner for loop to perform insertion sort with the current gap; if the preceding element is greater than temp, shifts it one position backward until the correct position for inserting temp is found.
4. Result output: After sorting is complete, the sorted array is printed.

Example Run

Assuming the input array is {12, 34, 54, 2, 3}:

1. Initial state: {12, 34, 54, 2, 3}
2. First gap of 2:
   • Insert 54 and 2: {12, 2, 54, 34, 3}
   • Insert 34 and 3: {12, 2, 3, 34, 54}
3. Second gap of 1:
   • Insertion sort: {2, 3, 12, 34, 54}

Final result: {2, 3, 12, 34, 54}

Time Complexity Analysis

The time complexity of shell sort depends on the choice of gap sequence. Common gap sequences include the Knuth sequence, Hibbard sequence, etc. In general, the time complexity is difficult to analyze precisely, but the following conclusions exist:

• Best-case time complexity: When using the optimal gap sequence, shell sort can achieve a time complexity of $O(n \log^2 n)$.
• Worst-case time complexity: In the worst case, the time complexity is $O(n^2)$, which depends on the choice of gap sequence.
• Average time complexity: Typically, the average time complexity of shell sort is better than insertion sort, approximately between $O(n \log n)$ and $O(n \log^2 n)$.

Space Complexity Analysis

Shell sort is an in-place sorting algorithm that requires no additional auxiliary space, so the space complexity is $O(1)$. In this implementation, we only use a few extra variables (gap, i, temp, j), so the space complexity remains at a constant level.

Advantages and Disadvantages

Advantages:

• Simple and easy to implement.
• More efficient than insertion sort, especially for large-scale data.
• In-place sorting; low space complexity.
• Good performance for most practical applications.

Disadvantages:

• Worst-case time complexity may still be relatively high.
• Unstable sorting algorithm; may change the relative order of equal elements.

Applicable Scenarios

Shell sort is suitable for the following scenarios:

• Sorting large datasets.
• When a more efficient sorting algorithm than insertion sort is needed.
• Scenarios where stability is not a high priority.

Summary

Shell sort is an efficient improvement on insertion sort that uses gap sequences to reduce the number of element movements, thereby improving sorting efficiency. Although its worst-case time complexity may still be relatively high, in most practical applications, shell sort outperforms insertion sort, especially for large-scale data.