Dada una array arr[] de enteros, la tarea es organizarlos de una manera similar al movimiento de ida y vuelta de un péndulo sin usar ningún espacio adicional.
Arreglo de péndulo :
- El elemento mínimo de la lista de enteros debe estar en la posición central de la array.
- El número en orden ascendente al lado del mínimo, va a la derecha, el siguiente número más alto va a la izquierda del número mínimo y continúa.
- A medida que se alcanzan números más altos, uno va hacia un lado de manera similar a la de un péndulo.
Ejemplos:
Entrada: arr[] = {2, 3, 5, 1, 4}
Salida: 5 3 1 2 4
El elemento mínimo es 1, por lo que se mueve al medio.
El siguiente elemento superior 2 se mueve a la derecha del
elemento central mientras que el siguiente elemento superior 3 se
mueve a la izquierda del elemento central y
este proceso continúa.
Entrada: arr[] = {11, 2, 4, 55, 6, 8}
Salida: 11 6 2 4 8 55
Enfoque: En este artículo se ha discutido un enfoque que utiliza una array auxiliar . Aquí hay un enfoque sin usar espacio adicional:
- Ordenar la array dada.
- Mueva todo el elemento de posición impar en el lado derecho de la array.
- Invierta el elemento de la posición 0 a (n-1)/2 de la array.
Por ejemplo, sea arr[] = {2, 3, 5, 1, 4}.
La array ordenada será arr[] = {1, 2, 3, 4, 5}.
Después de mover todos los elementos de posición de índice impar a la derecha,
arr[] = {1, 3, 5, 2, 4} (1 y 3 son las posiciones de índice impar)
Después de invertir los elementos de 0 a (n – 1) / 2,
arr[] = {5, 3, 1, 2, 4} que es la array requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the Pendulum
// arrangement of the given array
void pendulumArrangement(int arr[], int n)
{
// Sort the array
sort(arr, arr + n);
int odd, temp, in, pos;
// pos stores the index of
// the last element of the array
pos = n - 1;
// odd stores the last odd index in the array
if (n % 2 == 0)
odd = n - 1;
else
odd = n - 2;
// Move all odd index positioned
// elements to the right
while (odd > 0) {
temp = arr[odd];
in = odd;
// Shift the elements by one position
// from odd to pos
while (in != pos) {
arr[in] = arr[in + 1];
in++;
}
arr[in] = temp;
odd = odd - 2;
pos = pos - 1;
}
// Reverse the element from 0 to (n - 1) / 2
int start = 0, end = (n - 1) / 2;
for (; start < end; start++, end--) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// Printing the pendulum arrangement
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 11, 2, 4, 55, 6, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
pendulumArrangement(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.Arrays;
import java.io.*;
class GFG {
// Function to print the Pendulum
// arrangement of the given array
static void pendulumArrangement(int arr[], int n)
{
// Sort the array
// sort(arr, arr + n);
Arrays.sort(arr);
int odd, temp, in, pos;
// pos stores the index of
// the last element of the array
pos = n - 1;
// odd stores the last odd index in the array
if (n % 2 == 0)
odd = n - 1;
else
odd = n - 2;
// Move all odd index positioned
// elements to the right
while (odd > 0) {
temp = arr[odd];
in = odd;
// Shift the elements by one position
// from odd to pos
while (in != pos) {
arr[in] = arr[in + 1];
in++;
}
arr[in] = temp;
odd = odd - 2;
pos = pos - 1;
}
// Reverse the element from 0 to (n - 1) / 2
int start = 0, end = (n - 1) / 2;
for (; start < end; start++, end--) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// Printing the pendulum arrangement
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 11, 2, 4, 55, 6, 8 };
int n = arr.length;
pendulumArrangement(arr, n);
}
}
// This code is contributed by akt_mit
Python3
# Python 3 implementation of the approach # Function to print the Pendulum # arrangement of the given array def pendulumArrangement(arr, n): # Sort the array arr.sort(reverse = False) # pos stores the index of # the last element of the array pos = n - 1 # odd stores the last odd index in the array if (n % 2 == 0): odd = n - 1 else: odd = n - 2 # Move all odd index positioned # elements to the right while (odd > 0): temp = arr[odd] in1 = odd # Shift the elements by one position # from odd to pos while (in1 != pos): arr[in1] = arr[in1 + 1] in1 += 1 arr[in1] = temp odd = odd - 2 pos = pos - 1 # Reverse the element from 0 to (n - 1) / 2 start = 0 end = int((n - 1) / 2) while(start < end): temp = arr[start] arr[start] = arr[end] arr[end] = temp start += 1 end -= 1 # Printing the pendulum arrangement for i in range(n): print(arr[i], end = " ") # Driver code if __name__ == '__main__': arr = [11, 2, 4, 55, 6, 8] n = len(arr) pendulumArrangement(arr, n) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the Pendulum
// arrangement of the given array
static void pendulumArrangement(int[] arr, int n)
{
// Sort the array
// sort(arr, arr + n);
Array.Sort(arr);
int odd, temp, p, pos;
// pos stores the index of
// the last element of the array
pos = n - 1;
// odd stores the last odd index in the array
if (n % 2 == 0)
odd = n - 1;
else
odd = n - 2;
// Move all odd index positioned
// elements to the right
while (odd > 0)
{
temp = arr[odd];
p = odd;
// Shift the elements by one position
// from odd to pos
while (p != pos)
{
arr[p] = arr[p + 1];
p++;
}
arr[p] = temp;
odd = odd - 2;
pos = pos - 1;
}
// Reverse the element from 0 to (n - 1) / 2
int start = 0, end = (n - 1) / 2;
for (; start < end; start++, end--)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// Printing the pendulum arrangement
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main()
{
int[] arr = { 11, 2, 4, 55, 6, 8 };
int n = arr.Length;
pendulumArrangement(arr, n);
}
}
// This code is contributed by ChitraNayal
PHP
<?php
// PHP implementation of the approach
// Function to print the Pendulum
// arrangement of the given array
function pendulumArrangement($arr, $n)
{
// Sort the array
sort($arr) ;
// pos stores the index of
// the last element of the array
$pos = $n - 1;
// odd stores the last odd index in the array
if ($n % 2 == 0)
$odd = $n - 1;
else
$odd = $n - 2;
// Move all odd index positioned
// elements to the right
while ($odd > 0)
{
$temp = $arr[$odd];
$in = $odd;
// Shift the elements by one position
// from odd to pos
while ($in != $pos)
{
$arr[$in] = $arr[$in + 1];
$in++;
}
$arr[$in] = $temp;
$odd = $odd - 2;
$pos = $pos - 1;
}
// Reverse the element from 0 to (n - 1) / 2
$start = 0;
$end = floor(($n - 1) / 2);
for (; $start < $end; $start++, $end--)
{
$temp = $arr[$start];
$arr[$start] = $arr[$end];
$arr[$end] = $temp;
}
// Printing the pendulum arrangement
for ($i = 0; $i < $n; $i++)
echo $arr[$i], " ";
}
// Driver code
$arr = array( 11, 2, 4, 55, 6, 8 );
$n = count($arr);
pendulumArrangement($arr, $n);
// This code is contributed by AnkitRai01
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print the Pendulum
// arrangement of the given array
function pendulumArrangement(arr, n)
{
// Sort the array
// sort(arr, arr + n);
arr.sort(function(a, b){return a - b});
let odd, temp, p, pos;
// pos stores the index of
// the last element of the array
pos = n - 1;
// odd stores the last odd index in the array
if (n % 2 == 0)
odd = n - 1;
else
odd = n - 2;
// Move all odd index positioned
// elements to the right
while (odd > 0)
{
temp = arr[odd];
p = odd;
// Shift the elements by one position
// from odd to pos
while (p != pos)
{
arr[p] = arr[p + 1];
p++;
}
arr[p] = temp;
odd = odd - 2;
pos = pos - 1;
}
// Reverse the element from 0 to (n - 1) / 2
let start = 0, end = parseInt((n - 1) / 2, 10);
for (; start < end; start++, end--)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
// Printing the pendulum arrangement
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
let arr = [ 11, 2, 4, 55, 6, 8 ];
let n = arr.length;
pendulumArrangement(arr, n);
</script>
Producción:
11 6 2 4 8 55
Complejidad de Tiempo : O(n 2 )
Espacio Auxiliar : O(1)