Rearrange an array in order - Smallest, Largest, 2nd Smallest, 2nd Largest and so on

The Algorithm of the Approach

The algorithm for the solution to the problem is as follows.

1. Sort the given input array.
2. We'll need a temporary array, so make one.
3. Set the index to zero.
4. With i = 0 and j = n – 1 up the half-length of the array, traverse the array from left to right.
   i. Transfer the value of arr [j] to temporary [index] and increase the index's value by one.
   ii. Save the value of arr [j] to the temporary [index] variable and increase the index's value by one.
5. Store the value of the temporary array to the original array to update the original array.
6. Print the original array at the end.

Explanation

Given an array of integers, solve the problem. We have to rearrange the array so that the smallest and largest numbers in the array are placed in the first and second positions, accordingly. Then, the second smallest and second largest numbers should come next, followed by the third lowest and third greatest numbers. We must reshuffle the array in this sequence. To meet this criterion, we'll use an additional array. Sort the array so that each item appears in a non-descending order.

(Image of the approach to array reordering)

We have the smallest number in one half of the array and the greatest number in the other half by sorting the array. We can now traverse from the left and store the data in the array we constructed in the same way. Because we're starting from the left, there will only be the smallest element, which we can put into the temporary array. As a result, the smallest element is in the first place. Since the array is ordered so that the largest element is at the top, we'll start from the right and insert that element into the temporary array. Similarly, we should pick the next element from the left and store it in a temporary array, pick the second largest element from the right, save it in an array, and go on till we traverse the whole array. Finally, we need to print the array.

Implementation

Now, let’s look at the implementation of the approach in C++ and Java. We have added the necessary comments in the codes to make you understand the codes better. Let’s see the implementation in C++ first.

C++ Code

//Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest, ..
#include <iostream>
#include <algorithm>
using namespace std;
int i=0, j=0;

// Function to rearrange array in order – smallest, largest, 2nd smallest, 2nd largest, ..
void rearrange(int arr[], int n)
{
    // Sort the array
    sort(arr, arr+n);
    int temp[n];
    
    // Find the number of pairs
    int cnt = n/2;
    int index = 0;
    
    // Copy the array in temp rearranged order - smallest, largest, 2nd smallest, 2nd largest, ..
    for (int i=0, j = n-1; i<cnt || j>=cnt; i++, j--)
    {
        temp[index] = arr[i];
        index++;
        temp[index] = arr[j];
        index++;
    }
    
    // Copy the temp array to arr
    for (int i=0; i<n; i++)
        arr[i] = temp[i];
        
    // Print the array
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}

// Driver program
int main()
{
    int n;
    cout << "Enter the number of elements: \n";
    cin >> n;
    int arr[n];
    cout << "Enter the elements: \n";
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    rearrange(arr, n); // call reorder function
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java Code

//Rearrange an array in order – smallest, largest, 2nd smallest, 2nd largest, so on
import java.util.*;
class arrayReorder
{
    // Function to rearrange array in order – smallest, largest, 2nd smallest, 2nd largest, ..
    static void rearrange(int arr[], int n)
    {
        int i=0,j=0;
        
        //sort the array
        Arrays.sort(arr);
        
        //define temp array
        int temp[] = new int[n];
        
        //define index
        int index = 0;
        int cnt = (n/2);
        
        //loop through the array
        for ( i = 0, j = n-1; i < n / 2 || j >= n / 2; i++, j--)
        {
            //handling i==j case
            if (i == j)
            {
                temp[index++] = arr[i];
            }
            else
            {
                //handling i<j case
                if (i < j)
                {
                    temp[index++] = arr[i];
                    temp[index++] = arr[j];
                }
                else
                {
                    //handling i>j case
                    temp[index++] = arr[j];
                    temp[index++] = arr[i];
                }
            }
        }
        
        //copy the temp array to the original array
        for (i=0; i<n; i++)
            arr[i] = temp[i];
            
        //print the array
        for (i=0; i<n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String args[])
    {
        System.out.println("Enter the number of elements:");
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
            int arr[] = new int[n];
            System.out.println("Enter the elements:");
            for (int i=0; i<n; i++)
                arr[i] = sc.nextInt();
            rearrange(arr, n);
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Complexity Analysis

Time Complexity: O (N log N), where "N" is the number of elements in the array. We have this runtime complexity because we have sorted the input using the built-in sorting of Java, which is the dual-pivot Quicksort, and the introsort built-in sorting method of C++. Both these sorts have O (N log N) time complexity.

Space Complexity: O (N), where “N” is the number of elements present in the array. Because the above program uses a temporary array which holds the data from the original array, the space complexity is O(N).

Frequently Asked Questions

Why does a data structure require an array?

Arrays are helpful in data structures for the following reasons: 

• Arrays are the ideal choice for storing several values in a single variable. 
• Arrays are more efficient in handling a large number of values quickly. 
• Arrays make it simpler to sort and search for values.
   

Is an array's length fixed?

An array is a container object that can hold a fixed number of values of the same type. When an array is constructed, its length is determined. Its length is fixed after it is created.
 

What are the advantages of using an array?

The index number in an array can be used to access the elements at random. For all of the elements in an array, memory is allocated in contiguous memory addresses. As a result, in the case of arrays, no additional RAM will be allocated. In arrays, this prevents memory overflow and shortages.
 

In a data structure, what is a pointer?

Pointers are variables that are used to keep track of where a value is stored in memory. The memory address is stored in a pointer to a location. Dereferencing is getting the value stored at a location that is referenced by a pointer.

Conclusion

In this article, we have discussed the data structure problem of rearranging an array in order – smallest, largest, 2nd smallest, 2nd largest, and so on and their implementation in Java and C++ programming languages.

We hope that this blog has helped you learn more about rearranging elements of an array by putting the smallest element in the first position, the highest element in the second position, the second smallest in the third position, and so on. If you want to continue learning more, check out our articles on Arrays, Stack, Linked List, Strings, Queue, Heap and Priority Queue. Please upvote this blog to show your love and help other students to find this article.

Look at our new Coding Ninjas Studio practice platform to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations and much more!

Recommended Problems -

• Rearrange Array Alternately
• Sum Of Two Arrays
• Merge K Sorted Arrays

Happy Reading!