Dada una array circular arr[] de tamaño N y dos enteros K y M , la tarea es ordenar M elementos de la array a partir del índice K .
Ejemplos:
Entrada: arr[] = {4, 1, 6, 5, 3}, K = 2, M = 3
Salida: 4 1 3 5 6
Explicación: Después de ordenar 3 elementos de la array a partir del índice 2, modifica arr[] a {4 , 1, 3, 5, 6}.Entrada: arr[] = {67, 2, 9, 7, 1}, K = 4, M = 3
Salida: 2 67 9 7 1
Explicación: Después de ordenar 3 elementos de array a partir del índice 4, modifica arr[] a {2 , 67, 9, 7, 1}.
Enfoque: La idea es intercambiar los elementos adyacentes en la array circular si los elementos de ellos no están en el orden correcto. Siga los pasos a continuación para resolver el problema dado:
- Recorre la array dada arr[] sobre el rango [0, M – 1] usando la variable i .
- Recorra la array arr[] nuevamente sobre el rango [K, K + M – 1] usando la variable j y si arr[j%n] es mayor que arr[(j + 1)%n] , entonces intercambie los pares adyacentes actuales de valores
- Después de los pasos anteriores, imprima la array arr[] .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4 1 3 5 6
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA