Group together and Sort Odd and Even elements of the Array using Bubble sort

DennisJ 0
Viewed 49

I am trying to make an array where odd numbers are sorted in order using Bubble sort algorithm on the left side of the array, and even numbers are sorted in order on the right side of the array.

The output should be like this:

int[] a = {1,2,3,4,5,6,7,8,9,10}
output: 1 3 5 7 9 2 4 6 8 10

The first split between even and odd numbers works, and also the sorting of the odd numbers, but the even numbers are not sorted, and I don't know why.

My Code:

public class ObligOppgave4 {

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9,10};
       
        sortEvenAndOdd(a);
        bubbleSortOdd(a);
        bubbleSortEven(a);

        print(a);
    }

    public static void sortEvenAndOdd(int[] a) {

        int l = a.length;
        int v = 0, h = l - 1;

        if (a.length == 0) return;

        while (v <= h) {
            if (((a[v] % 2) == 0) && !((a[h] % 2) == 0)) {
                change(a, v++, h--);
            } else if ((a[v] % 2) == 0) {
                h--;
            } else if (!((a[h] % 2) == 0)) {
                v++;
            } else if (!((a[v] % 2) == 0) && ((a[h] % 2) == 0)) {
                v++;
                h--;
            }
        }
    }

    public static void bubbleSortOdd(int[] a) {
        for (int n = 0; n < a.length; n++) {
            for (int i = 1; i < n && a[i] % 2 != 0; i++) {
                if (a[i - 1] > a[i]) {
                    change(a, i - 1, i);
                }
            }
        }
    }

    public static void bubbleSortEven(int[] a){
        for (int n = 0; n < a.length; n++) {
            for (int i = 1; i < n && a[i] % 2 == 0; i++) {
                if (a[i - 1] > a[i]) {
                    change(a, i ,i);
                }
            }
        }
    }

    public static void change(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void print(int[] a) {
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");

        System.out.println();
    }
}
bubble-sort java arrays algorithm
2 Answers

It appears to me that this is the problem:

public static void bubbleSortEven(int[] a){
    for (int n = 0; n < a.length; n++)
    {
        for (int i = 1; i < n && a[i] % 2 == 0; i++)
                                 ^^^^^^^^^^^^^^

As you have already moved the odd numbers to the beginning of the array, a[1] is pretty much guaranteed to be odd, and so your loop will exit before it does anything because with i=1, a[i]%2 is 1.

You should probably start sortEven by scanning through the array to find the first even number, and then starting from there.

Another option would be to do a single bubble sort where you weight the even-ness more than the difference. Something like:

int n1 = a[i-1];
int n2 = a[i];
if (n1%2 != n2%2) {
  if (n1%2 == 0) {
    // n1 is even and n2 is not. Swap them
    change(a, i - 1, i);
  }
} else if (n1 > n2) {
  change(a, i - 1, i);
}
userFlO50

You can address this problem by sorting by sorting odd and even parts of the array. That would the solution a bit more concise.

To do that, we can obtain a pivot (index which would point either at the rightmost odd number or at the leftmost even number) while splitting the array into two parts.

Then pivot index can be used as a boundary while sorting the array.

That's how it might be implemented:

public static void sortEvenAndOdd(int[] arr) {
    int pivot = split(arr);
    sort(arr, pivot);
}

public static int split(int[] arr) {
    int odd = 0;
    int even = arr.length - 1;

    while (true) {
        while (arr[odd] % 2 != 0 && odd < even) odd++;
        while (arr[even] % 2 == 0 && odd < even) even--;
    
        if (odd < even) swap(arr, odd, even);
        else break;
    }
    return odd;
}

public static void sort(int[] arr, int pivot) {
    int hiOdd = arr[pivot] % 2 != 0 ? pivot : pivot - 1; // if pivot points at the Even number - step one index back
    
    for (int odd = 0, even = 0; odd <= hiOdd || arr.length - 1 - even > hiOdd; odd++, even++) {
        for (int i = 0; i < hiOdd - odd; i++) {
            if (arr[i] > arr[i + 1]) swap(arr, i, i + 1);
        }
        for (int j = arr.length - 1; j > hiOdd + even + 1; j--) {
            
            if (arr[j - 1] > arr[j]) swap(arr, j, j - 1);
        }
    }
}

public static void swap(int[] arr, int odd, int even) {
    int temp = arr[odd];
    arr[odd] = arr[even];
    arr[even] = temp;
}

main()

public static void main(String[] args) {
    int[] array = {1,2,3,4,5,6,7,8,9,10};
    sortEvenAndOdd(array);

    System.out.println(Arrays.toString(array));
}

Output:

[1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
Alexander Ivanchenko0
Related