ADVERTISEMENT
ADVERTISEMENT

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[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.

ADVERTISEMENT
ADVERTISEMENT


Comments and Discussions!



ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.