Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
The Algorithm of the Approach
4.
Explanation
5.
Implementation
5.1.
C++ Code
5.2.
Java Code
5.3.
Output
5.4.
Complexity Analysis
6.
Frequently Asked Questions
6.1.
Why does a data structure require an array?
6.2.
Is an array's length fixed?
6.3.
What are the advantages of using an array?
6.4.
In a data structure, what is a pointer?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

An array data structure, or simply an array, is a data structure in computer science that consists of a collection of items identified by at least one array index or key.

In this article, we will learn to reorder an array. We will follow a sequence of reordering. We have to place the smallest element in the first position of the array, the largest element in the second, the 2nd smallest element in the third position, the 2nd largest element in the fourth position, etc.

Let’s begin with an introduction to the problem statement.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Assume we are working with an integer array. The problem is that we need to sort this array so that the first element is the smallest, the second element is the largest, the third element is the second smallest, the fourth element is the second-largest, and so on.

Example

Input: Given the size of array n=5, and the array is arr[n] = [3,2,1,4,5].

Output: The output array would contain the elements [1,5,2,4,3].

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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);
    }
}

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 ArraysStackLinked ListStringsQueueHeap 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 -

Happy Reading!

Previous article
Rearrange array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i
Next article
Rearrange Array such that Even Positioned are Greater than Odd
Live masterclass