CareerCup

def sort_array array
	(0..array.length-1).step(2).each do |index|
		if index + 1 < array.length-1 and array[index] > array[index+1]
			swap array, index, index+1
		end
		if index + 2 < array.length-1 and array[index+1] < array[index+2]
			swap array, index+1, index+2
		end
	end
	array
end

def swap array, index, index2
	temp = array[index]
	array[index] = array[index2]
	array[index2] = temp
end

One bubble sort iteration:

void swap(int* x, int* y)
{
	int t = *x;
	*x = *y;
	*y = t;
}

void rearrange(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		if (i % 2 == 0)
		{
			if (arr[i] > arr[i+1])
				swap(arr + i, arr + i + 1);
		}
		else
		{
			if (arr[i+1] > arr[i])
				swap(arr + i, arr + i + 1);
		}
	}
}

Just iterate over array and fix this property if it's not true. Fixing the property at n'th step can't break property at n-1'th step since e.g. a[n-2] <= a[n-1] and suppose a[n - 1] <= a[n], then a[n-2] <= a[n] and we can replace a[n-1] with a[n]. Same for >=

def rearrange(arr):
    for i in xrange(len(arr) - 1):
        if i % 2 == 0:
            if not arr[i] <= arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:
            if not arr[i] >= arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]

def check_property(arr):
    good = True
    for i in xrange(len(arr) - 1):
        if i % 2 == 0:
            good &= arr[i] <= arr[i + 1]
        else:
            good &= arr[i] >= arr[i + 1]
        if not good:
            break
    return good

for example in [
    [1, 2, 3, 4],
    [0, 5, 1, 9, 6, -1],
    [2, 1],
    [0, 0, 0, 0, 1],
    [2, 1, 3, -1, 5, 2, 7]
]:
    rearrange(example)
    assert check_property(example)
    print example

i am not sure this is the correct or not but think about it.

1) assume array is {7,3,5,6,2,1,9,4,8}
2) sort the array {1,2,3,4,5,6,7,8,9}
3)re arrange like this {1,3,2,4,5,7,6,8,9}

u can do this by swapping array[1] with array[3], array[5] with array[6]...............

is A sorted already?

Sort array 0 1 2 3 4 5
Then swap each 2 elements starting from index 1 i.e. swap 1 with 2, 3 with 4 and so on
0 <= 2 >= 1 <= 4 >= 3 <= 5 <= 6

int[] rearrage(int[] a) {
		for(int i=0; i<a.Length-2; i++) {
			if(i % 2 == 0) {
				if(a[i] <= a[i+1])	swap(ref a[i+1], ref a[i]);
				else				swap(ref a[i], ref a[i+1]);
			}
			else {
				if(a[i] >= a[i+1])	swap(ref a[i+1], ref a[i]);
				else				swap(ref a[i], ref a[i+1]);
			}
		}
		return a;
	}

	void swap(ref int a, ref int b) {
		int temp = a;
		a = b;
		b = temp;
	}

If array is sorted... Print postfix of those elements.. Then it will be our answer..

Print post fix if array is sorted

def rearrange(arr):
    for i in xrange(len(arr) - 1):
        if i % 2 == 0:
            if not arr[i] <= arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:
            if not arr[i] >= arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]

def check_property(arr):
    good = True
    for i in xrange(len(arr) - 1):
        if i % 2 == 0:
            good &= arr[i] <= arr[i + 1]
        else:
            good &= arr[i] >= arr[i + 1]
        if not good:
            break
    return good

for example in [
    [1, 2, 3, 4],
    [0, 5, 1, 9, 6, -1],
    [2, 1],
    [0, 0, 0, 0, 1]
]:
    rearrange(example)
    assert check_property(example)
    print example

bool ascending = true;
    for (int i = 1; i < array.Length; i++) {
        if ((array[i] > array[i-1]) != ascending) {
            int tmp = array[i-1];
            array[i-1] = array[i];
            array[i] = tmp;
        }
        ascending = !ascending;
    }

void Reorder(vector<int>& A){ 
   if(!A.size()){
       cout<<"Empty Vector"<<endl;
   }   
   for(int i=1;i<A.size();i++){
       if(i%2 ==1 ){
           if(A[i]<A[i-1]){
               A[i] ^= A[i-1];
               A[i-1] ^= A[i];
               A[i] ^= A[i-1];
           }
       }
   }   
   for(int i=1;i<A.size();i++){
       if(i%2 ==1 && (i != A.size()-1)){
           if(A[i]<A[i+1]){
               A[i] ^= A[i+1];
               A[i+1] ^= A[i];
               A[i] ^= A[i+1];
           }
       }
   }   
}

I think this can be achieved through 2 passes which O(n) - even if given vector V is not sorted

Pass - 1) start with i=1. If i is odd and V[i]<V[i-1], swap values
Pass -2 ) Start with i=1. if ( i is odd and i!= V.size()-1) and V[i]<V[i+1], swap values

There's a pattern here. First, sort the integers using count sort(linear time). Then, use the pattern...

A0 <= A1
A2 <= A1

A2 <= A3
A4 <= A3

A4 <= A5
A6 <= A5

----
1 2 3 4 5 6

A0=1
A2=2
A1=3
-----
A3=5
A2=2
A4=4
-----
A5=6
A4=4
A6=5

A (n log n) approach. MakeHeap (in-place, linear time). Pop n/2 largest elements, and insert them in the even position of a new array. Insert the remaining elements into the odd positions.

Thanks for user smarthbehl sharing this problem. I believe I came up with a linear time constant space solution. Due to code complexity, my code uses recursive, hence it has stack space overhead. But one can convert it into a non-recursive one and get a constant space solution.
Assume elements are distinct. otherwise there may or may not be a problem.

pseudo-code:
median <- quickSelection(A); // linear time, A is bi-partitioned such that A[left elements]<A[medianIndex]=median<A[right elements];
while (leftPointer < medianIndex)
swap(A[leftPointer],A[rightPointer]);
leftPointer+=2; rightPointer-=2;
end;

code:

#include <ctime>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int* ZigZagArray(int A[], int n);

int main()
{
  srand(time(0));
  int N = rand()%20+1;
  int *A = new int [N];
  for (int i=0; i<N; i++)
  {
    A[i] = rand()%100;
    printf("%02d ",A[i]);
  }
  printf("\n");
  int *B = ZigZagArray(A, N);
  for (int i=0; i<N; i++)
  {
    printf("%02d ",B[i]);
  }
  printf("\n");
  delete [] A;
  delete [] B;

  return 0;
}

int quickSelect(int A[], int quantile, int L, int R)
{
  if (R-L==1)
    return L;
  int pivotID = L + rand()%(R-L);
  int pivot = A[pivotID];
  int l = L, r = R-1;
  A[pivotID] = A[R-1];
  while (l<r)
  {
    while ((l<r)&&(A[l]<=pivot))
      l++;
    if (l>=r)
      break;
    A[r--] = A[l];
    while ((l<r)&&(A[r]>pivot))
      r--;
    if (l>=r)
      break;
    A[l++] = A[r];
  }
  pivotID = l;
  A[pivotID] = pivot;
  if (pivotID==quantile)
    return pivotID;
  if (pivotID<quantile)
    return quickSelect(A,quantile,pivotID+1,R);
  else
    return quickSelect(A,quantile,L,pivotID);
}


int *ZigZagArray(int A[], int n)
{
  int *B = new int [n];
  for (int i=0; i<n; i++)
    B[i] = A[i];
  int medianI = quickSelect(B,n/2,0,n);
  int pivot = B[medianI];
  int l = 0, r = n-1-(n%2);
  while (l<medianI)
  {
    int k = B[l];
    B[l] = B[r];
    B[r] = k;
    l += 2; r -= 2;
  }
  return B;
}

recursive solution

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define SIZE 10

int arr[SIZE] = { 42, 19, 41, 33, 39, 96, 19, 24, 38, 96 };

void reArrange(int *arr, int i, int size){
	if (i == size) return;	
	int left = i % 2;
	int right = left;
	int mid = (left == 0) ? 1 : 0;
	if (mid){
		if (arr[i] > arr[i + 1]) swap(arr + i, arr + i + 1);
		if (arr[i + 1] < arr[i + 2]) swap(arr + i + 1, arr + i + 2);
	}
	else{
		if (arr[i] < arr[i + 1]) swap(arr + i, arr + i + 1);
		if (arr[i + 1] > arr[i + 2]) swap(arr + i + 1, arr + i + 2);
	}
	reArrange(arr, i + 1, size);
}
void swap(int *a, int *b){
	int temp = *a;
	*a = *b;
	*b = temp;
}
int main()
{
	reArrange(arr, 0, SIZE);
	return 0;
}

OutPut :: 19 42 33 41 39 96 19 38 24 96

Just find the max element for consecutive 3 elements and place it at even position.

static void weirdSorting(int[] arr){
		int max = 0;
		int temp = 0;
		for(int i=1;i<arr.length;i+=2){
			max = Ideone.findMax(arr,i);
			temp = arr[max];
			arr[max] = arr[i];
			arr[i] = temp;
		}
 
	}
	static int findMax(int[] arr, int i){
		int max = 0;
		if(i<arr.length-1){
				max = arr[i]>arr[i-1]? i:i-1;
				max = arr[i+1]>arr[max]? i+1:max;
		}else{
			max = arr[i]>arr[i-1]? i:i-1;
		}
			System.out.println(max +"max	");
		return max;
	}

Solution with O(N)

void arrangeArray(int[] array){
		
		for(int i=1; i<array.length; i=i+2){
			if(array[i-1]>array[i]){
				swap(array, i-1, i);				
			}
			if(i+1<array.length && array[i+1]>array[i]){
				swap(array, i, i+1);
			}
		}
	}
private void swap(int[] array, int i1, int i2) {
		int temp = array[i1];
		array[i1]= array[i2];
		array[i2]=temp;
		
	}

void arrangeArray(int[] array){
		
		for(int i=1; i<array.length; i=i+2){
			if(array[i-1]>array[i]){
				swap(array, i-1, i);				
			}
			if(i+1<array.length && array[i+1]>array[i]){
				swap(array, i, i+1);
			}
		}
	}

	private void swap(int[] array, int i1, int i2) {
		int temp = array[i1];
		array[i1]= array[i2];
		array[i2]=temp;
		
	}

#include<bits/stdc++.h>
using namespace std;
int main()
{
long int tc,t,i,n,p;
scanf("%d",&tc);
while(tc--)
{
scanf("%ld",&n);long int a[n];
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
//sort(a,a+n);
for(i=0;i<n-1;i++)
{
if(i%2==0)
{
if(a[i]>=a[i+1])
{
t=a[i];a[i]=a[i+1];a[i+1]=t;
}

}
else if(i%2!=0)
{
if(a[i]<=a[i+1])
{
p=a[i];a[i]=a[i+1];a[i+1]=p;
}
}
}
for(i=0;i<n;i++)
printf("%ld ",a[i]);
printf("\n");
}
return 0;
}

{#include<bits/stdc++.h>
using namespace std;
int main()
{
long int tc,t,i,n,p;
scanf("%d",&tc);
while(tc--)
{
scanf("%ld",&n);long int a[n];
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
//sort(a,a+n);
for(i=0;i<n-1;i++)
{
if(i%2==0)
{
if(a[i]>=a[i+1])
{
t=a[i];a[i]=a[i+1];a[i+1]=t;
}

}
else if(i%2!=0)
{
if(a[i]<=a[i+1])
{
p=a[i];a[i]=a[i+1];a[i+1]=p;
}
}
}
for(i=0;i<n;i++)
printf("%ld ",a[i]);
printf("\n");
}
return 0;
}}