Home » Data Structure » Array Data Structure

Rearrange the array in order - smallest, largest, 2nd smallest, 2nd largest, so on

C++ implementation to rearrange the array in order - smallest, largest, 2nd smallest, 2nd largest, so on.
Submitted by Vikneshwar GK, on March 07, 2022

Consider an integer array, of size n. The task at hand is to arrange the array in such a way that the smallest element is at 0^th position, the largest element at 1^st position, 2^nd smallest element at 2^nd position, 2^nd largest element at 3^rd position, and so on.

Example:

Input:
array[]= {2, 5, 4, 1, 6, 3}

Output:
array[] = {1, 6, 2, 5, 3, 4} 

Input:
array[]= {5, 1, 4, 6, 3, 7, 9}

Output:
array[] = {1, 9, 3, 7, 4, 6, 5}

Solution: Using Sorting

This method involves sorting the array using an O(nlog(n)) algorithm. After sorting, use two pointers, namely min, and max, to point the smallest and largest elements in the array and then place them accordingly in a new array by incrementing the min pointer and decrementing the max pointer.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

void rearrangeArray(int array[], int length)
{
    // Sort the array
    sort(array, array + length);

    // temporary array
    int tempArray[length];
    // index to store elements in temporary array
    int arrayIndex = 0;

    // traverse the array
    int min = 0, max = length - 1;
    while (min <= length / 2 || max > length / 2) {
        tempArray[arrayIndex] = array[min];
        arrayIndex++;
        tempArray[arrayIndex] = array[max];
        arrayIndex++;

        min++;
        max--;
    }
    printArray(tempArray, length);
}

// Main function
int main()
{
    int array[100], N, k;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 3
Enter element 2: 1
Enter element 3: 5
Enter element 4: 4
Enter element 5: 2
Enter element 6: 6
1 6 2 5 3 4 

Time Complexity: O(nlog(n)), where n is the length of the array.