Sorted Array List in Java

Sorted array list in Java

Minimalistic Solution

Here is a quick and dirty solution.

class SortedArrayList<T> extends ArrayList<T> {
    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        int i = Collections.binarySearch((List<Comparable<T>>) this, value);
        add(i < 0 ? -i - 1 : i, value);
    }
}

Note that despite the binarySearch, insertSorted will run in linear time since add(index, value) runs in linear time for an ArrayList.

Inserting something non-comparable results in a ClassCastException. (This is the approach taken by PriorityQueue as well: A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)

A more complete implementation would, just like the PriorityQueue, also include a constructor that allows the user to pass in a Comparator.

Demo

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

....prints:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Overriding List.add

Note that overriding List.add (or List.addAll for that matter) to insert elements in a sorted fashion would be a direct violation of the interface specification.

From the docs of List.add:

boolean add(E e)

    Appends the specified element to the end of this list (optional operation).

Maintaining the sortedness invariant

Unless this is some throw-away code, you probably want to guarantee that all elements remain sorted. This would include throwing UnsupportedOperationException for methods like add, addAll and set, as well as overriding listIterator to return a ListIterator whose set method throws.

How to sort a List/ArrayList?

Collections.sort(testList);
Collections.reverse(testList);

That will do what you want. Remember to import Collections though!

Here is the documentation for Collections.

Sorting an ArrayList of arrays in java

You should use Collections.sort() together with a custom Comparator:

List<Integer[]> arrays = new ArrayList<>();

arrays.add(new Integer[]{1, 2});
arrays.add(new Integer[]{3, 4});

Collections.sort(arrays, new Comparator<Integer[]>() {
    public int compare(Integer[] a, Integer[] b) {
        return 1; // FIX this according to your needs
    }
});

compare() above is just a stub, you should implement it according to the documentation and it could be replaced with a lambda expression. In the code above that would be: Collections.sort(arrays, (a, b) -> 1).

How to sort an ArrayList of ArrayLists (by one of the variables) in Java?

With Stream API (Java 8):

public static void main(String[] args) {
    List<List<Integer>> list = new ArrayList<>();

    list.add(asList(5, 10));
    list.add(asList(2, 11));
    list.add(asList(1, 12));
    list.add(asList(8, 15));

    System.out.println("sorted asc = " + list.stream()
            .sorted(Comparator.comparing(o -> o.get(0)))
            .collect(Collectors.toList()));

    System.out.println("sorted desc = " +  list.stream()
            .sorted((i, j) -> -i.get(0).compareTo(j.get(0)))
            .collect(Collectors.toList()));
}

private static List<Integer> asList(Integer... arr) {
    return Arrays.asList(arr);
}

sorted asc = [[1, 12], [2, 11], [5, 10], [8, 15]]

sorted desc = [[8, 15], [5, 10], [2, 11], [1, 12]]

How to sort an ArrayList in Java

Use a Comparator like this:

List<Fruit> fruits= new ArrayList<Fruit>();

Fruit fruit;
for(int i = 0; i < 100; i++)
{
  fruit = new Fruit();
  fruit.setname(...);
  fruits.add(fruit);
}

// Sorting
Collections.sort(fruits, new Comparator<Fruit>() {
        @Override
        public int compare(Fruit fruit2, Fruit fruit1)
        {

            return  fruit1.fruitName.compareTo(fruit2.fruitName);
        }
    });

Now your fruits list is sorted based on fruitName.

Sort an Arraylist without modifying the original list

Well, you don't actually need to make a deep copy unless your Comparator is mutating your objects, which it shouldn't. The easiest way is therefore to make shallow copy:

ArrayList<String> original = new ArrayList<>();
ArrayList<String> copy = new ArrayList<>(original);
copy.sort(Comparator.naturalOrder());

Replace Comparator.naturalOrder() with your actual Comparator implementation. For example, if you are comparing a member field, you can use Comparator.comparing as an easy way to create your desired Comparator.

And to answer your question: No, it's not possible without an additional data structure because on the one hand you want to alter the order of the elements, i.e. sort them, and on the other hand you want them to stay in the same order.

Sorting ArrayList with sorted Array in Java Ends Up with Different Results

It works for this case: {"c1","a1","e","a2","d","c2","c3","b","c4","f","a3"} because all elements are unique.

indexOf method returns the index of the first occurence of a given element and since your original array i.e. {"1","3", "0", "5","3", "5", "6", "8", "8", "2","12"} contains duplicates, indexOf is going to return same value for elements "3", "5" and "8" (returns 1 for both"3", 3 for both "5", 7 for both "8")

I don't think you can apply Comparator here since it uses the values of compared elements and your problem requires inspection of indices of compared elements without checking their actual values (well, unless you guarantee that the elements are unique)

Or you may create a list of class Pair with string field having value of strings that your original list consists of, and int field having value of index of corresponding string. In that case you may use comparator to sort the list of pairs and after that you get your sorted list of strings by iterating through the sorted list of pairs

Java: create a separate sorted Arraylist while keeping the original list

I'm going to assume the ArrayList holds Strings:

ArrayList<String> stopsSorted = new ArrayList<>(value.getNewStop()); // use the arraylist attribute
Collections.sort(stopsSorted);
System.out.println(stopsSorted);

As you can see, we pass the ArrayList that we don't want to modify into the constructor of a new ArrayList<String>.

---

Related Topics