Sorting an array and indexOf() runtime

Question

Is it safe to assume that array.indexOf() does a linear search from the beginning of the array?

So if I often search for the biggest value, will sorting the array before calling indexOf make it run even faster?

Notes:

I want to sort only once and search many times.

"biggest value" is actually the most popular search key which is a string.

Answer 1

Yes, indexOf is starting from the first to the last. Sorting it before asking the first entry afterwards makes a difference in performance depending in the performance of sorting algorithm. Normally O(N log N) in quicksort to O(n) in linear search. I would suggest you to make a simple test for it with random value count and see how performance behave.

Of course it depends on your DataObject: ArrayList:

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

Perhaps a TreeSet can also help you till its ordered all the time.

At the end i would say:"Depends on your data-container and how the ordering or search is implemented and where the performance in the whole process is needed".

As a comment say with pure arrays you can make binarySearch which has the same performance impact of quicksort.

So at the end its not only a question of the performance of algorithm but also at what time you need the performance in the process. For example if you have lots of time by adding values and no time by getting the value you need, a sorted structure can improve it very well, like Tree-Collections. If you need more performance by adding things its perhaps the other way around.