Open In App

Sort a nearly sorted (or K sorted) array

Last Updated : 10 Oct, 2024
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow
Companies:
Show Topics
Solve Problem
Medium
75.25%
45.8K

Given an array and a number k where k is smaller than or equal to the size of the array. The given array is sorted in a way that every element is at-most k distance away from it sorted position. It means if we completely sort the array, then the index of the element can go from i – k to i + k where i is index in the given array. Our task is to completely sort the array.

Examples: 

Input: arr[] = {6, 5, 3, 2, 8, 10, 9}, K = 3 
Output: arr[] = {2, 3, 5, 6, 8, 9, 10}

Input: arr[] = {10, 9, 8, 7, 4, 70, 60, 50}, k = 4
Output: arr[] = {4, 7, 8, 9, 10, 50, 60, 70}

Naive Approach – Insertion Sort – O(nk) Time and O(1) Space

We simply use insertion sort as it is to sort the array efficiently as index of every element can be changed by atmost K places, which will reduce the time complexity of this algorithm from O(n2) to O(nk) as the element would not be inserted more than k position away, 

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

void insertionSort(vector<int>& arr) {
    
    // Traverse through 1 to size of the array
    for (int i = 1; i < arr.size(); i++) {
        
        // Move elements of arr[0..i-1], that are greater than key
        // to one position ahead of their current position
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {6, 5, 3, 2, 8, 10, 9};
    insertionSort(arr);    
    for (int x : arr)
        cout << x << " ";
    return 0;
}
C
/* 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;
    }
}
Java
/* Function to sort an array using insertion sort*/
static 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;
    }
}
Python
# Function to sort an array using
# insertion sort


def insertionSort(A, size):
    i, key, j = 0, 0, 0
    for i in range(size):
        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 and A[j] > key:
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key
C#
/* C# Function to sort an array using insertion sort*/
static 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;
    }
}
JavaScript
/* Function to sort an array using insertion sort*/
function insertionSort(A, size)
{
   var 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;
   }
}

// This code is contributed by itsok.

Output
2 3 5 6 8 9 10 

Expected Approach – Using Heap – O(k + (n-k)*Log k) Time and O(k) Space

Follow the below steps to solve the problem:

  • Create a Min Heap of size K+1 with the first K+1 elements. We are creating a heap of size K as the element can be at most K distance from its index in a sorted array. 
  • One by one remove the min element from the heap, put it in the result array, and add a new element to the heap from the remaining elements.

Below is the implementation of the above approach:

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

// Sorts a nearly sorted array where every element is at most
// k positions away from its target position.
void sortK(vector<int>& arr, int k)
{
    int n = arr.size();  

    // Size of priority queue or min heap
    int pqSz = (n == k) ? k : k + 1; 
    
    // Min-heap to store the first k+1 elements
    priority_queue<int, vector<int>, greater<int>> 
                    pq(arr.begin(), arr.begin() + pqSz);

    int idx = 0;

    // Process remaining elements
    for (int i = k + 1; i < n; i++) {
        arr[idx++] = pq.top();
        pq.pop();
        pq.push(arr[i]);
    }

    // Place remaining elements from the heap into 
    // the array
    while (!pq.empty()) {
        arr[idx++] = pq.top();
        pq.pop();
    }
}

int main()
{
    int k = 3;
    vector<int> arr = {2, 6, 3, 12, 56, 8};
    sortK(arr, k);
    for (int& x : arr)
        cout << x << ' ';
    return 0;
}
Java
// Java program to sort a nearly sorted array
import java.util.Iterator;
import java.util.PriorityQueue;

class GFG {
    private static void kSort(int[] arr, int n, int k)
    {
        if (arr == null || arr.length == 0) {
            return;
        }
        // min heap
        PriorityQueue<Integer> priorityQueue
            = new PriorityQueue<>();
        // if there are less than k + 1 elements present in
        // the array
        int minCount = Math.min(arr.length, k + 1);
        // add first k + 1 items to the min heap
        for (int i = 0; i < minCount; i++) {
            priorityQueue.add(arr[i]);
        }

        int index = 0;
        // here even if size=k then n will be n=k,so i<n
        // works fine
        for (int i = k + 1; i < n; i++) {
            arr[index++] = priorityQueue.peek();
            priorityQueue.poll();
            priorityQueue.add(arr[i]);
        }

        Iterator<Integer> itr = priorityQueue.iterator();

        while (itr.hasNext()) {
            arr[index++] = priorityQueue.peek();
            priorityQueue.poll();
        }
    }

    // A utility function to print the array
    private static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

    // Driver Code
    public static void main(String[] args)
    {
        int k = 3;
        int arr[] = { 2, 6, 3, 12, 56, 8 };
        int n = arr.length;

        // function call
        kSort(arr, n, k);
        printArray(arr, n);
    }
}

// This code is contributed by
// Manpreet Singh(manpreetsngh294)
Python
# A Python3 program to sort a
# nearly sorted array.

from heapq import heappop, heappush, heapify


# A utility function to print
# array elements
def print_array(arr: list):
    for elem in arr:
        print(elem, end=' ')

# Given an array of size n, where every
# element is k away from its target
# position, sorts the array in O(nLogk) time.


def sort_k(arr: list, n: int, k: int):
    """
    :param arr: input array
    :param n: length of the array
    :param k: max distance, which every 
     element is away from its target position.
    :return: None
    """
    # List of first k+1 items
    heap = arr[:k + 1]

    # using heapify to convert list
    # into heap(or min heap)
    heapify(heap)

    # "rem_elmnts_index" is index for remaining
    # elements in arr and "target_index" is
    # target index of for current minimum element
    # in Min Heap "heap".
    target_index = 0

    # here even if size=k then n will be n=k,so i<n works fine
    for rem_elmnts_index in range(k + 1, n):
        arr[target_index] = heappop(heap)
        heappush(heap, arr[rem_elmnts_index])
        target_index += 1

    while heap:
        arr[target_index] = heappop(heap)
        target_index += 1


# Driver Code
k = 3
arr = [2, 6, 3, 12, 56, 8]
n = len(arr)
sort_k(arr, n, k)

print_array(arr)

# This code is contributed by
# Veerat Beri(viratberi)
C#
// A C# program to sort a nearly sorted array
using System;
using System.Collections.Generic;
class GFG {

    static void kSort(int[] arr, int n, int k)
    {

        // min heap
        List<int> priorityQueue = new List<int>();

        // add first k + 1 items to the min heap
        for (int i = 0; i < k + 1; i++) {
            priorityQueue.Add(arr[i]);
        }

        priorityQueue.Sort();

        int index = 0;
        // here even if size=k then n will be n=k,so i<n
        // works fine
        for (int i = k + 1; i < n; i++) {
            arr[index++] = priorityQueue[0];
            priorityQueue.RemoveAt(0);
            priorityQueue.Add(arr[i]);
            priorityQueue.Sort();
        }

        int queue_size = priorityQueue.Count;

        for (int i = 0; i < queue_size; i++) {
            arr[index++] = priorityQueue[0];
            priorityQueue.RemoveAt(0);
        }
    }

    // A utility function to print the array
    static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }

    // Driver code
    static void Main()
    {
        int k = 3;
        int[] arr = { 2, 6, 3, 12, 56, 8 };
        int n = arr.Length;
        kSort(arr, n, k);
        printArray(arr, n);
    }
}

// This code is contributed by divyeshrabadiya07.
JavaScript
<script>
// A javascript program to sort a nearly sorted array

function kSort(arr,n,k)
{
    let priorityQueue=[];
    // add first k + 1 items to the min heap
        for (let i = 0; i < k + 1; i++) {
            priorityQueue.push(arr[i]);
        }
        priorityQueue.sort(function(a,b){return a-b;});
 
        let index = 0;
        
        // here even if size=k then n will be n=k,so i<n works fine
        for (let i = k + 1; i < n; i++) {
            arr[index++] = priorityQueue[0];
            priorityQueue.shift();
            priorityQueue.push(arr[i]);
            priorityQueue.sort(function(a,b){return a-b;});
        }
 
        
 
        while (priorityQueue.length != 0) {
            arr[index++] = priorityQueue[0];
            priorityQueue.shift();
        }
}

// A utility function to print the array
function printArray(arr,n)
{
    for (let i = 0; i < n; i++)
            document.write(arr[i] + " ");
}

// Driver Code
let k = 3;
let arr = [ 2, 6, 3, 12, 56, 8 ];
let n = arr.length;
kSort(arr, n, k);

printArray(arr, n);

// This code is contributed by unknown2108
</script>

Output
2 3 6 8 12 56 

Note: We can also use a Balanced Binary Search Tree instead of a Heap to store k+1 elements. The insert and delete operations on Balanced BST also take O(log k) time. So Balanced BST-based method will also take O(n log k) time, but the Heap based method seems to be more efficient as the minimum element will always be at the root. Also, Heap doesn’t need extra space for left and right pointers.



Previous Article
Next Article

Similar Reads

Sort a nearly sorted (or K sorted) array | Set 2 (Gap method - Shell sort)
Given an array, arr[] of N elements, where each element is at most K away from its target position, the task is to devise an algorithm that sorts in O(N*log(K)) time. Examples: Input: arr[] = {10, 9, 8, 7, 4, 70, 60, 50}, K = 4Output: 4 7 8 9 10 50 60 70Explanation:Follow the steps below to sort the array: Start with Gap = K(i.e. 4)10 9 8 7 4 70 60
8 min read
Sort a nearly sorted array using STL
Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. It may be assumed that k < n. Example: Input: arr[] = {6, 5, 3, 2, 8, 1
11 min read
Sort a nearly sorted doubly linked list
Given a doubly linked list containing n nodes, each node is at most k-indices away from its target position. The problem is to sort the given doubly linked list. The distance can be assumed in either of the directions (left and right). Examples: Input: Doubly Linked List : 3 <-> 2 <-> 1 <-> 5 <-> 6 <-> 4 , k = 2Output:
15+ min read
Check if a number can be represented as sum of K positive integers out of which at least K - 1 are nearly prime
Given two integers N and K, the task is to check if N can be represented as a sum of K positive integers, where at least K - 1 of them are nearly prime. Nearly Primes: Refers to those numbers which can be represented as a product of any pair of prime numbers. Examples: Input: N = 100, K = 6Output: YesExplanation: 100 can be represented as 4 + 6 + 9
15+ min read
Tag sort or Bucket sort or Bin sort in Python
Tag sort, also known as Bucket sort or Bin sort, is a non-comparison based sorting algorithm that distributes elements of an array into a number of "buckets", and then sorts each bucket individually. Tag sort or Bucket sort or Bin sort Algorithm:Determine Range:Find the maximum and minimum values in the input array to determine the range of tags ne
2 min read
Comparison among Bubble Sort, Selection Sort and Insertion Sort
Bubble Sort, Selection Sort, and Insertion Sort are simple sorting algorithms that are commonly used to sort small datasets or as building blocks for more complex sorting algorithms. Here's a comparison of the three algorithms: Bubble Sort:Time complexity: O(n^2) in the worst and average cases, O(n) in the best case (when the input array is already
15 min read
Sort a K sorted Doubly Linked List | Set 2 (Using Shell Sort)
Given a doubly-linked list containing N nodes, where each node is at most K away from its target position in the list, the task is to sort the given doubly linked list. Examples: Input: DLL: 3<->6<->2<->12<->56<->8, K = 2Output: 2<->3<->6<->8<->12<->56 Input: DLL: 3<->2<->1<
12 min read
Count number of common elements between a sorted array and a reverse sorted array
Given two arrays consisting of N distinct integers such that the array A[] and B[] are sorted in ascending and descending order respectively, the task is to find the number of values common in both arrays. Examples: Input: A[] = {1, 10, 100}, B[] = {200, 20, 2}Output: 0 Input: A[] = {2, 4, 5, 8, 12, 13, 17, 18, 20, 22, 309, 999}, B[] = {109, 99, 68
15+ min read
Circularly Sorted Array (Sorted and Rotated Array)
Circularly sorted arrays are arrays that are sorted in ascending or descending order and then rotated by a number of steps. Let us take an example to know more about circularly sorted arrays: Consider an array: arr[] = {23, 34, 45, 12, 17, 19}The elements here, {12, 17, 19, 23, 34, 45} are sorted 'In-order' but they are rotated to the left by 3 tim
7 min read
Check if two sorted arrays can be merged to form a sorted array with no adjacent pair from the same array
Given two sorted arrays A[] and B[] of size N, the task is to check if it is possible to merge two given sorted arrays into a new sorted array such that no two consecutive elements are from the same array. Examples: Input: A[] = {3, 5, 8}, B[] = {2, 4, 6}Output: Yes Explanation: Merged array = {B[0], A[0], B[1], A[1], B[2], A[2]} Since the resultan
15+ min read
Add elements in start to sort the array | Variation of Stalin Sort
Stalin sort (also 'dictator sort' and 'trump sort') is a nonsensical 'sorting' algorithm in which each element that is not in the correct order is simply eliminated from the list. This sorting algorithm is a less destructive variation of Stalin sort, that will actually sort the list: In this case, the elements that are not in order are moved to the
6 min read
Sort the array using slow sort
Given an array arr[] consisting of N integers, the task is to sort the given array in ascending order using the slow sort. Examples: Input: arr[] = {6, 8, 9, 4, 12, 1}Output: 1 4 6 8 9 12 Input: arr[] = {5, 4, 3, 2, 1}Output: 1 2 3 4 5 Approach: Like Merge Sort, Slow Sort is a Divide and Conquer algorithm. It divides the input array into two halves
7 min read
Sort an array using Bubble Sort without using loops
Given an array arr[] consisting of N integers, the task is to sort the given array by using Bubble Sort without using loops. Examples: Input: arr[] = {1, 3, 4, 2, 5}Output: 1 2 3 4 5 Input: arr[] = {1, 3, 4, 2}Output: 1 2 3 4 Approach: The idea to implement Bubble Sort without using loops is based on the following observations: The sorting algorith
9 min read
Bucket Sort To Sort an Array with Negative Numbers
We have discussed bucket sort in the main post on Bucket Sort . Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the problem of sorting a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. In the above post, we have discussed Buck
9 min read
Program to sort an array of strings using Selection Sort
Given an array of strings, sort the array using Selection Sort. Examples: Input : paper true soap floppy flower Output : floppy, flower, paper, soap, true Prerequisite : Selection Sort. C/C++ Code // C++ program to implement selection sort for // array of strings. #include <bits/stdc++.h> #include <string.h> using namespace std; #define
7 min read
Count swaps required to sort an array using Insertion Sort
Given an array A[] of size N (1 ≤ N ≤ 105), the task is to calculate the number of swaps required to sort the array using insertion sort algorithm. Examples: Input: A[] = {2, 1, 3, 1, 2} Output: 4 Explanation: Step 1: arr[0] stays in its initial position. Step 2: arr[1] shifts 1 place to the left. Count = 1. Step 3: arr[2] stays in its initial posi
15 min read
Sort an array of strings having characters at odd and even indices sorted in decreasing and increasing order respectively
Given an array arr[] consisting of N strings, the task is to first sort the characters at odd and even indices of the string in decreasing and increasing order respectively, for each string of the array and then, sort the modified array. Examples: Input: arr[] = {"ball", "bat", "boy"}Output: albl atb byoExplanation:S[0]="ball" is converted to "albl
7 min read
Sort an array having first N elements sorted and last M elements are unsorted
Given two positive integers, N and M, and an array arr[ ] consisting of (N + M) integers such that the first N elements are sorted in ascending order and the last M elements are unsorted, the task is to sort the given array in ascending order. Examples: Input: N = 3, M = 5, arr[] = {2, 8, 10, 17, 15, 23, 4, 12}Output: 2 4 8 10 12 15 17 23 Input: N
13 min read
Sort an almost sorted array where only two elements are swapped
Given an almost sorted array where only two elements are swapped, how to sort the array efficiently?Examples : Input: arr[] = {10, 20, 60, 40, 50, 30} // 30 and 60 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {10, 20, 40, 30, 50, 60} // 30 and 40 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {1, 5, 3} //
7 min read
Sort an array when two halves are sorted
Given an integer array of which both first half and second half are sorted. Task is to merge two sorted halves of array into single sorted array. Examples: Input : A[] = { 2, 3, 8, -1, 7, 10 } Output : -1, 2, 3, 7, 8, 10 Input : A[] = {-4, 6, 9, -1, 3 } Output : -4, -1, 3, 6, 9Recommended: Please solve it on "PRACTICE" first, before moving on to th
10 min read
Sort a Rotated Sorted Array
You are given a rotated sorted array and your aim is to restore its original sort in place.Expected to use O(1) extra space and O(n) time complexity. Examples: Input : [3, 4, 1, 2] Output : [1, 2, 3, 4] Input : [2, 3, 4, 1] Output : [1, 2, 3, 4] We find the point of rotation. Then we rotate array using reversal algorithm. 1. First, find the split p
11 min read
Sort given Array which is already Sorted based on absolute values of elements
Given an array arr[] of size N, sorted based on the absolute value of its elements. The task is to sort this array based on the actual values of the elements. Examples: Input: arr[] = {5, -7, 10, -11, 18}Output: -11, -7, 5, 10, 18Explanation: When the array is sorted the negative values will come at the beginning of the array. Input: arr[] = {1, -2
7 min read
Sort an array of strings in ascending order with each string sorted in descending order
Given a array of strings S[] of size N (1 ? N ? 105), sort characters of each string in descending order and then print the array of strings in ascending order. Examples: Input: s[] = {"apple", "box", "cat"} Output: pplea tca xob Explanation: Sorting each string in descending order, S[] modifies to {"pplea", "xob", "tca"}. Sorting the array in asce
9 min read
Maximize partitions that if sorted individually makes the whole Array sorted
Given an array arr[]. The task is to divide arr[] into the maximum number of partitions, such that, those partitions if sorted individually make the whole array sorted. Examples: Input: arr[] = { 28, 9, 18, 32, 60, 50, 75, 70 }Output: 4Explanation: Following are the partitions in which the array is divided. If we divide arr[] into four partitions {
5 min read
Insertion sort to sort even and odd positioned elements in different orders
We are given an array. We need to sort the even positioned elements in the ascending order and the odd positioned elements in the descending order. We must apply insertion sort to sort them.Examples: Input : a[] = {7, 10, 11, 3, 6, 9, 2, 13, 0} Output : 11 3 7 9 6 10 2 13 0 Even positioned elements after sorting int ascending order : 3 9 10 13 Odd
7 min read
sort() vs. partial_sort() vs. nth_element() + sort() in C++ STL
In this article, we will discuss the difference between sort(), partial_sort(), and nth_element()+sort(). Below is the illustration of the above functions: sort(): C++ STL provides a function sort() that sorts a list of element in O(N*log N) time. By default, sort() sorts an array in ascending order. Below is the program to illustrate sort(): // C+
4 min read
Selection Sort VS Bubble Sort
Not a valid contributionIn this, we will cover the comparison between Selection Sort VS Bubble Sort. The resources required by Selection Sort & Bubble Sort algorithms on the basis of Time and Space Complexity are as follows. Time Complexity - [Tex]O(n^2)[/Tex]Space Complexity - [Tex]O(1)[/Tex] Let’s dive deep into the working of these algorithm
13 min read
Sorting by combining Insertion Sort and Merge Sort algorithms
Insertion sort: The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.Advantages: Following are the advantages of insertion sort: If the size of the list to be sorted is small, insertion sort runs fasterInsertion sort takes O(N) time when eleme
2 min read
Radix Sort vs Bucket Sort
We have two standard sorting algorithms, named bucket sort and radix sort. They both share differences and similarities. Let’s explore some similarities, differences, advantages, and disadvantages here in more detail. Bucket Sort: Bucket sort is a sorting algorithm in which the elements are separated into several groups that are called buckets. Eac
6 min read
Difference between Comb Sort and Shell Sort
Comb Sort: The pre-processing stage of Comb Sort is similar to the Shell Sort method. Comb sort is a significant advancement over bubble sort, and it is accomplished by pre-processing the data by integrating the comparison of the components' step positions that are far apart from one another. It is a kind of comparison sorting algorithm. The major
10 min read
Practice Tags :
three90RightbarBannerImg