Add and Sort to ArrayList at Same

Question

I am trying to write a method that will randomly add items to the ArrayList and then sort it based on the elements being added as you go, but it isn't working properly. I have posted my code below, but I don't know why it isn't working properly. Any help would be greatly appreciated.

public static void sortAndAdd(ArrayList<Integer> inL, int maxNumberOfElements) {

        inL.clear();
        inL.add(new java.util.Random().nextInt());
        for (int i = 1; i < maxNumberOfElements - 1; i++) {
            inL.add(new java.util.Random().nextInt(limit));
            if (inL.get(i) > inL.get(i-1)) {
                inL.set(i-1, inL.get(i));
                inL.set(i, inL.get(i-1));
            } 
        }
    }

What does "not working properly" mean exactly. What is happening to it? — Nexevis, Sep 19 '19 at 19:17
If you want to **swap** the values of `a` and `b`, you cannot just write `a=b; b=a;`, since that'll override value of `a` so second assignment won't work. You need to write `temp=a; a=b; b=temp;`. It a standard **swap** construct, and you didn't use it. --- Also, you cannot sort a array in a single iteration. Sorting is more complex than that, and programmer guides will spend entire chapters just on sorting algorithms. Use the build-in sort methods of Java, or start reading a Java guide on sorting. — Andreas, Sep 19 '19 at 19:20
Don't create multiple `Random` objects in a loop. Create one before the loop then use it. Creating multiple will prevent good randomization, so don't do that. --- Don't mix the building of the list with the sorting. Build the list first, *then* sort it. It's known as Separation of Concerns, and will become more useful as your code gets more complex. — Andreas, Sep 19 '19 at 19:23
In addition to what others have said, there's no reason to pass a list into your `sortAndAdd` method, since you immediately clear it. Instead, have your method return a list. Then declare the new list inside the method, and return it once you're done adding and sorting. — Jordan, Sep 19 '19 at 19:25
Another possibility would be to iterate over the list until you find some value that is greater than the one you want to insert. Then just slide the rest of the list down and insert the new one directly before the greater one. Then continue to repeat this for the next value. — WJS, Sep 19 '19 at 20:20

score 3 · Answer 1 · answered Sep 19 '19 at 19:36

Even if the temp variable is fixed, your logic is flawed as this will not sort. Below I will show you an example on why it will not work.

Let us assume Random will generate values 1 to 10.

First value is generated is 7.

[7]

Next generated is 4.

[7, 4]

It swaps them and it is now:

[4, 7]

Next generated value is 2.

[4, 7, 2]

Final values swap and it is now:

[4, 2, 7]

As you can see this will not correctly sort a List because you are only comparing the final two values, but you do not account for the previous ones at all.

You will most likely need another loop inside of the for loop to continue comparing until you find the correct place for it. Or use a different algorithm completely.

`You will most likely need another loop inside of the for loop to continue comparing until you find the correct place for it.` If you assume the list is sorted before you insert the element (which is a safe assumption, since you start with a fresh list and then ensure it's sorted after each insertion), you can use a [binary search](https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html#binarySearch-java.util.List-T-) to find where the new element should go, and then just insert it there. That'll be more efficient than a loop. — yshavit, Sep 19 '19 at 19:39

score 1 · Answer 2 · answered Sep 19 '19 at 19:23

1

Looks like you're overwriting your value here:

inL.set(i-1, inL.get(i));
inL.set(i, inL.get(i-1));

Use a temporary variable to store the value before setting it:

int temp = inL.get(i-1);
inL.set(i-1, inL.get(i));
inL.set(i, temp);

answered Sep 19 '19 at 19:23

Matthias

75
8

score 1 · Answer 3 · answered Sep 19 '19 at 19:26

            inL.set(i-1, inL.get(i));
            inL.set(i, inL.get(i-1));

You've got a problem in your logic here. Let's start where i = 1. You're saying "set place 0 value to place 1's value" and then saying "set place 1's value to place 0's value". But you've already overridden place 0's value with the value of place 1.

You need to evaluate the variables before you start setting the values in the list.

If you're using Java 8, you could also check out the Stream API.

https://www.baeldung.com/java-8-streams

Add and Sort to ArrayList at Same

3 Answers3