Sorting

Shell sort

Pinterest LinkedIn Tumblr

Shell sort is a sorting algorithm that starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Shell sort is a variation of insertion sort. Shell sort is a generalization of insertion sort.

Write a program to implement the shell sort.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class Shellsort {
 
     public static void sort( int[] a)  {
         int increment = a.length / 2;
            while (increment > 0) {
                for (int i = increment; i < a.length; i++) {
                    int j = i;
                    int temp = a[i];
                    while (j >= increment && a[j - increment] > temp) {
                        a[j] = a[j - increment];
                        j = j - increment;
                    }
                    a[j] = temp;
                }
                if (increment == 2) {
                    increment = 1;
                } else {
                    increment *= (5.0 / 11);
                }
            }
     }
    public static void main(String[] args) {
          int arr[] = {12, 11, 13, 5, 6, 7};
          System.out.println("unsorted array before sorting : " + Arrays.toString(arr));
         sort(arr);
          System.out.println("Sorted array After Shellsort sorting : " + Arrays.toString(arr));
 
    }
 
}

Output

Unsorted array before sorting: [12, 11, 13, 5, 6, 7]
Sorted array After Shell sort sorting: [5, 6, 7, 11, 12, 13]

Algorithm Explanation

Starts by comparing elements far apart, then elements less far apart
Compare adjacent elements
Return sorted items and print the values.

Time Complexity

Best CaseAverage CaseWorst Case
O(n log2 n)O(n^2)

Reference

  1. http://www.stoimen.com/blog/2012/02/27/computer-algorithms-shell-sort/
  2. https://en.wikipedia.org/wiki/Shellsort

Write A Comment