Question

Im really trying to understand fully and PROPERLY. very lost on the topic. Please help me and give explaination of each steps. thank you so much

Answer 1

Let us assume size of array is N where each element is atmost k away from its target position. Now an algorithm that sorts inO (nlogk) time.

Examples:

1.Input-

a[] ={7,4,2,8,9,3,1}

k=3

Output-

a[]={1,2,3,4,7,8,9}

2 Input

a[] ={8,7,6,4,3,2,9,1}

k=8

Output

a[] ={1,2,3,4,6,7,8,9}

................Program to implement insertion sort........

static void insertionSort(int Arr[], int size)

{

int i, key, j;

for (i = 1; i < size; i++)

{

    key= Arr[i];

    j = i-1;

    while (j >= 0 && Arr[j] > key)

    {

‌   Arr[j+1] = Arr[j];

        j = j-1;

    }
Arr[j+1]=key;
}
}

.............

Inner loop will run at almost k times. To move each element to correct location at most k elements are required to move. So complexity will be O(nk).

You can also solve it with the help of Heap data structures.