Changing sorting algorithm java

Question

starting Java coder here. I was wondering how to change my code so it would sort array by always swapping the biggest value to first. Sample output should be:

[3, 1, 2, 0] [3, 2, 1, 0].

public class Sorting {

static void biggest(int[] arr, int start, int end) {
    for (start = 0; start < arr.length; start++) {
        for (end = start + 1; end < arr.length; end++) {
            if (arr[start] < arr[end]) {
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
                System.out.println(Arrays.toString(arr));

            }
        }
    }
}

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3};
    int temp = 0;
    for (int i = 0; i < 4; ++i) {
        biggest(arr, temp, 4 - 1);
        for (int j = 0; j < 4; ++j) {
        }
        ++temp;
    }
}

Thanks in advance, - Em

Please read "How to create a minimal reproducible example". Then use the edit link to improve your question (do not add more information via comments). Otherwise we are not able to answer your question and help you. — GhostCat
– GhostCat, Commented Nov 26, 2018 at 19:01

ameddin73 · Accepted Answer · 2018-11-26 20:21:04Z

If you just want the sort to be successful, I suggest taking advantage of Java's built in sort method then reversing the list as suggested here:

Arrays.sort(arr);
ArrayUtils.reverse(arr);

But it sounds like the spirit of your question is to modify your code for this purpose. Here's the solution I came up with:

import java.util.Arrays;

public class Sorting {

static void biggest(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(Arrays.toString(arr));
        int max, maxAt = i;
        for (int j = i; j < arr.length; j++) {
            maxAt = arr[j] > arr[maxAt] ? j : maxAt;
        }
        max = arr[maxAt];
        if (arr[i] < max) {
            arr[maxAt] = arr[i];
            arr[i] = max;
        }
    }
}

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 3};
    biggest(arr);
    System.out.println(Arrays.toString(arr));
}
}

First off, you had a lot of extra code that you didn't need. It's a bad idea to have a loop in your main. That should be handled by the helper function. You also had a lot of redundant declarations (like start and end). You were on the right track with your helper function, but because of your main loop your time complexity was 0(n²). Eliminating that allows mine to be O(logn). Complexity aside, the key difference in terms of logic is here in your internal loop:

for (end = start + 1; end < arr.length; end++) {
        if (arr[start] < arr[end]) {
            int temp = arr[end];
            arr[end] = arr[start];
            arr[start] = temp;

In this loop you're switching the array entry with the first one you find that's bigger. This will result in unwanted early switches (like 1 & 2). Here is my solution:

for (int j = i; j < arr.length; j++) {
        maxAt = arr[j] > arr[maxAt] ? j : maxAt;
    }
    max = arr[maxAt];
    if (arr[i] < max) {
        arr[maxAt] = arr[i];
        arr[i] = max;
    }

The key difference is that I search for the maximum value entry following the one we're swapping. That way as we proceed through the array we will always bring forward the next biggest.

Best of luck learning Java I hope this helps!

Collectives™ on Stack Overflow

Changing sorting algorithm java

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related