Alternative Sorting

Introduction

Alternative sorting is a format where the array is printed in a particular manner. It is important to note that it is not a Sorting technique as the name suggests but rather an array representation. 

In this article, we will discuss the problem of Alternative sorting along with its time complexity and auxiliary space.

Problem Statement

We have a given integer array of length N. Now, use the alternative sorting technique to rearrange and display the output array. The required output should look in such a manner that the largest element is positioned in the first position (index 0), and the smallest element is placed in the second position (index 1). Similarly, the second largest element is positioned at the third position (index 2), and second smallest element on the fourth (index 3), and so on.

Sample Examples

Example 1:

Example 2:

Approach

1. Sort the given array using any algorithm like merge sort, quick sort, etc., keeping in mind that the time complexity should be O(n log(n)).
2. Place two pointers in the array, first at the starting element (0th index) and the other at the last(n-1th index), representing the maximum and minimum.
3. Then alternatively, print elements pointed by two-pointers and move them toward each other.

Pseudocode

Input Array: 
myArr[] = {5, 3, 7, 1, 6, 0, 8, 9}
Sorted Array: 
MyArr[] = {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]);
}

Implementation

#include <iostream>
using namespace std;

//swap the elements
void swap(int *a, int *b) 
{
    int t = *a;
    *a = *b;
    *b = t;
}

// function to rearrange array
int partition(int array[], int low, int high) 
{
    int pivot = array[high];
    int i = (low - 1);

  // traverse each element of the array
  // compare them with the pivot
    for (int j = low; j < high; j++) 
    {
        if (array[j] <= pivot) 
        {
            i++;
            swap(&array[i], &array[j]);
        }
    }
  
  //now, swap pivot with the greater element at i
    swap(&array[i + 1], &array[high]);
    return (i + 1);
}

void sort(int array[], int low, int high) 
{
    if (low < high) 
    {
        // find the pivot element so
        // elements smaller than the pivot are on the left of the pivot
        // and elements greater than the pivot are on the right of the pivot
        int pi = partition(array, low, high);
    
        // recursive call on the left of the pivot
        sort(array, low, pi - 1);
    
        // recursive call on the right of pivot
        sort(array, pi + 1, high);
    }
}

// Function to perform Alternative Sorting
void alternateSort(int arr[], int n)
{
    // Sort the array by quick Sort
    sort(arr, 0, n-1);
 
    //Print the element in the alternative order
    int i = 0, j = n-1;
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }
    
    // If the total element in given array is odd 
    //print the last middle element.
    if (n % 2 != 0)
        cout << arr[i];
}

// function to print the array
void printArray(int array[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}
// Main
int main() {
  int arr[] = {8, 1, 12, 4, 6, 7, 10, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  alternateSort(arr, n);
}

You can also try this code with Online C++ Compiler

Run Code

Output

Time complexity

The time complexity of the given problem is O(n log(n)), where ‘n’ is the length of the array.

Space Complexity

The time complexity of the given problem is O(1).

Also see,  Rabin Karp Algorithm

Refer to know about :  Topological sort