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;
}
Try It

 


Next > < Prev
Scroll to Top