# Sort a Nearly Sorted Array (K Sorted Array)

Learn about the K sorted array (sort a nearly sorted array) and its implementation using C++ programs.
Submitted by Vikneshwar GK, on January 16, 2022

K Sorted Array is an array whose elements are at most K elements away from their sorted position. The goal is to sort such an array in an O (n log k) time complexity.

Example:

```Input:
test1[] = {5, 6, 1, 7, 3, 10, 9}
K = 3
Output:
test1[] = {1, 3, 5, 6, 7, 9, 10}

Input:
test2[] = {9, 6, 2, 5, 10, 7}
K = 6
Output:
test2[] = {2, 5, 6, 7, 9, 10}
```

Solution 1: Using Insertion Sort

It is one of the efficient ways to sort K sorted Array. The time complexity of the overall program will be O(nk).

C++ Implementation:

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

// Function that performs Insertion Sort
void insertionSort(int array[], int N, int K)
{
int i, flag, j;

// start from index 1
for (i = 1; i < N; i++) {
// store current element in flag
flag = array[i];
j = i - 1;

// Move the flag element until
// its previous element is greater
// or index is 0
while (j >= 0 && array[j] > flag) {
array[j + 1] = array[j];
j = j - 1;
}
// assign the flag value
// to correct index
array[j + 1] = flag;
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array, N, K;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}

cout << "Enter the value of K: ";
cin >> K;

insertionSort(array, N, K);

cout << "Sorted Array" << endl;
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 10
Enter element 1:2
Enter element 2:4
Enter element 3:1
Enter element 4:3
Enter element 5:6
Enter element 6:5
Enter element 7:7
Enter element 8:10
Enter element 9:9
Enter element 10:8
Enter the value of K: 4
Sorted Array
1 2 3 4 5 6 7 8 9 10
```

Solution 2: Using Heap Data Structure

Algorithm:

• From the first K+1 elements from the K sorted array, create a min Heap of size K+1.
• Pop the minimum element from the Heap and push it into the resultant array.
• Now push the next element from the K sorted array into the Heap.
• If K sorted array becomes empty, rearrange the Heap and Pop.
• Continue this process until Heap becomes empty.

C++ Implementation:

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

// Function to Sort the K Sorted Array
void sortK(int array[], int N, int K)
{
int length;
// if K==N, assign length = K
// else length = K+1
length = (N == K) ? K : K + 1;

// Initialize a Priority Queue with
// the first K elements from the array
priority_queue<int, vector<int>, greater<int> > priority_queue(array, array + length);

int index = 0;
for (int i = K + 1; i < N; i++) {
// Push the min element
// From Priority Queue into the array
array[index++] = priority_queue.top();

// Pop the min element
priority_queue.pop();

// Push another element from array
// Into Priority Queue
priority_queue.push(array[i]);
}

// Pop all elements from Priority Queue
// Push them into array
// Until Priority Queue becomes empty
while (priority_queue.empty() == false) {
array[index++] = priority_queue.top();
priority_queue.pop();
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++)
cout << array[i] << " ";
cout << endl;
}

// Main function
int main()
{
int array, N, K;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}

cout << "Enter the value of K: ";
cin >> K;

sortK(array, N, K);

cout << "Sorted Array" << endl;
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 8
Enter element 1:0
Enter element 2:2
Enter element 3:1
Enter element 4:1
Enter element 5:5
Enter element 6:7
Enter element 7:6
Enter element 8:7
Enter the value of K: 4
Sorted Array
0 1 1 2 5 6 7 7
```

Time Complexity:

1. Min Heap creation - O(k)
2. Push Pop operation in Heap for 1 element - O(log(k))
3. Push Pop operation in Heap for n element - O(n-k * log(k))

Total time complexity - O(k) + O(n-k * log(k))

Preparation

What's New

Top Interview Coding Problems/Challenges!