Given an array arr[] of N integers, the task is to sort the array using Shell-Metzner sort.
Input: arr[] = {0, -2, 8, 5, 1}
Output: -2 0 1 5 8
Input: arr[] = {4, 5, 6, 1, 100000, 1000}
Output: 1 4 5 6 1000 100000
Prerequisite: Shell Sort
The Shell-Metzner sort is an adaptation of the Shell sort by Marlene Metzner. The Shell-Metzner Sort uses five indices to check which cells to swap. The Metzner version starts with a step size equal to half the length of the array, with each pass increasing the number of comparisons quadratically.
Below is the implementation of Shell-Metzner sort:
C++
// C++ implementation of Shell-Metzner Sort#include <bits/stdc++.h>using namespace std;// Function to swap two elementsvoid swap(int& a, int& b){ int temp = a; a = b; b = temp;}// Function to sort arr[] using Shell Metzner sortvoid sort_shell_metzner(int arr[], int n){ // Declare variables int i, j, k, l, m, temp; // Set initial step size to // the size of the array m = n; while (m > 0) { // Step size decreases by half each time m /= 2; // k is the upper limit for j k = n - m; // j is the starting point j = 0; do { // i equals to smaller value i = j; do { // l equals to larger value l = i + m; // Compare and swap arr[i] with arr[l] if (arr[i] > arr[l]) { swap(arr[i], arr[l]); // Decrease smaller value by step size i -= m; } else break; } while (i >= 0); // Increment the lower limit of i j++; } while (j <= k); }}// Function to print the contents of an arrayvoid printArray(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Driver codeint main(){ int arr[] = { 0, -2, 8, 5, 1 }; int n = sizeof(arr) / sizeof(arr[0]); // Sort the array using Shell Metzner Sort sort_shell_metzner(arr, n); // Print the sorted array printArray(arr, n); return 0;} |
Java
// Java implementation of Shell-Metzner Sort class GFG { // Function to swap two elements static int[] swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Function to sort arr[] using Shell Metzner sort static void sort_shell_metzner(int arr[], int n) { // Declare variables int i, j, k, l, m, temp; // Set initial step size to // the size of the array m = n; while (m > 0) { // Step size decreases by half each time m /= 2; // k is the upper limit for j k = n - m; // j is the starting point j = 0; do { // i equals to smaller value i = j; do { // l equals to larger value l = i + m; // Compare and swap arr[i] with arr[l] if (l < n && arr[i] > arr[l]) { swap(arr, i, l); // Decrease smaller value by step size i -= m; } else { break; } } while (i >= 0); // Increment the lower limit of i j++; } while (j <= k); } } // Function to print the contents of an array static void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int arr[] = {0, -2, 8, 5, 1}; int n = arr.length; // Sort the array using Shell Metzner Sort sort_shell_metzner(arr, n); // Print the sorted array printArray(arr, n); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of Shell-Metzner Sort# Function to sort arr[] using Shell Metzner sortdef sort_shell_metzner( arr, n): # Set initial step size to # the size of the array m = n; while (m > 0): # Step size decreases by half each time m //= 2 # k is the upper limit for j k = n - m # j is the starting point j = 0 while(j < k): # i equals to smaller value i = j while(i >= 0): # l equals to larger value l = i + m # Compare and swap arr[i] with arr[l] if (arr[i] > arr[l]): arr[i], arr[l]=arr[l],arr[i] # Decrease smaller value by step size i -= m else: break # Increment the lower limit of i j += 1# Function to print the contents of an arraydef printArray(arr, n): for i in range( n): print( arr[i], end= " ")# Driver codeif __name__ =="__main__": arr = [ 0, -2, 8, 5, 1 ] n = len(arr) # Sort the array using Shell Metzner Sort sort_shell_metzner(arr, n) # Print the sorted array printArray(arr, n)# This code is contributed by chitranayal |
C#
// C# implementation of Shell-Metzner Sortusing System; class GFG { // Function to swap two elements static int[] swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Function to sort arr[] using Shell Metzner sort static void sort_shell_metzner(int []arr, int n) { // Declare variables int i, j, k, l, m, temp; // Set initial step size to // the size of the array m = n; while (m > 0) { // Step size decreases by half each time m /= 2; // k is the upper limit for j k = n - m; // j is the starting point j = 0; do { // i equals to smaller value i = j; do { // l equals to larger value l = i + m; // Compare and swap arr[i] with arr[l] if (l < n && arr[i] > arr[l]) { swap(arr, i, l); // Decrease smaller value by step size i -= m; } else { break; } } while (i >= 0); // Increment the lower limit of i j++; } while (j <= k); } } // Function to print the contents of an array static void printArray(int []arr, int n) { for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } } // Driver code public static void Main(String[] args) { int []arr = {0, -2, 8, 5, 1}; int n = arr.Length; // Sort the array using Shell Metzner Sort sort_shell_metzner(arr, n); // Print the sorted array printArray(arr, n); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of Shell-Metzner Sort // Function to swap two elements function swap(arr,i,j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } // Function to sort arr[] using Shell Metzner sort function sort_shell_metzner(arr,n) { // Declare variables let i, j, k, l, m, temp; // Set initial step size to // the size of the array m = n; while (m > 0) { // Step size decreases by half each time m = Math.floor(m/2); // k is the upper limit for j k = n - m; // j is the starting point j = 0; do { // i equals to smaller value i = j; do { // l equals to larger value l = i + m; // Compare and swap arr[i] with arr[l] if (l < n && arr[i] > arr[l]) { swap(arr, i, l); // Decrease smaller value by step size i -= m; } else { break; } } while (i >= 0); // Increment the lower limit of i j++; } while (j <= k); } } // Function to print the contents of an array function printArray(arr,n) { for (let i = 0; i < n; i++) { document.write(arr[i] + " "); } } // Driver code let arr=[0, -2, 8, 5, 1]; let n = arr.length; // Sort the array using Shell Metzner Sort sort_shell_metzner(arr, n); // Print the sorted array printArray(arr, n);// This code is contributed by avanitrachhadiya2155</script> |
PHP
<?php// php implementation of Shell-Metzner Sort // Function to sort arr[] using Shell Metzner sort function sort_shell_metzner($arr, $n) { // Set initial step size to // the size of the array $m = $n; while ($m > 0) { // Step size decreases by half each time $m = $m / 2; // k is the upper limit for j $k = $n - $m; // j is the starting point $j = 0; do { // i equals to smaller value $i = $j; do { // l equals to larger value $l = $i + $m; // Compare and swap arr[i] with arr[l] if ($arr[$i] > $arr[$l]) { $temp = $arr[$i]; $arr[$i] = $arr[$l]; $arr[$l] = $temp; // Decrease smaller value by step size $i -= $m; } else break; } while ($i >= 0); // Increment the lower limit of i $j++; } while ($j <= $k); } return $arr ;} // Function to print the contents of an array function printArray($arr, $n) { for ($i = 0; $i < $n; $i++) echo $arr[$i], " "; } // Driver code $arr = array( 0, -2, 8, 5, 1 ); $n = count($arr); // Sort the array using Shell Metzner Sort $result_array = sort_shell_metzner($arr, $n); // Print the sorted array printArray($result_array, $n); // This code is contributed by Ryuga?> |
Output
-2 0 1 5 8
Time Complexity: O(n2)
Space Complexity: O(1) as no extra space has been used.
Another Approach: Using a loop to repeatedly reduce the gap value until it reaches 1.
- For each gap value, we perform an insertion sort on subarrays of the original array, using the gap value as the increment for the inner loop.
- In this implementation, we use five indices (‘i’,’j’, ‘k’, ‘l’, and ‘m’) to compare and swap elements within the subarray.
- ‘i’ is the current index being inserted, and ‘j’,’ k’, ‘l’, and ‘m’ are the indices that are ‘gap’ positions behind ‘i’.
- The while loop compares arr[i] to arr[j] and swaps them if necessary.
- Then, we update the indices to move ‘i and the other indices back by gap, and repeat the process until ‘j’ is out of bounds or arr[i] is in the correct position.
Below is the implementation:
C++
#include <iostream>#include <vector>using namespace std;vector<int> shell_sort(vector<int>& arr) { int n = arr.size(); int gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { int j = i - gap; int k = j - gap; int l = k - gap; int m = l - gap; while (j >= 0 && arr[i] < arr[j]) { swap(arr[i], arr[j]); i = j; j = k; k = l; l = m; m = (m - gap >= 0) ? m - gap : -1; } } gap /= 2; } return arr;}int main() { int arr[] = { 0, -2, 8, 5, 1 }; vector<int> vec(arr, arr + sizeof(arr) / sizeof(int)); vector<int> sorted_arr = shell_sort(vec); for (int x : sorted_arr) { cout << x << " "; } cout << endl; return 0;}// This code is contributed by user_dtewbxkn77n |
Java
import java.util.Arrays;public class ShellSort { public static int[] shellSort(int[] arr) { int n = arr.length; int gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { int j = i - gap; int k = j - gap; int l = k - gap; int m = l - gap; while (j >= 0 && arr[i] < arr[j]) { // Swap elements arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i = j; j = k; k = l; l = m; m = (m - gap >= 0) ? m - gap : -1; } } gap /= 2; } return arr; } public static void main(String[] args) { int[] arr = { 0, -2, 8, 5, 1 }; int[] sortedArr = shellSort(arr); System.out.println("Sorted Array:"); for (int x : sortedArr) { System.out.print(x + " "); } System.out.println(); }} |
Python
# Function to perform shell sortdef shell_sort(arr): n = len(arr) gap = n // 2 # Initialize the gap as half of the array length while gap > 0: # Continue until the gap is greater than zero for i in range(gap, n): j = i while j >= gap and arr[j - gap] > arr[j]: # Compare elements at intervals of 'gap' and swap if needed arr[j], arr[j - gap] = arr[j - gap], arr[j] j -= gap gap //= 2 # Reduce the gap return arrif __name__ == "__main__": arr = [0, -2, 8, 5, 1] sorted_arr = shell_sort(arr) # Display the sorted array for x in sorted_arr: print(x), # Use a comma at the end to avoid the newline print() # Move to the next line for clean output |
C#
using System;using System.Collections.Generic;public class Program{ // Function to perform Shell Sort on a list of integers public static List<int> ShellSort(List<int> arr) { int n = arr.Count; int gap = n / 2; // Reduce the gap in each iteration until it becomes 1 while (gap > 0) { // Perform insertion sort with the current gap value for (int i = gap; i < n; i++) { int j = i - gap; int k = j - gap; int l = k - gap; int m = l - gap; // Compare and swap elements with the gap distance // until the current element is in its correct position while (j >= 0 && arr[i] < arr[j]) { // Swap elements at index i and j int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // Update indices for the next iteration i = j; j = k; k = l; l = m; m = (m - gap >= 0) ? m - gap : -1; } } // Reduce the gap for the next iteration gap /= 2; } // Return the sorted list return arr; } public static void Main(string[] args) { int[] arr = { 0, -2, 8, 5, 1 }; List<int> vec = new List<int>(arr); // Call the ShellSort function to sort the list List<int> sorted_arr = ShellSort(vec); // Print the sorted list foreach (int x in sorted_arr) { Console.Write(x + " "); } Console.WriteLine(); }} |
Javascript
// Function to perform Shell Sort on an array of integersfunction shellSort(arr) { const n = arr.length; let gap = Math.floor(n / 2); // Reduce the gap in each iteration until it becomes 0 while (gap > 0) { // Perform insertion sort with the current gap value for (let i = gap; i < n; i++) { let j = i - gap; let k = j - gap; let l = k - gap; let m = l - gap; // Compare and swap elements with the gap distance // until the current element is in its correct position while (j >= 0 && arr[i] < arr[j]) { // Swap elements at index i and j using array destructuring [arr[i], arr[j]] = [arr[j], arr[i]]; // Update indices for the next iteration i = j; j = k; k = l; l = m; m = (m - gap >= 0) ? m - gap : -1; } } // Reduce the gap for the next iteration gap = Math.floor(gap / 2); } // Return the sorted array return arr;}// Main functionfunction main() { // Given input array const arr = [0, -2, 8, 5, 1]; // Call the shellSort function to sort the array const sortedArr = shellSort(arr); // Print the sorted array console.log(sortedArr.join(' '));}// Call the main function to start the sorting processmain(); |
Output
-2 0 1 5 8
Time Complexity: O(n2)
Auxiliary Space: O(1)
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!
