ronith
6/2/2018 - 4:47 AM

Alternative Sorting

https://www.geeksforgeeks.org/alternative-sorting/

Given an array of integers, print the array in such a way that the first element is first maximum and second element is first minimum and so on.

Examples :

Input : arr[] = {7, 1, 2, 3, 4, 5, 6} Output : 7 1 6 2 5 3 4

Input : arr[] = {1, 6, 9, 4, 3, 7, 8, 2} Output : 9 1 8 2 7 3 6 4

An efficient solution involves following steps.

  1. Sort input array using a O(n Log n) algorithm.
  2. We maintain two pointers, one from beginning and one from end in sorted array. We alternatively print elements pointed by two pointers and move them toward each other.
Alternative Sorting.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/alternative-sorting/
#include <bits/stdc++.h>
using namespace std;

int merge(int a[], int l, int m, int r){
    int n1 = m-l+1, n2 = r-m;
    int b[n1],c[n2];
    memcpy(b,a+l,n1*sizeof(int));
    memcpy(c,a+m+1,n2*sizeof(int));

    int i = 0, j = 0, k = l;
    while(i<n1 && j < n2){
        if (b[i] < c[j])
            a[k++] = b[i++];
        else
            a[k++] = c[j++];
    }
    while (i < n1)
        a[k++] = b[i++];
    while (j < n2)
        a[k++] = c[j++];
}

int mergesort(int a[], int l, int r){
    if(r>l){
        int m = (l+r)/2;
        mergesort(a,l,m);
        mergesort(a,m+1,r);
        merge(a, l,m,r);
    }
}

int main(){
    int n;
    cout<<"Enter the no.of elements:";
    cin>>n;
    int a[n];
    cout<<"Enter the elements:";
    for (int i=0;i<n;i++)
        cin>>a[i];
    int c=0,b=n-1;


    mergesort(a,0,n-1);

    for (int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;

    int i = 0, j = n-1;
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }

    if (n % 2 != 0)
        cout << arr[i];
}