AMD Interview Question
AnalystsCountry: India
Interview Type: In-Person
public class MinMax {
public static void main(String args[]){
int[] array = {1,2,3,4,5,6,7};
Arrays.sort(array);
int minMaxArray[] = new int[array.length];
for(int index =0,firstPos =0, lastPos = array.length-1;index<array.length;index++){
if(index % 2 != 0){
minMaxArray[index] = array[firstPos];
firstPos++;
}
else{
minMaxArray[index] = array[lastPos];
lastPos--;
}
}
System.out.println("Input:" + Arrays.toString(array));
System.out.println("Output:" + Arrays.toString(minMaxArray));
}
}
Formatted code:
public class MinMax {
public static void main( String args[] ){
int[] array = { 1,2,3,4,5,6,7 };
Arrays.sort( array );
int minMaxArray[] = new int[ array.length ];
for( int index = 0, firstPos = 0, lastPos = array.length - 1; index < array.length;index++ ){
if( index % 2 != 0 ){
minMaxArray[ index ] = array[ firstPos ];
firstPos++;
}
else {
minMaxArray[ index ] = array[ lastPos ];
lastPos--;
}
}
System.out.println( "Input:" + Arrays.toString( array ) );
System.out.println( "Output:" + Arrays.toString( minMaxArray ) );
}
}
This code solve the problem in O(log(n))
public static void main(String[] args) {
int [] input = {1,2,3,4,5,6,7};
int [] output = function1(input);
}
public static int[] function1( int [] input){
int n = input.length;
if (n<=3){ //BASE CASE
for (int i = 0; i<n; i++){
if (input[i]>input[0]){ swap(input,i,0);}
if (input[i]<input[1]){ swap(input,i,1);}
}
return input;
}
else{ //RECURSIVE
int p = n/2;
int [] a = function1(Arrays.copyOfRange(input, 0, p));
int [] b = function1(Arrays.copyOfRange(input, p, n));
if (b[0] > a[0]){
int temp = a[0];
a[0] = b[0];
b[0] = temp;
}
if (b[1] < a[1]){
int temp = a[1];
a[1] = b[1];
b[1] = temp;
}
int [] result = Arrays.copyOf(a, a.length + b.length);
System.arraycopy(b, 0, result, a.length, b.length);
return result;
}
}
public static void swap(int [] array, int pos1, int pos2){
int temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
}
This code solve the problem in O(log(n))
public static void main(String[] args) {
int [] input = {1,2,3,4,5,6,7};
int [] output = function1(input);
}
public static int[] function1( int [] input){
int n = input.length;
if (n<=3){ //BASE CASE
for (int i = 0; i<n; i++){
if (input[i]>input[0]){ swap(input,i,0);}
if (input[i]<input[1]){ swap(input,i,1);}
}
return input;
}
else{ //RECURSIVE
int p = n/2;
int [] a = function1(Arrays.copyOfRange(input, 0, p));
int [] b = function1(Arrays.copyOfRange(input, p, n));
if (b[0] > a[0]){
int temp = a[0];
a[0] = b[0];
b[0] = temp;
}
if (b[1] < a[1]){
int temp = a[1];
a[1] = b[1];
b[1] = temp;
}
int [] result = Arrays.copyOf(a, a.length + b.length);
System.arraycopy(b, 0, result, a.length, b.length);
return result;
}
}
public static void swap(int [] array, int pos1, int pos2){
int temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
}
This code solve the problem in O(log(n))
public static void main(String[] args) {
int [] input = {1,2,3,4,5,6,7};
int [] output = function1(input);
}
public static int[] function1( int [] input){
int n = input.length;
if (n<=3){ //BASE CASE
for (int i = 0; i<n; i++){
if (input[i]>input[0]){ swap(input,i,0);}
if (input[i]<input[1]){ swap(input,i,1);}
}
return input;
}
else{ //RECURSIVE
int p = n/2;
int [] a = function1(Arrays.copyOfRange(input, 0, p));
int [] b = function1(Arrays.copyOfRange(input, p, n));
if (b[0] > a[0]){
int temp = a[0];
a[0] = b[0];
b[0] = temp;
}
if (b[1] < a[1]){
int temp = a[1];
a[1] = b[1];
b[1] = temp;
}
int [] result = Arrays.copyOf(a, a.length + b.length);
System.arraycopy(b, 0, result, a.length, b.length);
return result;
}
}
public static void swap(int [] array, int pos1, int pos2){
int temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
}
c# implementation.
DP, D&C.
O(n*logn).
using System;
namespace ZigZagArrange {
public static class Program {
static public int[] ZigZagArrange( int[] arr ) {
if ( arr.Length < 2 ) { return arr; }
int[] part1 = GetReArrangedPart1( arr );
int[] part2 = GetPart2AsIs( arr, part1.Length );
if ( part2 != null ) {
part2 = ZigZagArrange( part2 );
}
return Concat( part1, part2 );
}
static private int[] GetReArrangedPart1( int[] arr ) {
int i = 1;
while( arr[ 0 ] == arr[ i ] && i < arr.Length - 1 ) { i++; } // handle duplicates
int fMinI = arr[ 0 ] > arr[ i ] ? i : 0 ;
int fMaxI = arr[ 0 ] < arr[ i ] ? i : 0 ;
if ( fMaxI == 0 ) {
fMinI = getfMinI( arr, i );
} else {
fMaxI = getfMaxI( arr, i );
}
int[] res = new int[ Math.Abs( fMaxI - fMinI ) + 1 ];
for ( i = 0; i <= Math.Max( fMinI, fMaxI ); i++ ) {
res[ i ] = arr[ i ];
}
res = ReArrange( res, fMaxI, fMinI );
return res;
}
private static int[] ReArrange( int[] arr, int fMaxI, int fMinI ) {
int[] res = new int[ arr.Length ];
int i = 0;
while ( i < res.Length ) {
res[ i++ ] = arr[ fMaxI ];
if ( i >= res.Length ) { break; }
res[ i++ ] = arr[ fMinI ];
fMaxI = fMaxI > fMinI ? fMaxI - 1 : fMaxI + 1;
fMinI = fMinI > fMaxI ? fMinI - 1 : fMinI + 1;
}
return res;
}
private static int[] Concat( int[] part1, int[] part2 ) {
if ( part1 == null ) { return part2; }
if ( part2 == null ) { return part1; }
int[] res = new int[ part1.Length + part2.Length ];
for ( int i = 0; i < part1.Length; i++ ) {
res[ i ] = part1[ i ];
}
for ( int i = 0; i < part2.Length; i++ ) {
res[ part1.Length + i ] = part2[ i ];
}
return res;
}
private static int[] GetPart2AsIs( int[] arr, int p2Length ) {
if ( arr.Length == p2Length ) { return null; }
int[] res = new int[ arr.Length - p2Length ];
for ( int i = p2Length; i < arr.Length; i++ ) {
res[ i - p2Length ] = arr[ i ];
}
return res;
}
static private int getfMinI( int[] arr, int i ) {
if ( i == arr.Length - 1 ) { return i; }
if ( arr[ i ] >= arr[ i + 1 ] ) {
return getfMinI( arr, i + 1 );
}
return i;
}
static private int getfMaxI( int[] arr, int i ) {
if ( i == arr.Length - 1 ) { return i; }
if ( arr[ i ] <= arr[ i + 1 ] ) {
return getfMaxI( arr, i + 1 );
}
return i;
}
static void Main(string[] args) { }
}
}
public class MaxMin {
public static void main(String[] args) {
// TODO Auto-generated method stub
int max=0;
int min=0;
int a[]= {5,6,7,1,3,4};
if(a[0] > a[1]) {
max = a[0];
min =a[1];
} else {
max = a[1];
min = a[0];
}
for(int i=0;i<a.length-1;i++) {
if(a[i] > max) {
max = a[i];
} if(a[i] < min) {
min = a[i];
}
}
int b[] = new int[a.length];
int i = 0;
int j=2;
b[0] = max;
b[1] = min;
while (i<a.length && j <b.length) {
if(a[i] != max && a[i]!=min) {
b[j] = a[i];
i++;j++;
}else {
i++;
}
}
for(int k=0;k<b.length;k++) {
System.out.println(b[k]);
}
//System.out.println(max + " " + min);
}
}
public class MaxMin {
public static void main(String[] args) {
// TODO Auto-generated method stub
int max=0;
int min=0;
int a[]= {5,6,7,1,3,4};
if(a[0] > a[1]) {
max = a[0];
min =a[1];
} else {
max = a[1];
min = a[0];
}
for(int i=0;i<a.length-1;i++) {
if(a[i] > max) {
max = a[i];
} if(a[i] < min) {
min = a[i];
}
}
int b[] = new int[a.length];
int i = 0;
int j=2;
b[0] = max;
b[1] = min;
while (i<a.length && j <b.length) {
if(a[i] != max && a[i]!=min) {
b[j] = a[i];
i++;j++;
}else {
i++;
}
}
for(int k=0;k<b.length;k++) {
System.out.println(b[k]);
}
//System.out.println(max + " " + min);
}
}
public class MaxMin {
public static void main(String[] args) {
// TODO Auto-generated method stub
int max=0;
int min=0;
int a[]= {5,6,7,1,3,4};
if(a[0] > a[1]) {
max = a[0];
min =a[1];
} else {
max = a[1];
min = a[0];
}
for(int i=0;i<a.length-1;i++) {
if(a[i] > max) {
max = a[i];
} if(a[i] < min) {
min = a[i];
}
}
int b[] = new int[a.length];
int i = 0;
int j=2;
b[0] = max;
b[1] = min;
while (i<a.length && j <b.length) {
if(a[i] != max && a[i]!=min) {
b[j] = a[i];
i++;j++;
}else {
i++;
}
}
for(int k=0;k<b.length;k++) {
System.out.println(b[k]);
}
//System.out.println(max + " " + min);
}
}
int main()
{
int a[] = { 10, 2, 1,4,7,8,3,9,5,6};
//o/p---10,1,8,2,7,3,4
//sort the array
int len = sizeof(a)/sizeof(int);
for (int i = 0; i <len-1; i++)
{
for (int j = 0; j < len-i-1; j++)
{
int temp = a[j];
if (a[j] > a[j + 1])
{
//swap
temp = a[j + 1];
a[j + 1] = a[j];
a[j] = temp;
}
}
}
//o/p form
int k = 0;
for (int i = len - 1; i > 0; i -= 2)
{
int temp = a[len-1];
int j = 0;
for (j = len - 1; j > k; j--)
{
a[j] = a[j - 1];
}
k += 2;
a[j] = temp;
}
return 0;
}
In place soluton in Java
package com.concurrency.pkg;
import java.util.Arrays;
public class FirstMaxFirstMin {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = {1,2,3,4,5,6,7,8,9,10,11};
Arrays.sort(a);
int j = a.length-1;
int i =0;
for(; i<j ;i+=2 )
{
int start = a[i];
int last = a[a.length-1];
int next = a[i+1];
if((i+1) == j){
a[i]= a[j];
a[j]= last;
a[a.length-1] = start;
swapLastTwo(a);
break;
}
a[i]= a[j];
a[i+1]= (i > 0) ? last : start;
a[a.length - 1] = (i > 0) ? start : next;
a[j] = next;
if( a[a.length-2] < a[a.length-1]){
swapLastTwo(a);
}
j--;
}
if((a.length - i) > 2 && (a.length%2 != 0) ){
int temp = a[a.length - 2];
a[a.length - 2] = a[a.length - 1];
a[a.length - 1] = temp;
}
for (i =0 ; i< a.length ; i++)
System.out.print(a[i]+" , ");
}
private static void swapLastTwo(int a[]){
int temp = a[a.length-1];
a[a.length-1] = a[a.length-2];
a[a.length-2] = temp;
}
private static int swap(int i , int j, int[] a){
int next = a[i+1];
int last = a[a.length-1];
int curr = a[i];
a[i+1] =
a[i]= a[--j];
a[i+1]= a[i];
if( i == 0)
a[j]= next;
return j;
}
}
Sort it and then go to the middle of the array and pull out the element and put that in the end of the output array.
After sorting
1 2 3 4 5 6
If size of the array is even or odd you will do accordingly pull out the array element from the middle. After that you start going from mid to start and mid to end and pull out elements and put it in alternate places in the output array. You should use recursion or iterative approach, either will work.
6 1 5 2 4 3
My first time posting.
hope it helps.
It's all basic code
public class SpecialOrder {
// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}
// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}
// I assume that the array is not sorted, and we're not allowed to use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}
if(min > temp )
{
min = temp;
minIndex = index;
}
}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;
}
}
}
//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;
}
public static void sortSpecialOrder(int [] orig){
int number;
if((number = orig.length) >= 2){
int num = 0;
while(num < number)
{
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}
if(min > temp )
{
min = temp;
minIndex = index;
}
}
if(maxIndex == num + 1)
{
if(minIndex == num)
maxMove(num,maxIndex,orig);
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
num = num + 2;
if(num + 1 == number)
break;
}
}
}
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;
}
public class SpecialOrder
{// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));}
// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;}
// I assume that the array is not sorted, and we cannot use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;}
if(min > temp )
{
min = temp;
minIndex = index;}}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);}}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig); }
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;}}}
//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;}
package reviewSet;
public class SpecialOrder {
// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}
// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}
// I assume that the array is not sorted, and we're not allowed to use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}
if(min > temp )
{
min = temp;
minIndex = index;
}
}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;
}
}
}
//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;
}
}
package reviewSet;
public class SpecialOrder {
// main application
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}
// helper method to help me print the array
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}
// I assume that the array is not sorted, and we're not allowed to use the code from library
public static void sortSpecialOrder(int [] orig){
int number;//the length of array
// if the length is smaller than 2, I don't need to sort it.
if((number = orig.length) >= 2){
int num = 0;// variable to help me check the loop times and the position
while(num < number)
{
// variables that help me find the position of the biggest and smallest variables among the rest ones
// every time when I finish a loop, I'll sort start from the unsorted part.
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
// every time when I finish a loop, I'll sort start from the unsorted part.
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}
if(min > temp )
{
min = temp;
minIndex = index;
}
}
// the confusing part
// problem is if the position I want to swap is exactly the position I'm going to put my another value,
// I need to change that "another" value first to make sure there's no effect for first one. eg. I have
// 0,1,_,_,_,7, if I swap 0 and 7 first, the value of minIndex position becomes 7, which will swap again.
if(maxIndex == num + 1)
{
// but both min and max are at the exact opposite position. I just need to swap them one time.
if(minIndex == num)
maxMove(num,maxIndex,orig);
// first move the max, then min, in this case
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
// first move the min, then max, in this case
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
// if all 4 positions are different(minIndex, num, num+1, maxIndex), whatever order will be fine.
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
//every loop, I'll determine the 2 positions
num = num + 2;
//when I have one left, I'll just leave it there, since it's the one at the middle
if(num + 1 == number)
break;
}
}
}
//helper method that help me move the max part
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
//helper method that help me move the min part
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;
}
}
package reviewSet;
public class SpecialOrder {
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}
public static void sortSpecialOrder(int [] orig){
int number;
if((number = orig.length) >= 2){
int num = 0;
while(num < number)
{
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}
if(min > temp )
{
min = temp;
minIndex = index;
}
}
if(maxIndex == num + 1)
{
if(minIndex == num)
maxMove(num,maxIndex,orig);
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
num = num + 2;
if(num + 1 == number)
break;
}
}
}
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;
}
}
package reviewSet;
public class SpecialOrder {
public static void main(String[] args)
{
int [] test = {0,1,2,3,4,5,5,1,0,13};
System.out.println(toString(test));
SpecialOrder.sortSpecialOrder(test);
System.out.println(toString(test));
}
public static String toString(int [] temp)
{
String tem = "[";
int index;
for(index = 0; index < temp.length - 1; index ++)
tem = tem + temp[index] + ",";
tem = tem + temp[index] + "]";
return tem;
}
public static void sortSpecialOrder(int [] orig){
int number;
if((number = orig.length) >= 2){
int num = 0;
while(num < number)
{
int max = orig[num];
int min = max;
int maxIndex = num;
int minIndex = maxIndex;
int index;
for( index = num; index < number; index ++)
{
int temp;
if(max < (temp = orig[index]) )
{
max = temp;
maxIndex = index;
}
if(min > temp )
{
min = temp;
minIndex = index;
}
}
if(maxIndex == num + 1)
{
if(minIndex == num)
maxMove(num,maxIndex,orig);
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
}
else if(minIndex == num)
{
minMove(num,minIndex,orig);
maxMove(num,maxIndex,orig);
}
else
{
maxMove(num,maxIndex,orig);
minMove(num,minIndex,orig);
}
num = num + 2;
if(num + 1 == number)
break;
}
}
}
public static void maxMove(int num, int maxIndex, int[] orig){
int temp = orig[num];
orig[num] = orig[maxIndex];
orig[maxIndex] = temp;
}
public static void minMove(int num, int minIndex, int[] orig){
int temp = orig[num + 1];
orig[num + 1] = orig[minIndex];
orig[minIndex] = temp;
}
}
This solution is O(n/2) if input array is already sorted. Yes, that's the same as O(n) theoretically but in practice, n and n/2 could make a lot of difference for large n.
int *maxmin(int arr[], int size)
{
// sort array in ascending order if not already sorted
// create new array
int *outputarr = new int [size];
int i, j;
for (i=0, j=size-1; i <= j; i++, j--)
{
outputarr[i*2] = arr[j];
if (i == j) break; // so we don't write outside of array
outputarr[i*2+1] = arr[i];
}
return outputarr;
}
private static void RearrangeArraysEasy() {
List<int> array_integers = new List<int> { 10, 1, 29, 8, 10, 45, 56, 100, 98, 34, 11, 9 };
array_integers.Sort();
List<int> sorted = new List<int>();
int middle = array_integers.Count / 2;
for(int i = 0; i< middle; i++) {
sorted.Add(array_integers[array_integers.Count-1] - i);
sorted.Add(array_integers[i]);
}
if(array_integers.Count % 2 == 1) sorted.Add(array_integers[middle]);
foreach (var i in sorted) {
Console.Write("{0} ", i);
}
}
It's in-place and O(n):
def maxMin(array):
for index in range(len(array) - 2, -1, -1):
if array[index + 1] > array[index]:
aux = array[index + 1]
array[index + 1] = array[index]
array[index] = aux
if index < len(array) - 2:
if array[index + 2] < array[index + 1]:
aux = array[index + 2]
array[index + 2] = array[index + 1]
array[index + 1] = aux
return array
print maxMin([1, 2, 3, 4, 5, 6, 7]) # [7, 1, 2, 3, 4, 5, 6]
print maxMin([100000, 200, 31235, 40, 522, 6, 748]) # [100000, 6, 31235, 200, 748, 40, 522]
print maxMin([7, 6, 5, 4, 3, 2, 1]) # [7, 1, 6, 5, 4, 3, 2]
void Sorting(int Number[],int size)
{
int temp;
int count = size /2;
int k = 0;
int incr = 0;
while(k < count)
{
for(int i=incr;i<size;i++)
{
for(int j = i+1;j<size;j++)
{
if(Number[j] > Number[i])
{
temp = Number[j];
Number[j] = Number[i];
Number[i] = temp;
}
}
}
incr++;
for(int i = incr;i<size;i++)
{
for(int j = i+1;j<size;j++)
{
if(Number[j] < Number[i])
{
temp = Number[i];
Number[i] = Number[j];
Number[j] = temp;
}
}
}
incr++;
k++;
}
for(int k=0;k<size;k++)
{
std::cout<<Number[k];
}
}
import java.util.*;
class TestSort1{
public static void main(String args[]){
ArrayList<Integer> al=new ArrayList<Integer>();
al.add(5);
al.add(1);
al.add(7);
al.add(3);
Collections.sort(al);
Iterator itr=al.iterator();
int size=al.size()-1;
System.out.println(al.get(size));
while(size>0){
System.out.println(itr.next());
size--;
}
}
}
Here's an O(n log n) solution in Python, assuming the input array is unsorted
- lick December 17, 2015