Sort a nearly sorted (or K sorted) array
Last Updated :
10 Oct, 2024
Given an array and a number k where k is smaller than or equal to the size of the array. The given array is sorted in a way that every element is at-most k distance away from it sorted position. It means if we completely sort the array, then the index of the element can go from i – k to i + k where i is index in the given array. Our task is to completely sort the array.
Examples:
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}
Naive Approach – Insertion Sort – O(nk) Time and O(1) Space
We simply use insertion sort as it is to sort the array efficiently as index of every element can be changed by atmost K places, which will reduce the time complexity of this algorithm from O(n2) to O(nk) as the element would not be inserted more than k position away,
C++
#include <bits/stdc++.h>
using namespace std;
void insertionSort(vector<int>& arr) {
// Traverse through 1 to size of the array
for (int i = 1; i < arr.size(); i++) {
// Move elements of arr[0..i-1], that are greater than key
// to one position ahead of their current position
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
vector<int> arr = {6, 5, 3, 2, 8, 10, 9};
insertionSort(arr);
for (int x : arr)
cout << x << " ";
return 0;
}
/* Function to sort an array using insertion sort*/
void insertionSort(int A[], int size)
{
int i, key, j;
for (i = 1; i < size; i++) {
key = A[i];
j = i - 1;
/* Move elements of A[0..i-1], that are
greater than key, to one
position ahead of their current position.
This loop will run at most k times */
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = key;
}
}
/* Function to sort an array using insertion sort*/
static void insertionSort(int A[], int size)
{
int i, key, j;
for (i = 1; i < size; i++) {
key = A[i];
j = i - 1;
/* Move elements of A[0..i-1], that
are greater than key, to one
position ahead of their current position.
This loop will run at most k times */
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = key;
}
}
# Function to sort an array using
# insertion sort
def insertionSort(A, size):
i, key, j = 0, 0, 0
for i in range(size):
key = A[i]
j = i-1
# Move elements of A[0..i-1], that are
# greater than key, to one position
# ahead of their current position.
# This loop will run at most k times
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
/* C# Function to sort an array using insertion sort*/
static void insertionSort(int A[], int size)
{
int i, key, j;
for (i = 1; i < size; i++) {
key = A[i];
j = i - 1;
/* Move elements of A[0..i-1], that are greater than
key, to one position ahead of their current
position. This loop will run at most k times */
while (j >= 0 && A[j] > key) {
A[j + 1] = A[j];
j = j - 1;
}
A[j + 1] = key;
}
}
/* Function to sort an array using insertion sort*/
function insertionSort(A, size)
{
var i, key, j;
for (i = 1; i < size; i++)
{
key = A[i];
j = i-1;
/* Move elements of A[0..i-1], that are
greater than key, to one
position ahead of their current position.
This loop will run at most k times */
while (j >= 0 && A[j] > key)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = key;
}
}
// This code is contributed by itsok.
Expected Approach – Using Heap – O(k + (n-k)*Log k) Time and O(k) Space
Follow the below steps to solve the problem:
- Create a Min Heap of size K+1 with the first K+1 elements. We are creating a heap of size K as the element can be at most K distance from its index in a sorted array.
- One by one remove the min element from the heap, put it in the result array, and add a new element to the heap from the remaining elements.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
// Sorts a nearly sorted array where every element is at most
// k positions away from its target position.
void sortK(vector<int>& arr, int k)
{
int n = arr.size();
// Size of priority queue or min heap
int pqSz = (n == k) ? k : k + 1;
// Min-heap to store the first k+1 elements
priority_queue<int, vector<int>, greater<int>>
pq(arr.begin(), arr.begin() + pqSz);
int idx = 0;
// Process remaining elements
for (int i = k + 1; i < n; i++) {
arr[idx++] = pq.top();
pq.pop();
pq.push(arr[i]);
}
// Place remaining elements from the heap into
// the array
while (!pq.empty()) {
arr[idx++] = pq.top();
pq.pop();
}
}
int main()
{
int k = 3;
vector<int> arr = {2, 6, 3, 12, 56, 8};
sortK(arr, k);
for (int& x : arr)
cout << x << ' ';
return 0;
}
// Java program to sort a nearly sorted array
import java.util.Iterator;
import java.util.PriorityQueue;
class GFG {
private static void kSort(int[] arr, int n, int k)
{
if (arr == null || arr.length == 0) {
return;
}
// min heap
PriorityQueue<Integer> priorityQueue
= new PriorityQueue<>();
// if there are less than k + 1 elements present in
// the array
int minCount = Math.min(arr.length, k + 1);
// add first k + 1 items to the min heap
for (int i = 0; i < minCount; i++) {
priorityQueue.add(arr[i]);
}
int index = 0;
// here even if size=k then n will be n=k,so i<n
// works fine
for (int i = k + 1; i < n; i++) {
arr[index++] = priorityQueue.peek();
priorityQueue.poll();
priorityQueue.add(arr[i]);
}
Iterator<Integer> itr = priorityQueue.iterator();
while (itr.hasNext()) {
arr[index++] = priorityQueue.peek();
priorityQueue.poll();
}
}
// A utility function to print the array
private 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 k = 3;
int arr[] = { 2, 6, 3, 12, 56, 8 };
int n = arr.length;
// function call
kSort(arr, n, k);
printArray(arr, n);
}
}
// This code is contributed by
// Manpreet Singh(manpreetsngh294)
# A Python3 program to sort a
# nearly sorted array.
from heapq import heappop, heappush, heapify
# A utility function to print
# array elements
def print_array(arr: list):
for elem in arr:
print(elem, end=' ')
# Given an array of size n, where every
# element is k away from its target
# position, sorts the array in O(nLogk) time.
def sort_k(arr: list, n: int, k: int):
"""
:param arr: input array
:param n: length of the array
:param k: max distance, which every
element is away from its target position.
:return: None
"""
# List of first k+1 items
heap = arr[:k + 1]
# using heapify to convert list
# into heap(or min heap)
heapify(heap)
# "rem_elmnts_index" is index for remaining
# elements in arr and "target_index" is
# target index of for current minimum element
# in Min Heap "heap".
target_index = 0
# here even if size=k then n will be n=k,so i<n works fine
for rem_elmnts_index in range(k + 1, n):
arr[target_index] = heappop(heap)
heappush(heap, arr[rem_elmnts_index])
target_index += 1
while heap:
arr[target_index] = heappop(heap)
target_index += 1
# Driver Code
k = 3
arr = [2, 6, 3, 12, 56, 8]
n = len(arr)
sort_k(arr, n, k)
print_array(arr)
# This code is contributed by
# Veerat Beri(viratberi)
// A C# program to sort a nearly sorted array
using System;
using System.Collections.Generic;
class GFG {
static void kSort(int[] arr, int n, int k)
{
// min heap
List<int> priorityQueue = new List<int>();
// add first k + 1 items to the min heap
for (int i = 0; i < k + 1; i++) {
priorityQueue.Add(arr[i]);
}
priorityQueue.Sort();
int index = 0;
// here even if size=k then n will be n=k,so i<n
// works fine
for (int i = k + 1; i < n; i++) {
arr[index++] = priorityQueue[0];
priorityQueue.RemoveAt(0);
priorityQueue.Add(arr[i]);
priorityQueue.Sort();
}
int queue_size = priorityQueue.Count;
for (int i = 0; i < queue_size; i++) {
arr[index++] = priorityQueue[0];
priorityQueue.RemoveAt(0);
}
}
// A utility function to print the array
static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
static void Main()
{
int k = 3;
int[] arr = { 2, 6, 3, 12, 56, 8 };
int n = arr.Length;
kSort(arr, n, k);
printArray(arr, n);
}
}
// This code is contributed by divyeshrabadiya07.
<script>
// A javascript program to sort a nearly sorted array
function kSort(arr,n,k)
{
let priorityQueue=[];
// add first k + 1 items to the min heap
for (let i = 0; i < k + 1; i++) {
priorityQueue.push(arr[i]);
}
priorityQueue.sort(function(a,b){return a-b;});
let index = 0;
// here even if size=k then n will be n=k,so i<n works fine
for (let i = k + 1; i < n; i++) {
arr[index++] = priorityQueue[0];
priorityQueue.shift();
priorityQueue.push(arr[i]);
priorityQueue.sort(function(a,b){return a-b;});
}
while (priorityQueue.length != 0) {
arr[index++] = priorityQueue[0];
priorityQueue.shift();
}
}
// A utility function to print the array
function printArray(arr,n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver Code
let k = 3;
let arr = [ 2, 6, 3, 12, 56, 8 ];
let n = arr.length;
kSort(arr, n, k);
printArray(arr, n);
// This code is contributed by unknown2108
</script>
Note: We can also use a Balanced Binary Search Tree instead of a Heap to store k+1 elements. The insert and delete operations on Balanced BST also take O(log k) time. So Balanced BST-based method will also take O(n log k) time, but the Heap based method seems to be more efficient as the minimum element will always be at the root. Also, Heap doesn’t need extra space for left and right pointers.