Home » Data Structure » Array Data Structure

Alternative Sorting

Learn about the alternative sorting in data structure with the algorithm, pseudo code, example, and C++ program.
Submitted by Vikneshwar GK, on January 15, 2022

Introduction:

Alternative sorting is a display format where the array is printed in a specific order. It has to be noted that it is not a sorting technique as the name falsely suggests, but rather an array representation.

Provided with an integer array of size N, alternative sorting rearranges and displays the array in such a way that the largest element is placed on the first position (index 0) and the least element is placed on the second position (index 1). Likewise, the second largest element is placed on the third position (index 2), and second least element on the fourth (index 3), and so on.

Example:

Input:
test1[] = {5, 3, 7, 1, 6, 0, 8, 9}
Output:
9, 0, 8, 1, 7, 3, 6, 5

Input:
test2[] = {-5, -3, 7, -2, 8, 0, -4, 0}
Output:
{8, -5, 7, -4, 0, -3, 0, -2}

Algorithm

• Sort the given array using an algorithm with time complexity of O(n log(n)), such as Quick Sort, Merge Sort, etc.
• Place a couple of pointers, one on the 0^th index and the other on the n-1^th index, to represent the minimum and maximum elements in the array.
• Print the pointer elements where the maximum element is printed first followed by the minimum element.
• Move the pointers towards each other by implementing decrement and increment.
• Continue the process until the pointers meet or cross each other.

Pseudo Code:

Input Array: arr[] = {5, 3, 7, 1, 6, 0, 8, 9}
Sorted Array: arr[] = {0, 1, 3, 5, 6, 7, 8, 9}

int i=0, j=n-1;

while(i<j){
	print(arr[j--]+" ");
	print(arr[i++]+" ");
}
if(n%2 != 0){
    print(arr[i]);
}

C++ program to implement alternative sorting

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

// Function to perform Alternative Sorting
void alternativeSorting(int arr[], int n)
{
    // Sorting the array
    sort(arr, arr + n);

    // Printing the element in alternative order
    // Right-most element first
    // Left-most element second
    // so on
    int i = 0, j = n - 1;

    cout << "Alternative Sorted Array : ";
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }

    // If the total element in array is odd
    // then print the last middle element.
    if (n % 2 != 0)
        cout << arr[i];
}

// Main function
int main()
{
    int arr[100], n;
    
    cout << "Enter number of elements: ";
    cin >> n;

    for (int i = 0; i < n; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> arr[i];
    }
    
    alternativeSorting(arr, n);
    
    return 0;
}

Output:

RUN 1:
Enter number of elements: 8
Enter element 1: 5
Enter element 2: 3
Enter element 3: 7
Enter element 4: 1
Enter element 5: 6
Enter element 6: 0
Enter element 7: 8
Enter element 8: 9
Alternative Sorted Array : 9 0 8 1 7 3 6 5 

RUN 2:
Enter number of elements: 9
Enter element 1: -5
Enter element 2: -3
Enter element 3: 7
Enter element 4: -2
Enter element 5: 8
Enter element 6: 0
Enter element 7: 0
Enter element 8: -4
Enter element 9: 1
Alternative Sorted Array : 8 -5 7 -4 1 -3 0 -2 0