Sorting: Given an array, sort the elements alternatively

Problem Statement:

You are given an array, rearrange the array in such a way that first max, first min, second max, second min etc

Example:

Input : {1, 2, 3, 4, 5, 6, 7, 8}

Output: 8, 1, 7, 2, 6, 3, 5, 4

Solution :

Sort the array

Take 2 pointers, one from beginning and one from end in the sorted array.

Then alternatively print the values.

Time Complexity: O(n logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

void solution(int arr[], int n)
{
	sort(arr, arr+n);

	int i = 0, j = n-1;
	while (i < j) 
	{
		cout << arr[j--] << " ";
		cout << arr[i++] << " ";
	}

	if (n % 2 != 0)
		cout << arr[i];
}

int main()
{
	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};

	int n = sizeof(arr)/sizeof(arr[0]);
	
	solution(arr, n);

	return 0;
}

Output
————-

8 1 7 2 6 3 5 4