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 Gapth element 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 nextGapint nextGap(double k){ if (k < 2) return 0; return ceil(k / 2);}// A utility function to print the arrayvoid printArray(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Function to sort a K sorted arrayvoid 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 Codeint 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 approachimport 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 approachimport math# Function to find the nextGapdef nextGap(k): if (k < 2): return 0 return math.ceil(k / 2)# A utility function to print arraydef printArray(arr, n): for i in range(n): print(arr[i], end = " ")# Function to sort a K sorted arraydef 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# Inputarr = [ 10, 9, 8, 7, 4, 70, 60, 50 ]K = 3n = len(arr) # Function callkSort(arr, K, n)# This code is contributed by target_2 |
C#
// C# program for the above approachusing 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 nextGapfunction nextGap(k){ if (k < 2) return 0; return Math.ceil(k / 2);}// A utility function to print the arrayfunction printArray(arr, n) { for(let i = 0; i < n; i++) document.write(arr[i] + " ");}// Function to sort a K sorted arrayfunction 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// Inputlet arr = [ 10, 9, 8, 7, 4, 70, 60, 50 ];let K = 3;let n = arr.length;// Function callkSort(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
