Shell Sort is an algorithm used to sort elements in an array. It is a type of insertion sort, which works by comparing elements in the array and then moving them around until they are properly sorted. Shell Sort was developed by Donald Shell in 1959. It is a fast and efficient sorting algorithm that works in-place, so it does not require additional memory for its operations.
What is Shell Sort?
Shell Sort is an algorithm used to sort elements in an array. It is a type of insertion sort, which works by comparing elements in the array and then moving them around until they are properly sorted. It is an in-place sorting algorithm, meaning that it does not require additional memory for its operations. Shell Sort is based on the idea of insertion sort, but it is more efficient because it uses a “gap” between elements to make comparisons and moves.
How Does Shell Sort Work?
Shell Sort works by comparing elements in the array and then moving them around until they are properly sorted. It begins by comparing elements that are a specific “gap” apart, and then gradually decreasing the gap until it is 1. This process is repeated until the array is completely sorted.
The algorithm works by sorting elements that are a specific “gap” apart and then gradually decreasing the gap until it is 1. This process is repeated until the array is completely sorted. The gap is important because it allows for comparisons and moves to be made more efficiently. By comparing elements that are further apart, it is possible to make more efficient moves and comparisons.
Shell Sort Pseudocode
The following pseudocode describes the process of Shell Sort:
// function to sort array using 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) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[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 += 1) {
// add a[i] to the elements that have been gap sorted
// save a[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 a[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 a[i]) in its correct location
arr[j] = temp;
}
}
}
Java Code for Shell Sort
Now let’s look at the Java code for Shell Sort:
public class ShellSort {
// Function to sort an array using shell sort
public static void sort(int[] arr)
{
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[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 += 1) {
// add a[i] to the elements that have been gap
// sorted save a[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 a[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 a[i]) in its correct
// location
arr[j] = temp;
}
}
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 34, 54, 2, 3 };
sort(arr);
System.out.println("Array after sorting:");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
Time Complexity
Shell Sort has an average time complexity of O(n2). This means that the time it takes to sort an array increases exponentially as the size of the array increases. The worst case time complexity of Shell Sort is also O(n2).
Space Complexity
The space complexity of Shell Sort is O(1). This means that the algorithm does not require additional memory for its operations.
Conclusion
In conclusion, Shell Sort is a fast and efficient sorting algorithm that works in-place, so it does not require additional memory for its operations. It is based on the idea of insertion sort, but it is more efficient because it uses a “gap” between elements to make comparisons and moves. The average time complexity of Shell Sort is O(n2) and the worst case time complexity is also O(n2). The space complexity of Shell Sort is O(1).
Exercises
Write a Java program to sort an array using Shell Sort.
public class ShellSort {
// Function to sort an array using shell sort
public static void sort(int[] arr)
{
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[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 += 1) {
// add a[i] to the elements that have been gap
// sorted save a[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 a[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 a[i]) in its correct
// location
arr[j] = temp;
}
}
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 34, 54, 2, 3 };
sort(arr);
System.out.println("Array after sorting:");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
Write a Java program to compare the time complexity of Shell Sort and Insertion Sort.
public class CompareSort {
// Function to sort an array using shell sort
public static void shellSort(int[] arr)
{
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[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 += 1) {
// add a[i] to the elements that have been gap
// sorted save a[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 a[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 a[i]) in its correct
// location
arr[j] = temp;
}
}
}
// Function to sort an array using insertion sort
public static void insertionSort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 34, 54, 2, 3 };
shellSort(arr);
System.out.println("Shell Sort Array:");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
int arr2[] = { 12, 34, 54, 2, 3 };
insertionSort(arr2);
System.out.println("Insertion Sort Array:");
for (int i = 0; i < arr2.length; i++)
System.out.print(arr2[i] + " ");
}
}
Write a Java program to calculate the space complexity of Shell Sort.
public class SpaceComplexity {
// Function to calculate the space complexity
// of Shell Sort
public static void spaceComplexity(int arr[])
{
int n = arr.length;
// Space complexity is O(1).
// This means that the algorithm
// does not require additional memory
// for its operations.
System.out.println("Space Complexity of Shell Sort is O(1).");
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 34, 54, 2, 3 };
spaceComplexity(arr);
}
}
Write a Java program to compare the time complexity of Shell Sort and Quick Sort.
public class CompareSort {
// Function to sort an array using shell sort
public static void shellSort(int[] arr)
{
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[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 += 1) {
// add a[i] to the elements that have been gap
// sorted save a[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 a[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 a[i]) in its correct
// location
arr[j] = temp;
}
}
}
// Function to sort an array using quick sort
public static void quickSort(int arr[], int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
public static int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 34, 54, 2, 3 };
shellSort(arr);
System.out.println("Shell Sort Array:");
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
int arr2[] = { 12, 34, 54, 2, 3 };
quickSort(arr2, 0, arr2.length - 1);
System.out.println("Quick Sort Array:");
for (int i = 0; i < arr2.length; i++)
System.out.print(arr2[i] + " ");
}
}
Write a Java program to calculate the average time complexity of Shell Sort.
public class TimeComplexity {
// Function to calculate the average time complexity
// of Shell Sort
public static void timeComplexity(int arr[])
{
int n = arr.length;
// Average time complexity of Shell Sort is O(n2).
System.out.println("Average Time Complexity of Shell Sort is O(n2).");
}
// Your Driver method goes here:
}