# 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 0th position, the largest element at 1st position, 2nd smallest element at 2nd position, 2nd largest element at 3rd 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, 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.

Preparation

What's New

Top Interview Coding Problems/Challenges!