×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

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.


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.