# Sorting a k sorted array

## k sorted array: An array in which each element is at max k away from its position in the sorted array.

Given an k sorted array, this function will sort the k sorted array in nlogk time

### Example

INPUT:
arr[] = {4, 1, 5, 2, 6}
k = 2

OUTPUT:
{1, 2, 4, 5, 6}

Time Complexity: O(nlogk)

## Algorithm

1. Create a min heap of size k+1 with first k+1 elements

2. The minimum element is at root now, remove minimum element(root) and store it in output array. Now, insert the next element in the heap.

3. Repeat step 2 till the end of the array.

## C++ Program

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

// A utility function to swap two elements
void swap(int *x, int *y)
{
int t = *x;
*x = *y;
*y = t;
}

class MinHeap
{
int *temp; // pointer to array of elements in heap
int heap_size; // size of min heap
public:
// Standard Min Heap Methods
// Constructor: Builds a heap from a given array a[] of given size
MinHeap(int a[], int size)
{
heap_size = size;
temp = a;  // store address of array
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}

// to heapify a subtree with root at given index
void MinHeapify(int i)
{
int l = leftchild(i);
int r = rightchild(i);
int minimum = i;
if (l < heap_size && temp[l] < temp[i])
minimum = l;
if (r < heap_size && temp[r] < temp[minimum])
minimum = r;
if (minimum != i)
{
swap(&temp[i], &temp[minimum]);
MinHeapify(minimum);
}
}

int replaceMin(int x)// method to change root(min) with given value x,
{					 //and return the old root
int root = temp[0];
temp[0] = x;
if (root < x)
MinHeapify(0);
return root;
}

int extractMin() //method to remove root(min) from min heap
{
int root = temp[0];
if (heap_size > 1)
{
temp[0] = temp[heap_size-1];
heap_size--;
MinHeapify(0);
}
return root;
}
// to get index of left child of node at index i
int leftchild(int i) { return (2*i + 1); }

// to get index of right child of node at index i
int rightchild(int i) { return (2*i + 2); }
};

int sortKSorted(int arr[], int n, int k)//prints the sorted array
{
// Create a Min Heap of first (k+1) elements from
// input array
int *temp = new int[k+1];
for (int i = 0; i<=k && i<n; i++) // i < n condition is needed when k > n
{
temp[i] = arr[i];
}
MinHeap h(temp, k+1);//creating object

// i is index for remaining elements in arr[] and o_index
// is the output array index to place cuurent minimum element.
for(int i = k+1, o_index = 0; o_index < n; i++, o_index++)
{
if (i < n) //if any elements are remaining
arr[o_index] = h.replaceMin(arr[i]);

// Otherwise place root at its target index and
else
arr[o_index] = h.extractMin();
}
for (int i=0; i < n; i++) //printing the sorted array
{
cout << arr[i] << " ";
}
}

int main()
{
int arr[]= {4, 1, 5, 2, 6, 7, 10};  //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
int k =2;
sortKSorted(arr, n, k);
return 0;
}``````

Scroll to Top