Sort a nearly sorted (or K sorted) array | Set 2 (Gap method – Shell sort)

0 0 7 minutes read

Given an array, arr[] of N elements, where each element is at most K away from its target position, the task is to devise an algorithm that sorts in O(N*log(K)) time.

Examples:

Input: arr[] = {10, 9, 8, 7, 4, 70, 60, 50}, K = 4
Output: 4 7 8 9 10 50 60 70
Explanation:
Follow the steps below to sort the array:

Start with Gap = K(i.e. 4)

10 9 8 7 4 70 60 50, swap the elements at indices 0 and 4. Then the array modifies to {4, 9, 8, 7, 10, 70, 60, 50}.
4 9 8 7 10 70 60 50, Do not swap the elements at indices 1 and 5.
4 9 8 7 10 70 60 50, Do not swap the elements at indices 2 and 6.
4 9 8 7 10 70 60 50, Do not swap the elements at indices 3 and 7.

Gap = ceiling of 4/2 = 2

4 9 8 7 10 70 60 50, Do not swap the elements at indices 0 and 2.
4 9 8 7 10 70 60 50, swap the elements at indices 1 and 3. Then the array modifies to {4, 7, 8, 9, 10, 70, 60, 50}.
4 7 8 9 10 70 60 50, Do not swap the elements at indices 2 and 4.
4 7 8 9 10 70 60 50, Do not swap the elements at indices 3 and 5.
4 7 8 9 10 70 60 50, Do not swap the elements at indices 4 and 6.
4 7 8 9 10 70 60 50, swap the elements at indices 5 and 7. Then the array modifies to {4, 7, 8, 9, 10, 70, 60, 50}.
4 7 8 9 10 50 60 70

Gap = ceiling of 2/2 = 1

4 7 8 9 10 50 60 70, Do not swap the elements at indices 0 and 1.
4 7 8 9 10 50 60 70, Do not swap the elements at indices 1 and 2.
4 7 8 9 10 50 60 70, Do not swap the elements at indices 2 and 3.
4 7 8 9 10 50 60 70, Do not swap the elements at indices 3 and 4.
4 7 8 9 10 50 60 70, Do not swap the elements at indices 4 and 5.
4 7 8 9 10 50 60 70, Do not swap the elements at indices 5 and 6.
4 7 8 9 10 50 60 70, Do not swap the elements at indices 6 and 7.

Input: arr[] = {6, 5, 3, 2, 8, 10, 9}, K = 3
Output: 2 3 5 6 8 9 10

Approach: The given problem Sort a nearly sorted (or K sorted) array is already solved. Here the idea is to use shell sorting to sort the array. The idea used here is similar to the merging step of the In-Place Merge Sort. Follow the steps below to solve the problem:

Initialize a variable, say Gap with a value K to sort every Gap^thelement of every sublist.
Iterate until Gap is greater than 0 and perform the following steps:
- Iterate over the range [0, N-Gap] using the variable i, and in each iteration, if arr[i] is greater than the arr[i+Gap], then swap the array elements.
- Update the Gap as Gap = ceil(Gap/2).
Finally, after completing the above step print the elements of the array arr[].

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the nextGap
int nextGap(double k)
{
    if (k < 2)
        return 0;
    return ceil(k / 2);
}
 
// A utility function to print the array
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
// Function to sort a K sorted array
void kSort(int arr[], int K, int n)
{
   
    // Iterate until gap is atleast
    // greater than 0
    for (int gap = K; gap > 0; gap = nextGap(gap)) {
 
        // Iterate over the range [0, N]
        for (int i = 0; i + gap < n; i++) {
 
            // If arr[i] is greater
            // than arr[i+gap]
            if (arr[i] > arr[i + gap]) {
 
                // Swap arr[i] and
                // arr[i+gap]
                swap(arr[i], arr[i + gap]);
            }
        }
    }
    printArray(arr, n);
}
 
// Driver Code
int main()
{
 
    // Input
    int arr[] = { 10, 9, 8, 7, 4, 70, 60, 50 };
    int K = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    kSort(arr, K, n);
    return 0;
}
 
// This code is contributed by lokesh potta.

Java

// Java program for the above approach
import java.util.Iterator;
import java.util.PriorityQueue;
 
class GFG {
 
    // Function to sort a K sorted array
    static void kSort(int[] arr, int K)
    {
        // Iterate until gap is atleast
        // greater than 0
        for (int gap = K; gap > 0; gap = nextGap(gap)) {
 
            // Iterate over the range [0, N]
            for (int i = 0; i + gap < arr.length; i++) {
 
                // If arr[i] is greater
                // than arr[i+gap]
                if (arr[i] > arr[i + gap]) {
 
                    // Swap arr[i] and
                    // arr[i+gap]
                    swap(arr, i, i + gap);
                }
            }
        }
        printArray(arr);
    }
 
    // Function to find the nextGap
    static int nextGap(double k)
    {
        if (k < 2)
            return 0;
        return (int)Math.ceil(k / 2);
    }
 
    // Function to swap two elements
    // of the array arr[]
    static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    // A utility function to print the array
    private static void printArray(int[] arr)
    {
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input
        int arr[] = { 10, 9, 8, 7, 4, 70, 60, 50 };
        int K = 3;
 
        // Function call
        kSort(arr, K);
    }
}

Python3

# Python3 program for the above approach
import math
 
# Function to find the nextGap
def nextGap(k):
     
    if (k < 2):
        return 0
         
    return math.ceil(k / 2)
 
# A utility function to print array
def printArray(arr, n):
     
    for i in range(n):
        print(arr[i], end = " ")
 
# Function to sort a K sorted array
def kSort(arr, K, n):
   
    # Iterate until gap is atleast
    # greater than 0
    gap = K
     
    while (gap > 0):
         
        # Iterate over the range [0, N]
        i = 0
        while (i + gap < n):
             
            # If arr[i] is greater
            # than arr[i+gap]
            if (arr[i] > arr[i + gap]):
                 
                # Swap arr[i] and
                # arr[i+gap]
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                 
            i += 1
         
        gap = nextGap(gap)
         
    printArray(arr, n)
 
# Driver Code
 
# Input
arr = [ 10, 9, 8, 7, 4, 70, 60, 50 ]
K = 3
n = len(arr)
   
# Function call
kSort(arr, K, n)
 
# This code is contributed by target_2

C#

// C# program for the above approach
using System;
 
class GFG {
 
    // Function to sort a K sorted array
    static void kSort(int[] arr, int K)
    {
        // Iterate until gap is atleast
        // greater than 0
        for (int gap = K; gap > 0; gap = nextGap(gap)) {
 
            // Iterate over the range [0, N]
            for (int i = 0; i + gap < arr.Length; i++) {
 
                // If arr[i] is greater
                // than arr[i+gap]
                if (arr[i] > arr[i + gap]) {
 
                    // Swap arr[i] and
                    // arr[i+gap]
                    swap(arr, i, i + gap);
                }
            }
        }
        printArray(arr);
    }
 
    // Function to find the nextGap
    static int nextGap(double k)
    {
        if (k < 2)
            return 0;
        return (int)Math.Ceiling(k / 2);
    }
 
    // Function to swap two elements
    // of the array arr[]
    static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    // A utility function to print the array
    private static void printArray(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // Input
        int []arr = { 10, 9, 8, 7, 4, 70, 60, 50 };
        int K = 3;
 
        // Function call
        kSort(arr, K);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the nextGap
function nextGap(k)
{
    if (k < 2)
        return 0;
         
    return Math.ceil(k / 2);
}
 
// A utility function to print the array
function printArray(arr, n) 
{
    for(let i = 0; i < n; i++)
        document.write(arr[i] + " ");
}
 
// Function to sort a K sorted array
function kSort(arr, K, n) 
{
     
    // Iterate until gap is atleast
    // greater than 0
    for(let gap = K; gap > 0; gap = nextGap(gap)) 
    {
         
        // Iterate over the range [0, N]
        for(let i = 0; i + gap < n; i++) 
        {
             
            // If arr[i] is greater
            // than arr[i+gap]
            if (arr[i] > arr[i + gap])
            {
                 
                // Swap arr[i] and
                // arr[i+gap]
                let temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
            }
        }
    }
    printArray(arr, n);
}
 
// Driver Code
 
// Input
let arr = [ 10, 9, 8, 7, 4, 70, 60, 50 ];
let K = 3;
let n = arr.length;
 
// Function call
kSort(arr, K, n);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output

4 7 8 9 10 50 60 70

Time Complexity: O(N*log K)
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 zambiatek!