Shell Sort Data Structure and Algorithm

#1 Shell Sort implement in Python

Code - Python Programming

def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
shell_sort(arr)
print("Sorted array:", arr)

This implementation uses the Shell Sort algorithm, which is an extension of the insertion sort algorithm. It sorts the elements by comparing and swapping elements that are distant from each other with a gap. The gap is reduced in each iteration until it becomes 1, at which point the algorithm behaves like an insertion sort.

#2 Shell Sort implement in Java

Code - Java Programming

public class ShellSort {

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("Original Array:");
        printArray(array);

        shellSort(array);

        System.out.println("\nSorted Array:");
        printArray(array);
    }

    // Function to perform Shell Sort on the given array
    public static void shellSort(int[] array) {
        int n = array.length;

        // Start with a large gap and reduce it until the gap becomes 1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Perform insertion sort for elements at each gap
            for (int i = gap; i  <  n; i++) {
                int temp = array[i];
                int j;

                // Shift the elements that are greater than temp to the right
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    array[j] = array[j - gap];
                }

                // Place temp (the original value) in its correct position
                array[j] = temp;
            }
        }
    }

    // Function to print an array
    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

#3 Shell Sort implement in C

Code - C Programming

#include <stdio.h>

// Function to perform shell sort
void shellSort(int arr[], int n) {
    // Start with a large gap and reduce it
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Do 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
            // position 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 position
            arr[j] = temp;
        }
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i  <  size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Array before sorting:\n");
    printArray(arr, n);

    shellSort(arr, n);

    printf("Array after sorting:\n");
    printArray(arr, n);

    return 0;
}

This is a basic example, and you can modify it according to your needs. The shellSort function is the implementation of the Shell Sort algorithm, and the printArray function is used to print the elements of the array.

#4 Shell Sort implement in C++

Code - C++ Programming

#include <iostream>
#include <vector>

void shellSort(std::vector<int>& arr) {
    int n = arr.size();

    // Start with a large gap and reduce it
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Do 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
            // position 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() {
    std::vector<int> arr = {12, 34, 54, 2, 3};
    
    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    shellSort(arr);

    std::cout << "\nSorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }

    return 0;
}

This C++ program defines a shellSort function that takes a vector of integers and sorts it using the Shell Sort algorithm. The main function demonstrates how to use this function with a sample array.