Sort K-Sorted Array

/* 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;

}

}

#include<stdio.h>

// Prototype of a utility function to swap two integers

void swap(int *x, int *y);

// A class for Min Heap

class MinHeap

{

int *harr; // pointer to array of elements in heap

int heap_size; // size of min heap

public:

// Constructor

MinHeap(int a[], int size);

// to heapify a subtree with root at given index

void MinHeapify(int );

// to get index of left child of node at index i

int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i

int right(int i) { return (2*i + 2); }

// to remove min (or root), add a new value x, and return old root

int replaceMin(int x);

// to extract the root which is the minimum element

int extractMin();

};

// 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)

{

// Create a Min Heap of first (k+1) elements from

// input array

int *harr = new int[k+1];

for (int i = 0; i <=k; i++)

harr[i] = arr[i];

MinHeap hp(harr, k+1);

// i is index for remaining elements in arr[] and ti

// is target index of for cuurent minimum element in

// Min Heapm 'hp'.

for(int i = k+1, ti = 0; ti < n; i++, ti++)

{

// If there are remaining elements, then place

// root of heap at target index and add arr[i]

// to Min Heap

if (i < n)

arr[ti] = hp.replaceMin(arr[i]);

// Otherwise place root at its target index and

// reduce heap size

else

arr[ti] = hp.extractMin();

}

}

// FOLLOWING ARE IMPLEMENTATIONS OF STANDARD MIN HEAP METHODS FROM CORMEN BOOK

// Constructor: Builds a heap from a given array a[] of given size

MinHeap::MinHeap(int a[], int size)

{

heap_size = size;

harr = a; // store address of array

int i = (heap_size - 1)/2;

while (i >= 0)

{

MinHeapify(i);

i--;

}

}

// Method to remove minimum element (or root) from min heap

int MinHeap::extractMin()

{

int root = harr[0];

if (heap_size > 1)

{

harr[0] = harr[heap_size-1];

heap_size--;

MinHeapify(0);

}

return root;

}

// Method to change root with given value x, and return the old root

int MinHeap::replaceMin(int x)

{

int root = harr[0];

harr[0] = x;

if (root < x)

MinHeapify(0);

return root;

}

// A recursive method to heapify a subtree with root at given index

// This method assumes that the subtrees are already heapified

void MinHeap::MinHeapify(int i)

{

int l = left(i);

int r = right(i);

int smallest = i;

if (l < heap_size && harr[l] < harr[i])

smallest = l;

if (r < heap_size && harr[r] < harr[smallest])

smallest = r;

if (smallest != i)

{

swap(&harr[i], &harr[smallest]);

MinHeapify(smallest);

}

}

// A utility function to swap two elements

void swap(int *x, int *y)

{

int temp = *x;

*x = *y;

*y = temp;

}

// A utility function to print array elements

void printArray(int arr[], int size)

{

for (int i=0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

}

// Driver program to test above functions

int main()

{

int k = 3;

int arr[] = {2, 6, 3, 12, 56, 8};

int n = sizeof(arr)/sizeof(arr[0]);

sortK(arr, n, k);

printf("Following is sorted array\n");

printArray (arr, n);

return 0;

}