Algorithm

Shell Sort is a sorting algorithm that belongs to the insertion sort family. It was proposed by Donald Shell in 1959. The basic idea behind Shell Sort is to exchange items that are far apart. The algorithm works by sorting sublists of a given interval, gradually reducing the interval between elements to be compared and swapped, until the entire list is sorted.

Here is a simplified description of the Shell Sort algorithm:

1. Gap Sequence: Choose a sequence of gap values, often referred to as the "gap sequence." The choice of gap sequence affects the efficiency of the algorithm.

2. Sorting Sublists: Start with the largest gap and use the insertion sort algorithm to sort the elements in each sublist defined by the current gap.

3. Reduce the Gap: Reduce the gap and repeat the sorting process until the gap becomes 1.

4. Final Pass: When the gap becomes 1, perform a final pass using the regular insertion sort algorithm to ensure that the entire list is sorted.

The idea is that by initially sorting the sublists with a large gap, the algorithm can quickly eliminate some of the disorder in the list, making the subsequent passes more efficient.

Code Examples

#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)
``````

Copy The Code &

#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();
}
}
``````
Copy The Code &

#3 Shell Sort implement in C

```Code - C Programming```

``````#include <stdio.h>

// Function to perform shell sort
void shellSort(int arr[], int n) {
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;
}
``````

Copy The Code &

#4 Shell Sort implement in C++

```Code - C++ Programming```

``````#include <iostream>
#include <vector>

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

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;
}
``````

Copy The Code &