Home » Data Structure » Array Data Structure

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[100], 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[100], 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))