CODEWITHSUNDEEP
javaalgorithm
sonam
sonam

Reputation: 3760

move all even numbers on the first half and odd numbers to the second half in an integer array

I had an interview question which i could not solve.

Write method (not a program) in Java Programming Language that will move all even numbers on the first half and odd numbers to the second half in an integer array.

E.g. Input = {3,8,12,5,9,21,6,10}; Output = {12,8,6,10,3,5,9,21}.

The method should take integer array as parameter and move items in the same array (do not create another array). The numbers may be in different order than original array. This is algorithm test, so try to give as efficient algorithm as you can (possibly linear O(n) algorithm). Avoid using built in functions/API. *

Also some basic intro to what is data structure efficiency

Upvotes: 1

Views: 18540

Answers (14)

user7295191
user7295191

Reputation: 1

public class ArraysSortEvensFirst {

public static void main(String[] args) {
    int[] arr = generateTestData();
    System.out.println(Arrays.toString(arr));

    ArraysSortEvensFirst test = new ArraysSortEvensFirst();
    test.sortEvensFirst(arr);

}

private static int[] generateTestData() {
    int[] arr = {1,3,5,6,9,2,4,5,7};
    return arr;
}

public int[] sortEvensFirst(int[] arr) {
    int end = arr.length;

    int last = arr.length-1;
    for(int i=0; i < arr.length; i++) {
        // find odd elements, then move to even slots
        if(arr[i]%2 > 0) {
            int k = findEven(last, arr);
            if(k > i) swap(arr, i, k);
            last = k;
        }
    }

    System.out.println(Arrays.toString(arr));
    return arr;
}

public int findEven(int last, int[] arr) {
    for(int k = last; k > 0; k--) {
        if(arr[k]%2 == 0) {
            return k;
        }
    }
    return -1; // not found;
}

public void swap(int[] arr, int x, int y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

}

Output: [1, 3, 5, 6, 9, 2, 4, 5, 7] [4, 2, 6, 5, 9, 3, 1, 5, 7]

Upvotes: 0

hari brahmeswara reddy Kovvuri
hari brahmeswara reddy Kovvuri

Reputation: 1

efficiency is O(log n).

public class TestProg {
public static void main(String[] args) {
    int[] input = { 32, 54, 35, 18, 23, 17, 2 };
    int front = 0;
    int mid = input.length - 1;
    for (int start = 0; start < input.length; start++) {
    //if current element is odd
        if (start < mid && input[start] % 2 == 1) {
    //swapping element is also odd?
            if (input[mid] % 2 == 1) {
                mid--;
                start--;
            } 
    //swapping element is not odd then swap
     else {
                int tmp = input[mid];
                input[mid] = input[start];
                input[start] = tmp;
                mid--;
            }
        }

    }
    for (int x : input)
        System.out.print(x + " ");
}

}

Upvotes: -1

honeyinapples
honeyinapples

Reputation: 21

public class SeperatOddAndEvenInList {

public static int[] seperatOddAndEvnNos(int[] listOfNumbers) {
    int oddNumPointer = 0;
    int evenNumPointer = listOfNumbers.length - 1;
    while(oddNumPointer <= evenNumPointer) {                
            if(listOfNumbers[oddNumPointer] % 2 == 0) { //even number, swap to front of last known even number
                int temp;
                temp = listOfNumbers[oddNumPointer];
                listOfNumbers[oddNumPointer] = listOfNumbers[evenNumPointer];
                listOfNumbers[evenNumPointer] = temp;
                evenNumPointer--;
            }
            else {  //odd number, go ahead... capture next element
                oddNumPointer++;
            }


    }
    return listOfNumbers;
}


public static void main(String[] args) {
    // TODO Auto-generated method stub
    int []arr = {3, 8, 12, 5, 9, 21, 6, 10};
    int[] seperatedArray = seperatOddAndEvnNos(arr);
    for (int i : seperatedArray) {
        System.out.println(i);
    }

}

}

Upvotes: 0

Tushar Bhandari
Tushar Bhandari

Reputation: 11

Use two counters i=0 and j=a.length-1 and keep swapping even and odd elements that are in the wrong place.

  public int[] evenOddSort(int[] a) {
        int i = 0;
        int j = a.length - 1;
        int temp;
        while (i < j) {
            if (a[i] % 2 == 0) {
                i++;
            } else if (a[j] % 2 != 0) {
                j--;
            } else {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            }
        }
        return a;
    }

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58281

You can do this with a single loop by moving odd items to the end of the array when you find them.

static void EvensToLeft(int[] items) {
    int end = items.length;
    for (int i = 0; i < end; i++) {
        if (items[i] % 2) {
            int t = items[i];
            items[i--] = items[--end];
            items[end] = t;
        }
    }
}

Given an input array of length n the inner loop executes exactly n times, and computes the parity of each array element exactly once.

Upvotes: 0

Saurabh Jain
Saurabh Jain

Reputation: 291

// to do this in one for loop 

public static void evenodd(int[] integer) {

    int i = 0, temp = 0;
    int j = integer.length - 1;

    while (j >= i) {
        // swap if found odd even combo at i and j
        if (integer[i] % 2 != 0 && integer[j] % 2 == 0) {
            temp = integer[i];
            integer[i] = integer[j];
            integer[j] = temp;
            i++;
            j--;

        } else {
            if (integer[i] % 2 == 0) {
                i++;
            }
            if (integer[j] % 2 == 1) {
                j--;
            }

        }

    }
}

Upvotes: 4

psk
psk

Reputation: 1

public void sortEvenOddIntegerArray(int[] intArray){
    boolean loopRequired = false;
    do{
        loopRequired = false;
        for(int i = 0;i<intArray.length-1;i++){

            if(intArray[i] % 2 != 0 && intArray[i+1] % 2 == 0){

                int temp = intArray[i];
                intArray[i] = intArray[i+1];
                intArray[i+1] = temp;
                loopRequired = true;
            }
        }
    }while(loopRequired);
}

Upvotes: 0

maverick
maverick

Reputation: 589

private static void rearrange(int[] a) {
    int i,j,temp;
    for(i = 0, j = a.length - 1; i < j ;i++,j--) {
        while(a[i]%2 == 0 && i != a.length - 1) {
            i++;
        }
        while(a[j]%2 == 1 && j != 0) {
            j--;
        }
        if(i>j)
            break;
        else {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }       
}

Upvotes: 0

Sanj
Sanj

Reputation: 291

@JLRishe,

Your algorithm doesn't maintain the order. For a simple example, say {1,5,2}, you will change the array to {2,5,1}. I could not comment below your post as I am a new user and lack reputations.

Upvotes: 2

JLRishe
JLRishe

Reputation: 101700

(With a lot of help from @manu-fatto's suggestion) I believe this would do it:

private static int[] OddSort(int[] items)
{
    int oddPos, nextEvenPos;
    for (nextEvenPos = 0; 
         nextEvenPos < items.Length && items[nextEvenPos] % 2 == 0;
         nextEvenPos++) { }
    // nextEvenPos is now positioned at the first odd number in the array, 
    // i.e. it is the next place an even number will be placed

    // We already know that items[nextEvenPos] is odd (from the condition of the 
    // first loop), so we'll start looking for even numbers at nextEvenPos + 1
    for (oddPos = nextEvenPos + 1; oddPos < items.Length; oddPos++)
    {
        // If we find an even number
        if (items[oddPos] % 2 == 0)
        {
            // Swap the values
            int temp = items[nextEvenPos];
            items[nextEvenPos] = items[oddPos];
            items[oddPos] = temp;
            // And increment the location for the next even number
            nextEvenPos++;
        }
    }

    return items;
}

This algorithm traverses the list exactly 1 time (inspects each element exactly once), so the efficiency is O(n).

Upvotes: 6

The Game
The Game

Reputation: 62

class Demo
{
public void sortArray(int[] a)
{
int len=a.length;
int j=len-1;
for(int i=0;i<len/2+1;i++)
{
if(a[i]%2!=0)
{
while(a[j]%2!=0 && j>(len/2)-1)
j--;
if(j<=(len/2)-1)
break;
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
}
}
for(int i=0;i<len;i++)
System.out.println(a[i]);
}

public static void main(String s[])
{
int a[]=new int[10];
System.out.println("Enter 10 numbers");
java.util.Scanner sc=new java.util.Scanner(System.in);
for(int i=0;i<10;i++)
{
a[i]=sc.nextInt();
}
new Demo().sortArray(a);
}
}

Upvotes: 0

sofa
sofa

Reputation: 11

public static void sorted(int [] integer) {

int i, j , temp;

for (i = 0;  i < integer.length;  i++) {

     if (integer[i] % 2 == 0) {
         for (j = i;  j < integer.length;  j++) {
              if (integer[j] % 2 == 1) {
                  temp = y[i];
                  y[i] = y[j];
                  y[j] = temp;
              }
          }
      }
      System.out.println(integer[i]);
}

public static void main(String args[]) {

       sorted(new int[]{1, 2,7, 9, 4}); 



}

}

The answer is 1, 7, 9, 2, 4.

Upvotes: 1

Leon
Leon

Reputation: 1181

Could it be that you were asked to implement a very basic version of the BubbleSort where the sort value of element e, where e = arr[i], = e%2==1 ? 1 : -1 ? Regards Leon

Upvotes: 0

Emanuele Paolini
Emanuele Paolini

Reputation: 10162

Keep two indices: one to the first odd number and one to the last even number. Swap such numbers and update indices.

Upvotes: 10

Related Questions