Sort a nearly sorted (or K sorted) array

Last Updated : 12 Apr, 2023

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.

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}

Sort a nearly sorted (or K sorted) array using insertion sort:

To solve the problem follow the below idea:

We can use insertion sort 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(N²) to O(NK).

Follow the below steps to solve the problem:

Iterate from arr[1] to arr[N] over the array.
Compare the current element (key) to its predecessor.
If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Below is the implementation of the above approach:

C++

/* C++ Function to sort an array using insertion sort*/
 
#include <bits/stdc++.h>
using namespace std;
 
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;
    }
   
  for(int i=0; i<size; i++)
      cout<<A[i]<<" ";
   
  cout<<endl;
}
 
int main()
{
      int A[] = {6, 5, 3, 2, 8, 10, 9};
      int size = 7;
      insertionSort(A, size);    
   
    return 0;
}
 
// This code is contributed by Shivani

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;
    }
}

Python3

# 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

Time Complexity: O(N*K), The inner loop will run at most K times. To move every element to its correct place, at most K elements need to be moved.
Auxiliary Space: O(1)

Another Approach:

In this modified algorithm, we only shift elements to the right if the current element is more than k positions away from its correct position. This optimization takes advantage of the fact that the elements are already nearly sorted and reduces the number of operations performed, resulting in a faster sorting algorithm for nearly sorted arrays.

C++

#include <bits/stdc++.h>
using namespace std;
  
void sortNearlySortedArray(int A[], int size, int k)
{
    int i, key, j;
    for (i = 1; i < size; i++) {
        key = A[i];
        j = i - 1;
  
        /* Check if the previous element is greater than the current
           element, and shift elements to the right until the correct
           position is found, but only if the current element is more
           than k positions away from its correct position */
        while (j >= max(0, i - k) && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
    
    for(int i=0; i<size; i++)
        cout<<A[i]<<" ";
    
    cout<<endl;
}
  
int main()
{
    int A[] = {2, 6, 3, 12, 56, 8};
    int size = 6;
    int k = 3;
    sortNearlySortedArray(A, size, k);   
    
    return 0;
}

Java

import java.util.Scanner;
 
class Main {
    static void sortNearlySortedArray(int A[], int size, int k) {
        int i, key, j;
        for (i = 1; i < size; i++) {
            key = A[i];
            j = i - 1;
  
            // Check if the previous element is greater than the current
            // element, and shift elements to the right until the correct
            // position is found, but only if the current element is more
            // than k positions away from its correct position
            while (j >= Math.max(0, i - k) && A[j] > key) {
                A[j + 1] = A[j];
                j--;
            }
            A[j + 1] = key;
        }
 
        // Print the sorted array
        for(i=0; i<size; i++)
            System.out.print(A[i] + " ");
    }
 
    public static void main(String[] args) {
        int A[] = {2, 6, 3, 12, 56, 8};
        int size = 6;
        int k = 3;
        sortNearlySortedArray(A, size, k);   
    }
}

Python3

def sortNearlySortedArray(A, size, k):
    for i in range(1, size):
        key = A[i]
        j = i - 1
 
        # Check if the previous element is greater than the current
        # element, and shift elements to the right until the correct
        # position is found, but only if the current element is more
        # than k positions away from its correct position
        while j >= max(0, i - k) and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key
 
    for i in range(size):
        print(A[i], end=' ')
 
    print()
 
# Driver Code
A = [2, 6, 3, 12, 56, 8]
size = 6
k = 3
sortNearlySortedArray(A, size, k)

C#

// C# code for the approach
 
using System;
 
public class GFG {
      // Function to sort a nearly sorted (or K sorted) array
    public static void
    SortNearlySortedArray(int[] arr, int size, int k)
    {
        int i, key, j;
        for (i = 1; i < size; i++) {
            key = arr[i];
            j = i - 1;
 
            // Check if the previous element is greater than
            // the current
            // element, and shift elements to the right
            // until the correct position is found, but only
            // if the current element is more than k
            // positions away from its correct position
            while (j >= Math.Max(0, i - k)
                   && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
 
            arr[j + 1] = key;
        }
       
        // Print the sorted array
        for (i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
   
    // Driver Code
    public static void Main(string[] args) {
          // Input array
        int[] arr = { 10, 9, 8, 7, 4, 70, 60, 50 };
        int size = 8;
        int k = 4;
       
          // Function Call
        SortNearlySortedArray(arr, size, k);
    }
}

Javascript

function sortNearlySortedArray(A, size, k) {
    let i, key, j;
    for (i = 1; i < size; i++) {
        key = A[i];
        j = i - 1;
 
        // Check if the previous element is greater than the current
        // element, and shift elements to the right until the correct
        // position is found, but only if the current element is more
        // than k positions away from its correct position
        while (j >= Math.max(0, i - k) && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
    }
 
    // Print the sorted array
    console.log(A.join(" "));
}
 
const A = [2, 6, 3, 12, 56, 8];
const size = 6;
const k = 3;
sortNearlySortedArray(A, size, k);

Output

2 3 6 8 12 56

Time complexity: The time complexity of the sortNearlySortedArray function is O(nk) because in the worst case scenario, each element of the array may need to be compared to k elements on its left to find its correct position.

Auxiliary Space: The space complexity of this function is O(1), because only a constant amount of extra space is required, regardless of the size of the input array.

Sort a nearly sorted (or K sorted) array using heap:

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++

// A STL based C++ program to sort a nearly sorted array.
#include <bits/stdc++.h>
using namespace std;
 
// Given an array of size n, where every element
// is k away from its target position, sorts the
// array in O(n logk) time.
void sortK(int arr[], int n, int k)
{
 
    // Insert first k+1 items in a priority queue (or min
    // heap)
    //(A O(k) operation). We assume, k < n.
    // if size of array = k i.e k away from its target
    // position then
    int size;
    size = (n == k) ? k : k + 1;
    priority_queue<int, vector<int>, greater<int> > pq(
        arr, arr + size);
 
    // i is index for remaining elements in arr[] and index
    // is target index of for current minimum element in
    // Min Heap 'pq'.
    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++] = pq.top();
        pq.pop();
        pq.push(arr[i]);
    }
 
    while (pq.empty() == false) {
        arr[index++] = pq.top();
        pq.pop();
    }
}
 
// A utility function to print array elements
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
// Driver code
int main()
{
    int k = 3;
    int arr[] = { 2, 6, 3, 12, 56, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    sortK(arr, n, k);
 
    printArray(arr, n);
 
    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)

Python3

# 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

Time Complexity: O(K) + O(m * log(k)) , where M = N – K
Auxiliary Space: O(K)

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.

Sort a nearly sorted (or K sorted) array using Quick-Sort:

To solve the problem follow the below idea:

The algorithm uses quick sort but changes the partition function in 2 ways.

Selects the pivot element as the middle element instead of the first or last element.

Scans the array from max(low, mid – k) to min(mid + k, high) instead of low to high.

The middle element is chosen as the pivot for diving the array into almost 2 halves for logarithmic time complexity

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
int sort(vector<int>& array, int l, int h, int k)
{
    int mid
        = l + (h - l) / 2; // Choose middle element as pivot
    int i = max(l, mid - k), j = i,
        end = min(mid + k, h); // Set appropriate range
    swap(array[mid],
         array[end]); // Swap middle and last element to
                      // avoid extra complications
    while (j < end) {
        if (array[j] < array[end]) {
            swap(array[i++], array[j]);
        }
        j = j + 1;
    }
    swap(array[end], array[i]);
    return i;
}
 
void ksorter(vector<int>& array, int l, int h, int k)
{
    if (l < h) {
        int q = sort(array, l, h, k);
        ksorter(array, l, q - 1, k);
        ksorter(array, q + 1, h, k);
    }
}
 
// Driver code
int main()
{
    vector<int> array(
        { 3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12 });
    int k = 3;
    cout << "Array before K sort\n";
    for (int& num : array)
        cout << num << ' ';
    cout << endl;
   
      // Function call
    ksorter(array, 0, array.size() - 1, k);
    cout << "Array after K sort\n";
    for (int& num : array)
        cout << num << ' ';
    return 0;
}

Java

// Java program for above approach
import java.io.*;
import java.util.*;
 
class GFG {
    public static int sort(ArrayList<Integer> arr, int l,
                           int h, int k)
    {
        int mid
            = l
              + (h - l)
                    / 2; // choose middle element as pivot
        int i = Math.max(l, mid - k), j = i,
            end = Math.min(mid + k,
                           h); // set appropriate ranges
        Collections.swap(
            arr, end, mid); // swap middle and last element
                            // to avoid extra complications
        while (j < end) {
            if (arr.get(j) < arr.get(end)) {
                Collections.swap(arr, j, i++);
            }
            j = j + 1;
        }
        Collections.swap(arr, end, i);
        return i;
    }
 
    public static void ksorter(ArrayList<Integer> arr,
                               int l, int h, int k)
    {
        if (l < h) {
            int q = sort(arr, l, h, k);
            ksorter(arr, l, q - 1, k);
            ksorter(arr, q + 1, h, k);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        ArrayList<Integer> arr = new ArrayList<>(List.of(
            3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12));
        int k = 3;
        int N = arr.size();
 
        System.out.println("Array before K sort\n");
        System.out.println(arr);
        System.out.println("\n");
 
        ksorter(arr, 0, N - 1, k);
 
        System.out.println("Array after K sort\n");
        System.out.println(arr);
    }
}
// this code is contributed by aditya942003patil

Python

# Python program for the above approach
def sort(array, l, h, k):
    mid = l + (h - l) // 2 # Choose middle element as pivot
    i = max(l, mid - k)
    j = i
    end = min(mid + k, h) # Set appropriate range
    array[mid], array[end] = array[end], array[mid] # Swap middle and last element to avoid extra complications
    while j < end:
        if array[j] < array[end]:
            array[i], array[j] = array[j], array[i]
            i += 1
        j += 1
    array[end], array[i] = array[i], array[end]
    return i
 
def ksorter(array, l, h, k):
    if l < h:
        q = sort(array, l, h, k)
        ksorter(array, l, q - 1, k)
        ksorter(array, q + 1, h, k)
 
# Driver code
array = [3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12]
k = 3
print("Array before K sort")
print(array)
 
# Function call
ksorter(array, 0, len(array) - 1, k)
print("Array after K sort")
print(array)
 
# This code is contributed by aadityamaharshi21.

C#

// C# program for above approach
using System;
 
public class GFG {
    public static void
    swap(int[] array, int i,
         int j) // function to swap two numbers
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static int sort(int[] array, int l, int h, int k)
    {
        int mid
            = l
              + (h - l)
                    / 2; // choose middle element as pivot
        int i = Math.Max(l, mid - k), j = i,
            end = Math.Min(mid + k,
                           h); // set appropriate ranges
        swap(array, end,
             mid); // swap middle and last element to avoid
                   // extra complications
        while (j < end) {
            if (array[j] < array[end]) {
                swap(array, j, i++);
            }
            j = j + 1;
        }
        swap(array, end, i);
        return i;
    }
 
    public static void ksorter(int[] array, int l, int h,
                               int k)
    {
        if (l < h) {
            int q = sort(array, l, h, k);
            ksorter(array, l, q - 1, k);
            ksorter(array, q + 1, h, k);
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int[] array
            = { 3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12 };
        int k = 3;
        int N = array.Length;
 
        Console.WriteLine("Array before K sort\n");
        for (int i = 0; i < N; i++)
            Console.Write(array[i] + " ");
        Console.WriteLine("\n");
 
        ksorter(array, 0, N - 1, k);
 
        Console.WriteLine("Array after K sort\n");
        for (int i = 0; i < N; i++)
            Console.Write(array[i] + " ");
        Console.WriteLine("\n");
    }
}
// this code is contributed by Abhijeet Kumar(abhijeet19403)

Javascript

// JavaScript code for the above approach
function sort(array, l, h, k) {
    let mid = Math.floor(l + (h - l) / 2); // Choose middle element as pivot
    let i = Math.max(l, mid - k);
    let j = i;
    let end = Math.min(mid + k, h); // Set appropriate range
    [array[mid], array[end]] = [array[end], array[mid]]; // Swap middle and last element to avoid extra complications
    while (j < end) {
        if (array[j] < array[end]) {
            [array[i++], array[j]] = [array[j], array[i]];
        }
        j = j + 1;
    }
    [array[end], array[i]] = [array[i], array[end]];
    return i;
}
 
function ksorter(array, l, h, k) {
    if (l < h) {
        let q = sort(array, l, h, k);
        ksorter(array, l, q - 1, k);
        ksorter(array, q + 1, h, k);
    }
}
 
// Driver code
let array = [3, 3, 2, 1, 6, 4, 4, 5, 9, 7, 8, 11, 12];
let k = 3;
console.log("Array before K sort");
console.log(array);
 
// Function call
ksorter(array, 0, array.length - 1, k);
console.log("Array after K sort");
console.log(array);
 
// This code is contributed by adityamaharshi21

Output

Array before K sort
3 3 2 1 6 4 4 5 9 7 8 11 12 
Array after K sort
1 2 3 3 4 4 5 6 7 8 9 11 12

Time Complexity: O(N * Log N)
Auxiliary Space: O(Log N)

Please write comments if you find any of the above codes/algorithms incorrect, or find other ways to solve the same problem.

GeeksforGeeks

Improve

Previous Article

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

Sort n numbers in range from 0 to n^2 - 1 in linear time

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

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

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

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

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

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<

Sort an array where a subarray of a sorted array is in reverse order

Given an array of N numbers where a subarray is sorted in descending order and rest of the numbers in the array are in ascending order. The task is to sort an array where a subarray of a sorted array is in reversed order. Examples: Input: 2 5 65 55 50 70 90 Output: 2 5 50 55 65 70 90 The subarray from 2nd index to 4th index is in reverse order. So

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

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

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

Article Tags :

Practice Tags :