How to sort some elements and leave others in Java?

Question

I'm looking to sort some elements within an array but exclude others.

For a simple example, an array containing integers, I would like to sort the odd numbers but leave the even where they are.

So far I have the following:

public class MyClass {
    public static void main(String args[]) {
        int temp;
        int array[] = {5, 3, 2, 8, 1, 4};

        int[] sortedArray = new int[array.length];
        for (int j = 0; j < array.length - 1; j++) {
            for (int x = 0; x < array.length - 1; x++) {
                if (array[x] > array[x + 1] && array[x] % 2 != 0 && array[x + 1] % 2 !=0) {
                    temp = array[x];
                    array[x] = array[x + 1];
                    array[x + 1] = temp;
                    sortedArray = array;
                }
            }
        }
        for (int i: sortedArray) {
            System.out.println(i);
        }

    }
}

Given integer array: 5, 3, 2, 8, 1, 4

Output of the code: 3, 5, 2, 8, 1, 4

Expected output: 1, 3, 2, 8, 5, 4

Can't quite figure out the logic needed for the scenario in which a lower odd number comes before an even number within the original array.

Answer 1

A simple brute force solution:

• iterate the input array, and retrieve all odd numbers
• collect the odd numbers in a new, smaller array
• sort that array
• now walk the initial array again: whenever you find a odd number, you pick the "next" entry from the odd array

The above is probably not the optimal solution (because of wasting memory on a second array, and spending time copying forth/back values) - but it should be super easy to write down and test.

Theoretically, you can also do that "in place". Meaning: you could create a class that wraps around an array of int - but that provides a view to its users that only shows an array of the odd ints.

Example implementation (thanks to Daniel Foerster):

public static int[] sortFiltered(int[] src, IntPredicate predicate) {
  int[] filtered = IntStream.of(src).filter(predicate).sorted().toArray();
  int[] dst = new int[src.length];
  for (int i = 0, j = 0; i < src.length; i++) {
    dst[i] = predicate.test(src[i]) ? filtered[j++] : src[i];
  }
  return dst;
}

Invocation with a filter for odd numbers:

sortFiltered(array, (n) -> n % 2 != 0);

As you can see this algorithm doesn’t depend on a particular predicate or array/list type. But as it uses IntStream and Lambda Expressions, it requires Java 8 or newer.

Answer 2

You have implemented some kind of (not super efficient) bubble sort. The problem with your code is that it excludes both elements from sorting even though only one is even. Building upon your solution, you could adjust your code as follows:

public class MyClass {
    public static void main(String args[]) {
        int temp;
        //odd numbers are sorted, even number stay where they are
        //Expected output: 1, 3, 2, 8, 5, 4
        int array[] = {5, 3, 2, 8, 1, 4};
        int[] sortedArray = new int[array.length];
        for (int j = 0; j < array.length - 1; j++) {
            for (int x = 0; x < array.length - 1; x++) {

                while(array[x] % 2 == 0 && x < array.length-1){
                    x++;
                }

                int y = x+1;

                if(y < array.length) {
                    while (array[y] % 2 == 0 && y < array.length - 1) {
                        y++;
                    }

                    if (array[x] > array[y] && array[y] % 2 == 1 && array[x] % 2 == 1) {
                        temp = array[x];
                        array[x] = array[y];
                        array[y] = temp;
                        sortedArray = array;
                    }
                }
            }
        }
        for (int i: sortedArray) {
            System.out.println(i);
        }
    }
}

This results in:

1 3 2 8 5 4

Answer 3

Your code is kind of a bubble sort but with that you're only comparing each direct neighbor. Here is working code that uses 2 for loops and works in place. It doesn't necessarily compares the direct neighbors but instead it looks up the next odd number to compare with the current odd number.

Further there was a little mistake with the copying of your array to sortedArray because you do this: sortedArray = array; in your loop which just copies the array reference. In the working code below I picked up your solution and changed it. I also just copy the array before the sorting begins so that the source array is unchanged.

The inner for loop starts with the index of the outer for loop plus 1. Moreover the inner loop just loops till one element before end. In the worst case it will need n-1 * n/2 = n^2/2 - n/2 operations which leads to O(n^2) like the regular bubble sort.

Code and working example on ideone:

public class MyClass
{
   public static void main(String args[])
   {
      int array[] = {5, 3, 2, 8, 1, 4};

      int[] sortedArray = new int[array.length];
      System.arraycopy(array, 0, sortedArray, 0, array.length);

      for (int i = 0; i < sortedArray.length - 1; i++)
      {
         /* is current odd, if so search next odd */
         if (sortedArray[i] % 2 != 0)
         {
            /* search for next odd and compare */
            for (int j = i + 1; j < sortedArray.length; j++)
            {
               if ((sortedArray[j] % 2 != 0) && (sortedArray[i] > sortedArray[j]))
               {
                  int temp = sortedArray[i];
                  sortedArray[i] = sortedArray[j];
                  sortedArray[j] = temp;
               }
            }
         }
      }
      for (int i: sortedArray)
      {
         System.out.println(i);
      }
   }
}

Output:

1
3
2
8
5
4

Answer 4

Given unsorted array A: Create 2 Vector instances O and E containing the odd and even elements of the array, in order. (all code examples are pseudocode. "up to" in a loop means that the right side of the limit isn't included, according to standard array bound numbering)

for i in 0 up to A.length: if A[i] is odd, append it to O, else append it to E

Create a separate array of booleans B as follows:

for i in 0 up to A.length: if A[i] is odd, B[i] = true, else B[i] = false

Sort O into a new Vector S (in ascending order). I recommend using Java's built-in sort as it will be much more efficient than the bubble sort the other answers claim you're using.

S = ascendingSort(O)

Define an operation pop that returns the first item in a Vector, then removes it from the Vector.

Create a new empty Vector R, then implement the following pseudocode:

for i in 0 up to B.length: if B[i] is true, then append pop(S) to R, else append pop(E) to R.

Return R as the result.

---

Why this works:

First, separate the odds from the evens to hide the evens from the sort, maintaining their original order (vectors O and E). Maintain the positions (vector B) of the odd/even items in the original array.

Sort the odds (vector S).

After sorting, stitch the evens and sorted odds back in order, maintaining the original ordering of the evens. Read through vector B, taking elements in order from vectors E and S. This maintains the order of the evens because they were placed into vector E in order in the first place, and they are put back in order.