Direct Insertion Sort

Direct Insertion Sort is one of the simplest sorting algorithms, conceptually similar to the way one organizes playing cards. The fundamental idea is to iterate through the dataset and insert each element into its correct position within a previously sorted sub-array.

Algorithm Logic

Assume the first element is already sorted. When processing the i-th element (where i > 0), compare it with the elements in the sorted sequence (indices 0 to i-1) from right to left. If the element at position i is smaller than the element in the sorted sequence, shift that sorted element to the right. This process continues until the correct position for the i-th element is found, at which point it is inserted.

Performance Characteristics

• Time Complexity: O(N²) in the worst case (reverse order). The best case is O(N) (already sorted).
• Space Complexity: O(1), as it operates in-place.
• Stability: Its a stable sorting algorithm, meaning the relative order of equal elements is preserved.

Code Implementation

The implementation separates the logic into two parts: handling a single pass (inserting one element) and wrapping it in a loop to handle the entire array.

void insertionSort(int arr[], int size) {
    // Iterate over the array starting from the second element
    for (int i = 1; i < size; ++i) {
        int key = arr[i]; // The value to be inserted
        int prev_index = i - 1; // Start comparing with the previous element

        // Shift elements of the sorted segment that are greater than the key
        // to one position ahead of their current position
        while (prev_index >= 0 && arr[prev_index] > key) {
            arr[prev_index + 1] = arr[prev_index];
            prev_index--;
        }
        
        // Insert the key into its correct position
        arr[prev_index + 1] = key;
    }
}

Shell Sort (Diminishing Increment Sort)

Shell Sort, also known as Diminishing Increment Sort, is an optimization of the Direct Insertion Sort. It addresses the inefficiency of Insertion Sort when dealing with large, unsorted datasets where small elements at the end of the array require many shifts to reach the beginning.

Algorithm Logic

The core concept is to group elements separated by a specific "gap" distance. Instead of comparing adjacent elements, we compare elements that are 'gap' units apart.

1. Pre-sorting: Select an initial gap (usually size/2). Sort elements within these sub-arrays. This moves elements quick towards their general destination regions.
2. Reducing Gap: Gradually reduce the gap (e.g., gap = gap / 2) and repeat the sorting process.
3. Final Pass: When the gap becomes 1, the algorithm performs a standard Insertion Sort. However, because the array is now "nearly sorted" due to the pre-sorting steps, this final pass is highly efficient.

Performance Characteristics

• Optimization: It optimizes Insertion Sort by allowing long-distance swaps early on.
• Time Complexity: The exact complexity depends on the gap sequence strategy used. A rough average estimate is O(N^1.3).
• Stability: It is an unstable sorting algorithm because elements jump over each other during the pre-sorting phases.

Code Implementation

The code below uses a gap sequence that halves the gap in each iteration. The inner logic mirrors Insertion Sort, but with a step size of gap instead of 1.

void shellSort(int arr[], int size) {
    int gap = size;
    
    // Continue until gap is reduced to 1
    while (gap > 1) {
        // Define the gap for the next pass
        gap = gap / 2; 
        
        // Perform a gapped insertion sort for this gap size
        for (int i = 0; i < size - gap; ++i) {
            int current_val = arr[i + gap];
            int j = i;
            
            // Compare elements separated by 'gap' and shift if necessary
            while (j >= 0) {
                if (current_val < arr[j]) {
                    arr[j + gap] = arr[j];
                    j -= gap;
                } else {
                    break;
                }
            }
            
            // Place the value in its correct location within the sub-array
            arr[j + gap] = current_val;
        }
    }
}

Detailed Operation Breakdown

Shell sort proceeds in two phases: pre-sorting with gaps larger than 1, and the final insertion sort with a gap of 1.

In the pre-sorting phase:

• A larger gap ensures that very small numbers near the end of the array move to the front quickly, and large numbers at the front move to the back.
• This creates an array that is "roughly" ordered, significantly reducing the number of shifts required in the final step.

As the gap decreases, the sorting behavior becomes finer. When gap == 1, the logic is identical to Direct Insertion Sort, operating on a dataset that is much easier to sort than the original.