Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. It may be assumed that k < n.
Example:
Input: arr[] = {6, 5, 3, 2, 8, 10, 9},
k = 3
Output: arr[] = {2, 3, 5, 6, 8, 9, 10}
Input: arr[] = {10, 9, 8, 7, 4, 70, 60, 50},
k = 4
Output: arr[] = {4, 7, 8, 9, 10, 50, 60, 70}
Simple Approach: The basic solution is to sort the array using any standard sorting algorithm.
Implementation:
CPP14
// A STL based C++ program to// sort a nearly sorted array.#include <bits/stdc++.h>using namespace std;// Given an array of size n,// where every element// is k away from its target// position, sorts the// array in O(n Log n) time.int sortK(int arr[], int n, int k){ // Sort the array using // inbuilt function sort(arr, arr + n);}// An utility function to print// array elementsvoid printArray( int arr[], int size){ for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl;}// Driver program to test// above functionsint main(){ int k = 3; int arr[] = { 2, 6, 3, 12, 56, 8 }; int n = sizeof(arr) / sizeof(arr[0]); sortK(arr, n, k); cout << "Following is sorted array\n"; printArray(arr, n); return 0;} |
Java
// A STL based Java program to // sort a nearly sorted array. import java.util.*;public class GFG{ // Given an array of size n, // where every element // is k away from its target // position, sorts the // array in O(n Log n) time. static void sortK(int[] arr, int n, int k) { // Sort the array using // inbuilt function Arrays.sort(arr); } // An utility function to print // array elements static void printArray( int[] arr, int size) { for (int i = 0; i < size; i++) System.out.print(arr[i] + " "); System.out.println(); } // Driver code public static void main(String[] args) { int k = 3; int[] arr = { 2, 6, 3, 12, 56, 8 }; int n = arr.length; sortK(arr, n, k); System.out.println("Following is sorted array"); printArray(arr, n); }}// This code is contributed by divyesh072019. |
Python3
# A STL based Java program to # sort a nearly sorted array. # Given an array of size n, # where every element # is k away from its target # position, sorts the # array in O(n Log n) time. def sortK(arr, n, k): # Sort the array using # inbuilt function arr.sort()# An utility function to print # array elements def printArray(arr, size): for i in range(size): print(arr[i], end = " ") print()# Driver codek = 3arr = [ 2, 6, 3, 12, 56, 8]n = len(arr)sortK(arr, n, k)print("Following is sorted array")printArray(arr, n)# This code is contributed by avanitrachhadiya2155 |
C#
// A STL based C# program to // sort a nearly sorted array. using System;class GFG { // Given an array of size n, // where every element // is k away from its target // position, sorts the // array in O(n Log n) time. static void sortK(int[] arr, int n, int k) { // Sort the array using // inbuilt function Array.Sort(arr); } // An utility function to print // array elements static void printArray( int[] arr, int size) { for (int i = 0; i < size; i++) Console.Write(arr[i] + " "); Console.WriteLine(); } // Driver code static void Main() { int k = 3; int[] arr = { 2, 6, 3, 12, 56, 8 }; int n = arr.Length; sortK(arr, n, k); Console.WriteLine("Following is sorted array"); printArray(arr, n); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// A STL based Javascript program to// sort a nearly sorted array.// Given an array of size n,// where every element// is k away from its target// position, sorts the// array in O(n Log n) time.function sortK(arr,n,k){ // Sort the array using // inbuilt function (arr).sort(function(a,b){return a-b;});}// An utility function to print// array elementsfunction printArray(arr,size){ for (let i = 0; i < size; i++) document.write(arr[i] + " "); document.write("<br>");}// Driver codelet k = 3;let arr=[ 2, 6, 3, 12, 56, 8 ];let n = arr.length;sortK(arr, n, k);document.write("Following is sorted array<br>");printArray(arr, n);// This code is contributed by ab2127</script> |
Output
Following is sorted array 2 3 6 8 12 56
Complexity Analysis:
- Time complexity: O(n log n), where n is the size of the array.
The sorting algorithm takes log n time. Since the size of the array is n, the whole program takes O(n log n) time. - Space Complexity: O(1).
As no extra space is required.
Efficient Solution: Sliding Window technique.
Approach: A better solution is to use a priority queue(or heap data structure). Use sliding window technique to keep consecutive k elements of a window in heap. Then remove the top element(smallest element) and replace the first element of the window with it.
As each element will be at most k distance apart, therefore keeping k consecutive elements in a window while replacing the i-th element with the smallest element from i to (i+k) will suffice(first i-1 elements are sorted).
Algorithm:
- Build a priority queue pq of first (k+1) elements.
- Initialize index = 0 (For result array).
- Do the following for elements from k+1 to n-1.
- Pop an item from pq and put it at index, increment index.
- Push arr[i] to pq.
- While pq is not empty,
Pop an item from pq and put it at index, increment index.
We have discussed a simple implementation in Sort a nearly sorted (or K sorted) array. In this post, an STL based implementation is done.
Implementation:
C++
// A STL based C++ program to sort// a nearly sorted array.#include <bits/stdc++.h>using namespace std;// Given an array of size n,// where every element// is k away from its target// position, sorts the// array in O(nLogk) time.int sortK(int arr[], int n, int k){ // Insert first k+1 items in a // priority queue (or min heap) // (A O(k) operation) priority_queue<int, vector<int>, greater<int> > pq(arr, arr + k + 1); // i is index for remaining // elements in arr[] and index // is target index of for // current minimum element in // Min Heapm 'hp'. int index = 0; for (int i = k + 1; i < n; i++) { arr[index++] = pq.top(); pq.pop(); pq.push(arr[i]); } while (pq.empty() == false) { arr[index++] = pq.top(); pq.pop(); }}// A utility function to print// array elementsvoid printArray(int arr[], int size){ for (int i = 0; i < size; i++) cout << arr[i] << " "; cout << endl;}// Driver program to test above functionsint main(){ int k = 3; int arr[] = { 2, 6, 3, 12, 56, 8 }; int n = sizeof(arr) / sizeof(arr[0]); sortK(arr, n, k); cout << "Following is sorted arrayn"; printArray(arr, n); return 0;} |
Java
// Java program to sort a nearly sorted array.import java.util.*;// Given an array of size n,// where every element// is k away from its target// position, sorts the// array in O(nLogk) time.public class SortK{ // Insert first k+1 items in a // priority queue (or min heap) // (A O(k) operation) public static int sortK(int arr[], int n, int k) { // Create a min heap PriorityQueue<Integer> pq = new PriorityQueue<>(); // Add first k+1 elements to the min heap for (int i = 0; i < k + 1; i++) pq.add(arr[i]); // i is index for remaining // elements in arr[] and index // is target index of for // current minimum element in // Min Heapm 'hp'. int index = 0; for (int i = k + 1; i < n; i++) { arr[index++] = pq.peek(); pq.poll(); pq.add(arr[i]); } // Remove all remaining elements // from the min heap while (!pq.isEmpty()) { arr[index++] = pq.peek(); pq.poll(); } return 0; } // A utility function to print // array elements public static void printArray(int arr[], int size) { for (int i = 0; i < size; i++) System.out.print(arr[i] + " "); System.out.println(); } // Driver program to test above functions public static void main(String args[]) { int k = 3; int arr[] = { 2, 6, 3, 12, 56, 8 }; int n = arr.length; sortK(arr, n, k); System.out.println("Following is sorted array"); printArray(arr, n); }}// This code is contributed by adityamaharshi21 |
Python
from heapq import heapify, heappop, heappushdef sortK(arr, n, k): # Insert first k+1 items in a # priority queue (or min heap) # (A O(k) operation) pq = arr[:k+1] heapify(pq) # i is index for remaining # elements in arr[] and index # is target index of for # current minimum element in # Min Heapm 'hp'. index = 0 for i in range(k+1, n): arr[index] = heappop(pq) heappush(pq, arr[i]) index += 1 while pq: arr[index] = heappop(pq) index += 1# A utility function to print# array elementsdef printArray(arr, size): for i in range(size): print(arr[i])# Driver program to test above functionsk = 3arr = [2, 6, 3, 12, 56, 8]n = len(arr)sortK(arr, n, k)print("Following is sorted array")printArray(arr, n)# This code is contributed by aadityamaharshi21. |
Javascript
function sortK(arr, n, k) { // Insert first k+1 items in a // priority queue (or min heap) // (A O(k) operation) const pq = arr.slice(0, k + 1); pq.sort((a, b) => a - b); // i is index for remaining // elements in arr[] and index // is target index of for // current minimum element in // Min Heapm 'hp'. let index = 0; for (let i = k + 1; i < n; i++) { arr[index] = pq.shift(); pq.push(arr[i]); pq.sort((a, b) => a - b); index += 1; } while (pq.length > 0) { arr[index] = pq.shift(); index += 1; } } // A utility function to print // array elements function printArray(arr) { console.log(arr.join(' ')); } // Driver program to test above functions const k = 3; const arr = [2, 6, 3, 12, 56, 8]; const n = arr.length; sortK(arr, n, k); console.log('Following is sorted array'); printArray(arr); // This code is contributed by adityamaharshi21. |
C#
using System;using System.Linq;using System.Collections.Generic;public class SortK { public static void SortKMethod(int[] arr, int n, int k) { // Insert first k+1 items in a // priority queue (or min heap) // (A O(k) operation) var pq = arr.Take(k + 1).ToList(); pq.Sort((a, b) = > a - b); // i is index for remaining // elements in arr[] and index // is target index of for // current minimum element in // Min Heapm 'hp'. int index = 0; for (int i = k + 1; i < n; i++) { arr[index] = pq[0]; pq.RemoveAt(0); pq.Add(arr[i]); pq.Sort((a, b) = > a - b); index += 1; } while (pq.Count > 0) { arr[index] = pq[0]; pq.RemoveAt(0); index += 1; } } // A utility function to print // array elements public static void PrintArray(int[] arr) { Console.WriteLine(string.Join(" ", arr)); } // Driver program to test above functions public static void Main() { int k = 3; int[] arr = { 2, 6, 3, 12, 56, 8 }; int n = arr.Length; SortKMethod(arr, n, k); Console.WriteLine("Following is sorted array"); PrintArray(arr); }} |
Output
Following is sorted arrayn2 3 6 8 12 56
Complexity Analysis:
- Time Complexity: O(n Log k).
For every element, it is pushed in the priority queue and the insertion and deletion needs O(log k) time as there are k elements in priority queue. - Auxiliary Space: O(k).
To store k elements in the priority queue, O(k) space is required.
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!
