Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest

Problem Statement

Suppose you have an integer array. The problem “Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest, ..” asks to rearrange the array in such a way that the smallest number comes first and then the largest number, then second smallest and then the second largest and so on.

Example

arr[] = {1,4,6,2,3,8,9,7}

1 9 2 8 3 7 4 6

Explanation: The smallest number is 1 and the largest as 9, 2^nd smallest as 2 and 2^nd largest as 8, 3^rd smallest is 3 and the 3^rd largest is 7, 4th smallest is 3 and the 4th largest is 7. Thus the resultant output is arranged in the same way as told in the problem.

Algorithm to rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest

1. Sort the given array.
2. We have to use a temporary array, so declare one.
3. Set index to 0.
4. Traverse the array from left and from right, with i = 0 and j = n – 1 up the half of the array length.
    1. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
    2. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
5. Update the original array by storing the value of a temporary array to the original array.
6. At last, the original array should be printed.

Explanation

Given an array of integers. We have asked to rearrange the array in such a manner that the smallest and the largest number of the array should come first and second respectively. Then the 2^nd smallest and 2md largest number should come next respectively, then continuing it, the 3^rd smallest and 3^rd largest number should come next in order. In this sequence, we have to rearrange the array. We will be using an extra array to fulfill this requirement. Sort the array given so that every come in order of non-decreasing manner.

By sorting the array, we have the smallest number in one half and the largest number in another half within the array respectively. Suppose we have the number from 1 to 10, randomly stored in an array, and if sort them, then from 1 to 5 will be in the first half and 6 to 10 will be in the second half.

Similarly here, we can now traverse from the left and store the values into the array we created. Since we start from the left, there will be only the smallest element so we can insert that element into the temporary array. So in the first position, there is only the smallest element. Now move from right, since the array is sorted so that there should be the largest element so now we put that element into the temporary array. Our first smallest and largest is completed, now moving further as we have done previously we should move from left next element and store it to a temporary array and then from right side pick the second largest element an store it to an array, with this manner, we can achieve to the result we want. Now simply print that array.

Code

C++ code to rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest

#include<iostream>
#include<algorithm>

using namespace std;

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

    int temporaryArray[n];

    int Index = 0;

    for (int i = 0, j = n-1; i <= n / 2 ||j > n / 2; i++, j--)
    {
        temporaryArray[Index] = arr[i];
        Index++;
        temporaryArray[Index] = arr[j];
        Index++;
    }
    for (int i = 0; i < n; i++)
        arr[i] = temporaryArray[i];

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {1,4,6,2,3,8,9,7};
    int n = sizeof(arr) / sizeof(arr[0]);

    rearrangeInOrderSL(arr, n);

    return 0;
}

1 9 2 8 3 7 4 6

Java code to rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest

import java.util.Arrays;
class rearrangeArraySL
{
    public static void rearrangeInOrderSL(int arr[], int n)
    {
        Arrays.sort(arr);

        int[] temporaryArray = new int[n];

        int Index = 0;

        for (int i = 0, j = n-1; i <= n / 2 || j > n / 2; i++, j--)
        {
            if(Index < n)
            {
                temporaryArray[Index] = arr[i];
                Index++;
            }

            if(Index < n)
            {
                temporaryArray[Index] = arr[j];
                Index++;
            }
        }
        for (int i = 0; i < n; i++)
            arr[i] = temporaryArray[i];
    }
    public static void main(String args[])
    {
        int arr[] = {1,4,6,2,3,8,9,7};
        int n = arr.length;
        rearrangeInOrderSL(arr, n);

        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+" ");
    }
}

1 9 2 8 3 7 4 6

Complexity Analysis

Time Complexity

O(N log N) where “N” is the number of elements in the array. We have sorted the input due to which we have this time complexity.

Space Complexity

O(N) where “N” is the number of elements in the array. Merge sort itself takes O(N) space.