Alternative Sorting
Given an array of integers, print the array in such a way that the first element is first maximum and second element is first minimum and so on.
Examples :
Input : arr[] = {7, 1, 2, 3, 4, 5, 6} Output : 7 1 6 2 5 3 4 Input : arr[] = {1, 6, 9, 4, 3, 7, 8, 2} Output : 9 1 8 2 7 3 6 4
A simple solution is to first print maximum element, then minimum, then second maximum, and so on. Time complexity of this approach is O(n2).
An efficient solution involves following steps.
- Sort input array using a O(n Log n) algorithm.
- We maintain two pointers, one from beginning and one from end in sorted array. We alternatively print elements pointed by two pointers and move them toward each other.
Implementation:
C++
// C++ program to print an array in alternate // sorted manner. #include <bits/stdc++.h> using namespace std; // Function to print alternate sorted values void alternateSort( int arr[], int n) { // Sorting the array sort(arr, arr+n); // Printing the last element of array // first and then first element and then // second last element and then second // element and so on. int i = 0, j = n-1; while (i < j) { cout << arr[j--] << " " ; cout << arr[i++] << " " ; } // If the total element in array is odd // then print the last middle element. if (n % 2 != 0) cout << arr[i]; } // Driver code int main() { int arr[] = {1, 12, 4, 6, 7, 10}; int n = sizeof (arr)/ sizeof (arr[0]); alternateSort(arr, n); return 0; } |
Java
// Java program to print an array in alternate // sorted manner import java.io.*; import java.util.Arrays; class AlternativeString { // Function to print alternate sorted values static void alternateSort( int arr[], int n) { Arrays.sort(arr); // Printing the last element of array // first and then first element and then // second last element and then second // element and so on. int i = 0 , j = n- 1 ; while (i < j) { System.out.print(arr[j--] + " " ); System.out.print(arr[i++] + " " ); } // If the total element in array is odd // then print the last middle element. if (n % 2 != 0 ) System.out.print(arr[i]); } /* Driver program to test above functions */ public static void main (String[] args) { int arr[] = { 1 , 12 , 4 , 6 , 7 , 10 }; int n = arr.length; alternateSort(arr, n); } } /*This code is contributed by Prakriti Gupta*/ |
Python3
# Python 3 program to print an array # in alternate sorted manner. # Function to print alternate sorted # values def alternateSort(arr, n): # Sorting the array arr.sort() # Printing the last element of array # first and then first element and then # second last element and then second # element and so on. i = 0 j = n - 1 while (i < j): print (arr[j], end = " " ) j - = 1 print (arr[i], end = " " ) i + = 1 # If the total element in array is odd # then print the last middle element. if (n % 2 ! = 0 ): print (arr[i]) # Driver code arr = [ 1 , 12 , 4 , 6 , 7 , 10 ] n = len (arr) alternateSort(arr, n) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# program to print an array in alternate // sorted manner using System; class AlternativeString { // Function to print alternate sorted values static void alternateSort( int [] arr, int n) { Array.Sort(arr); // Printing the last element of array // first and then first element and then // second last element and then second // element and so on. int i = 0, j = n - 1; while (i < j) { Console.Write(arr[j--] + " " ); Console.Write(arr[i++] + " " ); } // If the total element in array is odd // then print the last middle element. if (n % 2 != 0) Console.WriteLine(arr[i]); } /* Driver program to test above functions */ public static void Main() { int [] arr = { 1, 12, 4, 6, 7, 10 }; int n = arr.Length; alternateSort(arr, n); } } // |
PHP
<?php // PHP program to print an array in // alternate sorted manner. // Function to print alternate // sorted values function alternateSort( $arr , $n ) { // Sorting the array sort( $arr ); // Printing the last element // of array first and then // first element and then second // last element and then second // element and so on. $i = 0; $j = $n - 1; while ( $i < $j ) { echo $arr [ $j --]. " " ; echo $arr [ $i ++]. " " ; } // If the total element in array // is odd then print the last // middle element. if ( $n % 2 != 0) echo $arr [ $i ]; } // Driver code $arr = array (1, 12, 4, 6, 7, 10); $n = sizeof( $arr ) / sizeof( $arr [0]); alternateSort( $arr , $n ); // This code is contributed by Mithun Kumar ?> |
Javascript
<script> // JavaScript program to print an array in alternate // sorted manner. // Function to print alternate sorted values function alternateSort(arr, n) { // Sorting the array console.log(arr); arr.sort( function (a, b) { return a - b; }); console.log(arr); // Printing the last element of array // first and then first element and then // second last element and then second // element and so on. var i = 0, j = n - 1; while (i < j) { document.write(arr[j--] + " " ); document.write(arr[i++] + " " ); } // If the total element in array is odd // then print the last middle element. if (n % 2 != 0) document.write(arr[i]); } // Driver code var arr = [1, 12, 4, 6, 7, 10]; var n = arr.length; alternateSort(arr, n); // This code is contributed by rdtank. </script> |
Output
12 1 10 4 7 6
Time Complexity: O(n Log n)
Auxiliary Space : O(1), since no extra space has been taken.
This article is contributed by Sachin Bisht.
Contact Us