In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.
Java
// Java implementation of ShellSort class ShellSort { /* An utility function to print array of size n*/ static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } /* function to sort arr using shellSort */ int 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; } } return 0; } // Driver method public static void main(String args[]) { int arr[] = { 12, 34, 54, 2, 3 }; System.out.println("Array before sorting"); printArray(arr); ShellSort ob = new ShellSort(); ob.sort(arr); System.out.println("Array after sorting"); printArray(arr); } } /*This code is contributed by Rajat Mishra */ |
Output:
Array before sorting 12 34 54 2 3 Array after sorting 2 3 12 34 54
Time Complexity: O(n2)
Auxiliary Space: O(1)
Please refer complete article on ShellSort for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
