Program to print an array in Pendulum Arrangement
Write a program to input a list of integers in an array and arrange them in a way similar to the to-and-fro movement of a Pendulum.
- The minimum element out of the list of integers, must come in center position of array.
- The number in the ascending order next to the minimum, goes to the right, the next higher number goes to the left of minimum number and it continues.
- As higher numbers are reached, one goes to one side in a to-and-fro manner similar to that of a Pendulum.
Examples:
Input : 1 3 2 5 4 Output :5 3 1 2 4 Explanation: The minimum element is 1, so it is moved to the middle. The next higher element 2 is moved to the right of the middle element while the next higher element 3 is moved to the left of the middle element and this process is continued. Input : 11 12 31 14 5 Output :31 12 5 11 14
The idea is to sort the array first. Once the array is sorted, use an auxiliary array to store elements one by one.
Implementation:
C++
// C++ program for pendulum arrangement of numbers #include <bits/stdc++.h> using namespace std; // Prints pendulum arrangement of arr[] void pendulumArrangement( int arr[], int n) { // sorting the elements sort(arr, arr+n); // Auxiliary array to store output int op[n]; // calculating the middle index int mid = (n-1)/2; // storing the minimum element in the middle // i is index for output array and j is for // input array. int j = 1, i = 1; op[mid] = arr[0]; for (i = 1; i <= mid; i++) { op[mid+i] = arr[j++]; op[mid-i] = arr[j++]; } // adjustment for when no. of elements is even if (n%2 == 0) op[mid+i] = arr[j]; // Printing the pendulum arrangement cout << "Pendulum arrangement:" << endl; for (i = 0 ; i < n; i++) cout << op[i] << " " ; cout << endl; } // Driver function int main() { //input Array int arr[] = {14, 6, 19, 21, 12}; // calculating the length of array A int n = sizeof (arr)/ sizeof (arr[0]); // calling pendulum function pendulumArrangement(arr, n); return 0; } |
Java
// Java program for pendulum arrangement of numbers import java.util.Arrays; class Test { // Prints pendulum arrangement of arr[] static void pendulumArrangement( int arr[], int n) { // sorting the elements Arrays.sort(arr); // Auxiliary array to store output int op[] = new int [n]; // calculating the middle index int mid = (n- 1 )/ 2 ; // storing the minimum element in the middle // i is index for output array and j is for // input array. int j = 1 , i = 1 ; op[mid] = arr[ 0 ]; for (i = 1 ; i <= mid; i++) { op[mid+i] = arr[j++]; op[mid-i] = arr[j++]; } // adjustment for when no. of elements is even if (n% 2 == 0 ) op[mid+i] = arr[j]; // Printing the pendulum arrangement System.out.println( "Pendulum arrangement:" ); for (i = 0 ; i < n; i++) System.out.print(op[i] + " " ); System.out.println(); } // Driver method public static void main(String[] args) { //input Array int arr[] = { 14 , 6 , 19 , 21 , 12 }; // calling pendulum function pendulumArrangement(arr, arr.length); } } |
Python3
# Python 3 program for pendulum # arrangement of numbers # Prints pendulum arrangement of arr[] def pendulumArrangement(arr, n): # sorting the elements arr.sort() # Auxiliary array to store output op = [ 0 ] * n # calculating the middle index mid = int ((n - 1 ) / 2 ) # storing the minimum # element in the middle # i is index for output # array and j is for # input array. j = 1 i = 1 op[mid] = arr[ 0 ] for i in range ( 1 ,mid + 1 ): op[mid + i] = arr[j] j + = 1 op[mid - i] = arr[j] j + = 1 # adjustment for when no. # of elements is even if ( int (n % 2 ) = = 0 ): op[mid + i] = arr[j] # Printing the pendulum arrangement print ( "Pendulum arrangement:" ) for i in range ( 0 ,n): print (op[i],end = " " ) # Driver function # input Array arr = [ 14 , 6 , 19 , 21 , 12 ] # calculating the length of array A n = len (arr) # calling pendulum function pendulumArrangement(arr, n) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# program for pendulum // arrangement of numbers using System; class Test { // Prints pendulum arrangement of arr[] static void pendulumArrangement( int []arr, int n) { // sorting the elements Array.Sort(arr); // Auxiliary array to store output int []op = new int [n]; // calculating the middle index int mid = (n - 1) / 2; // storing the minimum element in // the middle i is index for output // array and j is for input array. int j = 1, i = 1; op[mid] = arr[0]; for (i = 1; i <= mid; i++) { op[mid + i] = arr[j++]; op[mid - i] = arr[j++]; } // adjustment for when no. // of elements is even if (n % 2 == 0) op[mid + i] = arr[j]; // Printing the pendulum arrangement Console.Write( "Pendulum arrangement:" ); for (i = 0 ; i < n; i++) Console.Write(op[i] + " " ); Console.WriteLine(); } // Driver code public static void Main() { //input Array int []arr = {14, 6, 19, 21, 12}; // calling pendulum function pendulumArrangement(arr, arr.Length); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program for pendulum // arrangement of numbers // Prints pendulam arrangement of arr[] function pendulumArrangement( $arr , $n ) { // sorting the elements sort( $arr , $n ); sort( $arr ); // Auxiliary array to // store output $op [ $n ] = NULL; // calculating the // middle index $mid = floor (( $n - 1) / 2); // storing the minimum // element in the middle // i is index for output // array and j is for // input array. $j = 1; $i = 1; $op [ $mid ] = $arr [0]; for ( $i = 1; $i <= $mid ; $i ++) { $op [ $mid + $i ] = $arr [ $j ++]; $op [ $mid - $i ] = $arr [ $j ++]; } // adjustment for when no. // of elements is even if ( $n % 2 == 0) $op [ $mid + $i ] = $arr [ $j ]; // Printing the pendulum // arrangement echo "Pendulum arrangement:" ; for ( $i = 0 ; $i < $n ; $i ++) echo $op [ $i ], " " ; echo "\n" ; } // Driver Code //input Array $arr = array (14, 6, 19, 21, 12); // calculating the length // of array A $n = sizeof( $arr ); // calling pendulum function pendulumArrangement( $arr , $n ); // This code is contributed by nitin mittal. ?> |
Javascript
<script> // JavaScript program for pendulum // arrangement of numbers // Prints pendulam arrangement of arr[] function pendulumArrangement(arr, n) { // sorting the elements arr.sort( function (a, b) { return a - b; }); // Auxiliary array to store output var op = [...Array(n)]; // calculating the middle index var mid = parseInt((n - 1) / 2); // storing the minimum element in the middle // i is index for output array and j is for // input array. var j = 1, i = 1; op[mid] = arr[0]; for (i = 1; i <= mid; i++) { op[mid + i] = arr[j++]; op[mid - i] = arr[j++]; } // adjustment for when no. of elements is even if (n % 2 == 0) op[mid + i] = arr[j]; // Printing the pendulum arrangement document.write( "Pendulum arrangement:<br>" ); for (i = 0; i < n; i++) document.write(op[i] + " " ); document.write( "<br>" ); } // Driver function //input Array var arr = [14, 6, 19, 21, 12]; // calculating the length of array A var n = arr.length; // calling pendulum function pendulumArrangement(arr, n); </script> |
Output
Pendulum arrangement: 21 14 6 12 19
Time Complexity: O(n*log(n)) where n is the size of the array.
Auxiliary Space: O(n)