Home Data Structures and Algorithms with Java Shell Sort in Java

Lesson 33 of 48

In Progress

← Previous Next→

Shell Sort in Java

Yasin Cakal

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:
}

Data Structures and Algorithms with Java

Participants 433