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.
// 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;
}
Output :
12 1 10 4 7 6
Time Complexity: O(n Log n)
Auxiliary Space : O(1)