Shell Metzner sort

Table of contents:

1. What is Shell-Metzner sort?
2. Implementing the solution
3. Time and Space Complexity
4. Another Approach

What is Shell-Metzner sort?

Prerequisite:

The Shell-Metzner sort is a modified version of a sorting method called Shell sort. It was developed by Marlene Metzner to make it work even better.

Let's understand it in more simple way:

Imagine you have a list of things that you want to arrange in order. The Shell-Metzner sort does this using a specific process. Instead of looking at one item at a time, it uses five different points to decide which items to move around.

At the beginning, the Shell-Metzner sort starts by looking at pairs of items that are far apart from each other (the distance is half the total number of items). Then, in each step, it compares and arranges the items that are that far apart. As it goes through these steps, the number of comparisons it makes increases in a specific way that helps to arrange the items more efficiently.

So, in simple words, the Shell-Metzner sort is like a clever way of organizing things. It uses five special points to decide how to move items around in a certain order. And with each step, it compares and arranges the items in a smart way to get everything in order.

Implementing the solution

We will be implementing solution using C++

#include <bits/stdc++.h>
using namespace std;

void shellMetznerSort(vector<int>& vec)
{
    int n = vec.size();

    int m, i, j, k, l;
    for (m = n / 2; m > 0; m /= 2) {
        for (i = m; i < n; i++) {
            for (j = i - m; j >= 0; j -= m) {
                if (vec[j] <= vec[j + m]) {
                    break;
                } else {
                    swap(vec[j], vec[j + m]);
                }
            }
        }
    }
}

void printVector(const vector<int>& vec)
{
    for (int num : vec)
        cout << num << " ";
}

int main()
{
    vector<int> vec = { -25, 12, -2, 0, 25, 36 };

    // Sort the vector using Shell Metzner Sort
    shellMetznerSort(vec);

    // Print the sorted vector
    printVector(vec);

    return 0;
}

Time and Space Complexity

Time Complexity : O(n^2)
Space Complexity: O(1)

Explanation:

1. The outer loop runs for a number of iterations determined by the gap sequence. In the worst case, where the gap sequence is a simple halving of the gap value (as seen in this code), the outer loop will run approximately log2(n) times. This is because the gap value m is halved in each iteration until it becomes 0.

2. The middle loop (the second loop) runs n - m times in each iteration of the outer loop, where n is the number of elements in the vector. Inside the outer loop, the middle loop runs for O(n) iterations. This loop scans through the entire array.

3. The innermost loop (the third loop) performs constant time operations for each comparison and swap within a subsequence. The number of iterations of this loop depends on the value of m and the length of the subsequence being considered.

Considering all the loops, the total time complexity is typically considered O(n^2) because the elements are partially sorted with the varying gap sequence before the final sorting pass with a gap of 1.

Another Approach

Continuously decrease the gap size within a loop until it becomes 1.

• Start with a gap value, initially set to half the length of the array.
• Divide the array into subarrays of this gap size.
• For each subarray, perform insertion sort by comparing elements that are 'gap' positions apart.
• Reduce the gap value and repeat the process until the gap becomes 1. At this point, the last step is a normal insertion sort.

Implementation

#include <iostream>
#include <vector>
using namespace std;

vector<int> shellSort(vector<int>& arr) {
    int n = arr.size();
    int gap = n / 2;

    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int current = i;
            int compare = current - gap;

            while (compare >= 0 && arr[current] < arr[compare]) {
                swap(arr[current], arr[compare]);
                current = compare;
                compare -= gap;
            }
        }
        gap /= 2;
    }

    return arr;
}

int main() {
    int input[] = { -25, 12, -2, 0, 25, 36 };
    vector<int> inputVector(input, input + sizeof(input) / sizeof(int));
    vector<int> sortedVector = shellSort(inputVector);

    for (int element : sortedVector) {
        cout << element << " ";
    }
    cout << endl;

    return 0;
}

Complexity

Time Complexity: O(n^2)
Auxiliary Space: O(1)