C Program to Implement Shell Sort

Introduction

Shell Sort is an in-place comparison-based sorting algorithm that generalizes insertion sort to allow the exchange of items that are far apart. The algorithm first sorts elements that are far apart and then progressively reduces the gap between elements to be compared. By sorting elements that are further apart, Shell Sort can move elements closer to their correct positions more quickly, improving efficiency over standard insertion sort.

Example:

• Input: Unsorted array [12, 34, 54, 2, 3]
• Output: Sorted array [2, 3, 12, 34, 54]

Problem Statement

Create a C program that:

• Implements the Shell Sort algorithm to sort an array.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Shell Sort Function: This function will sort the array using the Shell Sort algorithm.
3. Create a Main Function: Allow the user to input the array, apply Shell Sort, and display the sorted array.

C Program to Implement Shell Sort

#include <stdio.h>

// Function to implement Shell Sort
void shellSort(int arr[], int n) {
    // Start with a big gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Perform a gapped insertion sort for this gap size.
        // The first gap elements arr[0..gap-1] are already in gapped order
        // Keep adding one more element until the entire array is gap sorted
        for (int i = gap; i < n; i++) {
            // Add arr[i] to the elements that have been gap sorted
            // Save arr[i] in temp and make a hole at position i
            int temp = arr[i];

            // Shift earlier gap-sorted elements up until the correct location for arr[i] is found
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }

            // Put temp (the original arr[i]) in its correct location
            arr[j] = temp;
        }
    }
}

int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Apply Shell Sort
    shellSort(arr, n);

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

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Implement Shell Sort

• The shellSort function starts by choosing a large gap, typically half the size of the array, and progressively reduces the gap until it becomes 1.
• For each gap size, the algorithm performs a "gapped" insertion sort, where elements that are gap positions apart are compared and swapped if needed.
• The process continues until the entire array is sorted.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Shell Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 5
Enter 5 elements:
12 34 54 2 3
Sorted array: 2 3 12 34 54

Example Output (Reversed Array):

Enter the number of elements in the array: 5
Enter 5 elements:
5 4 3 2 1
Sorted array: 1 2 3 4 5

Conclusion

This C program demonstrates how to implement Shell Sort, an efficient sorting algorithm that generalizes insertion sort to allow the comparison and exchange of items that are far apart. Shell Sort is particularly useful for sorting medium-sized arrays, and it is simple to implement. The program provides a clear example of how Shell Sort can be applied to sort an array in C programming.