Data Modelling & AI Data Structure & Algorithm

Sort M elements of given circular array starting from index K

23 June 2025

0

Given a circular array arr[] of size N and two integers K and M, the task is to sort M array elements starting from the index K.

Examples:

Input: arr[] = {4, 1, 6, 5, 3}, K = 2, M = 3
Output: 4 1 3 5 6
Explanation: After sorting 3 array elements starting from index 2 modifies arr[] to {4, 1, 3, 5, 6}.

Input: arr[] = {67, 2, 9, 7, 1}, K = 4, M = 3
Output: 2 67 9 7 1
Explanation: After sorting 3 array elements starting from index 4 modifies arr[] to {2, 67, 9, 7, 1}.

Naive Approach: The idea is to swap the adjacent elements in the circular array if the elements of them are not in the correct order. Follow the steps below to solve the given problem:

Traverse the given array arr[] over the range [0, M – 1] using the variable i.
- Traverse the array arr[] again over the range [K, K + M – 1] using the variable j and if arr[j%n] is greater than arr[(j + 1)%n] then swap the current adjacent pairs of values.
After the above steps, print the array arr[].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the circular array
void printCircularArray(int arr[], int n)
{
    // Print the array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}
 
// Function to sort m elements of diven
// circular array starting from index k
void sortCircularArray(int arr[], int n,
                       int k, int m)
{
    // Traverse M elements
    for (int i = 0; i < m; i++) {
 
        // Iterate from index k to k + m - 1
        for (int j = k; j < k + m - 1; j++) {
 
            // Check if the next element
            // in the circular array is
            // less than the current element
            if (arr[j % n]
                > arr[(j + 1) % n]) {
 
                // Swap current element
                // with the next element
                swap(arr[j % n], arr[(j + 1) % n]);
            }
        }
    }
 
    // Print the circular array
    printCircularArray(arr, n);
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 1, 6, 5, 3 };
    int K = 2, M = 3;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    sortCircularArray(arr, N, K, M);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
      
// Function to print the circular array
static void printCircularArray(int arr[], int n)
{
    // Print the array
    for (int i = 0; i < n; i++) {
        System.out.print(arr[i] + " ");
    }
}
  
// Function to sort m elements of diven
// circular array starting from index k
static void sortCircularArray(int arr[], int n,
                       int k, int m)
{
    // Traverse M elements
    for (int i = 0; i < m; i++) {
  
        // Iterate from index k to k + m - 1
        for (int j = k; j < k + m - 1; j++) {
  
            // Check if the next element
            // in the circular array is
            // less than the current element
            if (arr[j % n]
                > arr[(j + 1) % n]) {
  
                // Swap current element
                // with the next element
                int t = arr[j % n];
                arr[j % n] = arr[(j + 1) % n];
                arr[(j + 1) % n] = t;
            }
        }
    }
  
    // Print the circular array
    printCircularArray(arr, n);
}
  
// Driver Code
public static void main (String[] args)
{   
    int[] arr = { 4, 1, 6, 5, 3 };
    int K = 2, M = 3;
    int N = arr.length;
  
    // Function Call
    sortCircularArray(arr, N, K, M);
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
 
# Function to print the circular array
def printCircularArray(arr, n):
     
    # Print the array
    for i in range(n):
        print(arr[i], end = " ")
 
# Function to sort m elements of diven
# circular array starting from index k
def sortCircularArray(arr, n, k, m):
 
    # Traverse M elements
    for i in range(m):
 
        # Iterate from index k to k + m - 1
        for j in range(k, k + m - 1):
 
            # Check if the next element
            # in the circular array is
            # less than the current element
            if (arr[j % n] > arr[(j + 1) % n]):
 
                # Swap current element
                # with the next element
                arr[j % n], arr[(j + 1) % n] = (arr[(j + 1) % n], 
                                                arr[j % n])
                 
    # Print the circular array
    printCircularArray(arr, n)
     
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 4, 1, 6, 5, 3 ]
    K = 2
    M = 3
    N = len(arr)
     
    # Function Call
    sortCircularArray(arr, N, K, M)
 
# This code is contributed by AnkThon

C#

// C# program for the above approach
using System;
 
class GFG
{
          
    // Function to print the circular array
    static void printCircularArray(int []arr, int n)
    {
        // Print the array
        for (int i = 0; i < n; i++)
        {
            Console.Write(arr[i] + " ");
        }
    }
      
    // Function to sort m elements of diven
    // circular array starting from index k
    static void sortCircularArray(int []arr, int n,
                           int k, int m)
    {
       
        // Traverse M elements
        for (int i = 0; i < m; i++)
        {
      
            // Iterate from index k to k + m - 1
            for (int j = k; j < k + m - 1; j++) 
            {
      
                // Check if the next element
                // in the circular array is
                // less than the current element
                if (arr[j % n]
                    > arr[(j + 1) % n]) {
      
                    // Swap current element
                    // with the next element
                    int t = arr[j % n];
                    arr[j % n] = arr[(j + 1) % n];
                    arr[(j + 1) % n] = t;
                }
            }
        }
      
        // Print the circular array
        printCircularArray(arr, n);
    }
      
    // Driver Code
    public static void Main (string[] args)
    {   
        int[] arr = { 4, 1, 6, 5, 3 };
        int K = 2, M = 3;
        int N = arr.Length;
      
        // Function Call
        sortCircularArray(arr, N, K, M);
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to print the circular array
function printCircularArray(arr, n)
{
    // Print the array
    for (let i = 0; i < n; i++) {
        document.write(arr[i] + " ");
    }
}
 
// Function to sort m elements of diven
// circular array starting from index k
function sortCircularArray(arr, n, k, m)
{
    // Traverse M elements
    for (let i = 0; i < m; i++) {
 
        // Iterate from index k to k + m - 1
        for (let j = k; j < k + m - 1; j++) {
 
            // Check if the next element
            // in the circular array is
            // less than the current element
            if (arr[j % n]
                > arr[(j + 1) % n]) {
 
                // Swap current element
                // with the next element
                let t = arr[j % n];
                arr[j % n] = arr[(j + 1) % n];
                arr[(j + 1) % n] = t;
            }
        }
    }
 
    // Print the circular array
    printCircularArray(arr, n);
}
 
// Driver Code
    let arr = [ 4, 1, 6, 5, 3 ];
    let K = 2, M = 3;
    let N = arr.length;
 
    // Function Call
    sortCircularArray(arr, N, K, M);
     
// This code is contributed by Surbhi Tyagi.
 
</script>

Output

4 1 3 5 6

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach:

Step-by-step approach:

Create a new array of size M and copy the M elements starting from index K of the circular array arr[] to the new array.
Sort the new array.
Traverse the circular array arr[] from index K to index (K + M – 1) mod N and replace each element with the corresponding element in the sorted new array.
If K + M is greater than N, traverse the remaining elements of the new array and replace the corresponding elements in the circular array arr[].

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
void sortCircularArray(int arr[], int n, int k, int m) {
    // Create a new array of size M and copy the 
    // M elements starting from index K
    int* tempArr = new int[m];
    for (int i = 0; i < m; i++) {
        tempArr[i] = arr[(k + i) % n];
    }
 
    // Sort the new array
    sort(tempArr, tempArr + m);
 
    // Traverse the circular array and replace the 
    // corresponding elements with sorted elements
    for (int i = 0; i < m; i++) {
        arr[(k + i) % n] = tempArr[i];
    }
 
    // If K + M is greater than N, traverse the remaining elements of the new array
    // and replace the corresponding elements in the circular array arr[]
    if (k + m > n) {
        for (int i = m; i < n - k; i++) {
            arr[(k + i) % n] = tempArr[i - m];
        }
    }
}
 
 
int main() {
    int arr[] = {4, 1, 6, 5, 3};
    int K = 2, M = 3;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    sortCircularArray(arr, N, K, M);
 
    // Print the modified circular array
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
}

Java

import java.util.Arrays;
 
public class Main {
    public static void sortCircularArray(int[] arr, int n,
                                         int k, int m)
    {
        // Create a new array of size M and copy the
        // M elements starting from index K
        int[] tempArr = new int[m];
        for (int i = 0; i < m; i++) {
            tempArr[i] = arr[(k + i) % n];
        }
 
        // Sort the new array
        Arrays.sort(tempArr);
 
        // Traverse the circular array and replace the
        // corresponding elements with sorted elements
        for (int i = 0; i < m; i++) {
            arr[(k + i) % n] = tempArr[i];
        }
 
        // If K + M is greater than N, traverse the
        // remaining elements of the new array and replace
        // the corresponding elements in the circular array
        // arr[]
        if (k + m > n) {
            for (int i = m; i < n - k; i++) {
                arr[(k + i) % n] = tempArr[i - m];
            }
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 4, 1, 6, 5, 3 };
        int K = 2, M = 3;
        int N = arr.length;
 
        sortCircularArray(arr, N, K, M);
 
        // Print the modified circular array
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Python3

def sortCircularArray(arr, n, k, m):
    # Create a new array of size M and copy the
    # M elements starting from index K
    tempArr = [0] * m
    for i in range(m):
        tempArr[i] = arr[(k + i) % n]
 
    # Sort the new array
    tempArr.sort()
 
    # Traverse the circular array and replace the
    # corresponding elements with sorted elements
    for i in range(m):
        arr[(k + i) % n] = tempArr[i]
 
    # If K + M is greater than N, traverse the remaining elements of the new array
    # and replace the corresponding elements in the circular array arr[]
    if k + m > n:
        for i in range(m, n - k):
            arr[(k + i) % n] = tempArr[i - m]
 
 
if __name__ == '__main__':
    arr = [4, 1, 6, 5, 3]
    K = 2
    M = 3
    N = len(arr)
 
    sortCircularArray(arr, N, K, M)
 
    # Print the modified circular array
    for i in range(N):
        print(arr[i], end=" ")

C#

using System;
 
public class GFG {
    public static void SortCircularArray(int[] arr, int n,
                                         int k, int m)
    {
        // Create a new array of size M and copy the
        // M elements starting from index K
        int[] tempArr = new int[m];
        for (int i = 0; i < m; i++) {
            tempArr[i] = arr[(k + i) % n];
        }
 
        // Sort the new array
        Array.Sort(tempArr);
 
        // Traverse the circular array and replace the
        // corresponding elements with sorted elements
        for (int i = 0; i < m; i++) {
            arr[(k + i) % n] = tempArr[i];
        }
 
        // If K + M is greater than N, traverse the
        // remaining elements of the new array and replace
        // the corresponding elements in the circular array
        // arr[]
        if (k + m > n) {
            for (int i = m; i < n - k; i++) {
                arr[(k + i) % n] = tempArr[i - m];
            }
        }
    }
 
    public static void Main()
    {
        int[] arr = { 4, 1, 6, 5, 3 };
        int K = 2, M = 3;
        int N = arr.Length;
 
        SortCircularArray(arr, N, K, M);
 
        // Print the modified circular array
        for (int i = 0; i < N; i++) {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
    }
}

Javascript

function sortCircularArray(arr, n, k, m) {
    // Create a new array of size M and copy the 
    // M elements starting from index K
    let tempArr = [];
    for (let i = 0; i < m; i++) {
        tempArr[i] = arr[(k + i) % n];
    }
 
    // Sort the new array
    tempArr.sort((a, b) => a - b);
 
    // Traverse the circular array and replace the 
    // corresponding elements with sorted elements
    for (let i = 0; i < m; i++) {
        arr[(k + i) % n] = tempArr[i];
    }
 
    // If K + M is greater than N, traverse the remaining elements of the new array
    // and replace the corresponding elements in the circular array arr[]
    if (k + m > n) {
        for (let i = m; i < n - k; i++) {
            arr[(k + i) % n] = tempArr[i - m];
        }
    }
}
 
// Main function
let arr = [4, 1, 6, 5, 3];
let K = 2, M = 3;
let N = arr.length;
 
sortCircularArray(arr, N, K, M);
 
// Print the modified circular array
for (let i = 0; i < N; i++) {
    console.log(arr[i] + " ");
}

Output

4 1 3 5 6

Time Complexity: O(M log M), where M is the number of elements to be sorted.
Auxiliary Space: O(M), since we are creating a new array of size M to store the M elements to be sorted.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Sort M elements of given circular array starting from index K

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Google Translate is testing a more expansive look for your translations

I thought my Galaxy had it all — until this iPhone feature proved me wrong

This is how Google Maps will use Gemini during navigation

The Pixel 10 Pro Fold tips the scales on the Android Police podcast

EDITOR PICKS

Google Translate is testing a more expansive look for your translations

I thought my Galaxy had it all — until this iPhone feature proved me wrong

This is how Google Maps will use Gemini during navigation

POPULAR POSTS

Google Translate is testing a more expansive look for your translations

I thought my Galaxy had it all — until this iPhone feature proved me wrong

This is how Google Maps will use Gemini during navigation

POPULAR CATEGORY

ABOUT US

FOLLOW US