Sorting algorithms with array lists

Question

I'm currently working on sorting algorithms with array lists. I have seen a project on GitHub to overwrite the first (smallest) element in a small array with a new (larger) element from a bigger array, and then to sort the small array.

This is the solution provided:

public int findLarger() throws IndexingError {
 int[] array = getArray();
 int k = getIndex();
 if (k <= 0 || k > array.length) {
 throw new IndexingError();
 }
 int[] smallArray = new int[k];
 for (int index = k; index < array.length; index++){
 if (array[index] > smallArray[0]){
 smallArray[0] = array[index];
 Arrays.sort(smallArray);
 }
 }
 return smallArray[0];
}

But I'm struggling to understand if this method I have created is more 'efficient', by using another variable instead of another array?

public int findLarger() throws IndexingError {
 int[] array = getArray();
 int max = array[0];
 for (int i = 0; i < k; i++) {
 if (max < array[i]) {
 max = array[i];
 }
 } 
 return max;
}
public abstract class Search {
private int[] array; 
private int k; 
Search(int[] array, int k) {
 this.array = array;
 this.k = k;
}
public int[] getArray() {
 return array;
}
int getIndex() { return k; }
abstract public int findElement() throws IndexingError;
}

edit:

if (array.length == 0 )
 throw new RuntimeException("Array can't be empty");
 int max = array[0];
 for (int i = 0; i < array.length; i++) {
 if (max < array[i]) {
 max = array[i];
 }
 } // end of obvious solution method
 return max;
 }

• kaya3: What problem does the first method solve? I don't think the second method solves the same problem.
• Steyrix: I do not think that the provided solution is effective one. Since it looks like O(N^2 * logN). Can you please provide implementation of methods getArray() and getIndex()?
• Naples: @kaya3 Both the methods essentially return the largest element of the small array, but go about it differently, the first method just uses the bigger array, whereas the second method uses a variable
• kaya3: @Naples the first method loops over the last n-k items from the big array, whereas the second one loops over the first k elements. It's hard to see how they could possibly do the same thing, since they don't even use the same part of the input.
• Naples: @Steyrix Just updated the question with the getArray() and getIndex() implementations

Answer 1

The first implementation is really bad, why would one sort (O n log n) even worst several array.length-k times, to find the minimum (O(n)) of a set is just awful.

So yes, a version with a single variable, storing the current minimum is the correct way to go. (Just take care that initializing your max with array[0] is not resistant to empty inputs)

On the other hand, as others have commented, the two algorithms are not using the same cells, and are thus currently incomparable. If in your second implementation you iterate from k to array.length like the first one, you do get a much better implementation than the first one.

• Steyrix: Agreed, I would also recommend the author to look at QuickSort, CountSort, MergeSort algorithms instead of wasting time at this concept.
• kaya3: The first method does not find the minimum of the array. It seems to be trying to find the kth largest element that occurs after index k.
• Naples: @Yann I have now accounted for the case of empty inputs, and have iterated from array.length, would this be a more efficient solution?
• Yann TM: Sorry, I misread your code, the intent was unclear, especially since your own algorithm is computing a max. See the other answer and Kaya's helpful insights. So the first algorithm is actually doing something that is not finding the min. It's sorting too many times however, as other answer notes, a single sort is basically enough, though with k small enough before n, a single call to sort is worstthan the original code solution.

Answer 2

This is a difficult question to answer for two reasons:

• Firstly, method #1 and method #2 do not do the same thing, so comparing their efficiency doesn't really make sense.
• Secondly, what method #1 actually does is a bit difficult to pin down exactly, and it's not clear that what it actually does is the same as what it should do. That is, method #1 is not just a solution to a different problem; I suspect it is an incorrect solution to a different problem.

Let me explain. Method #2 is quite straightforward: it finds the maximum element from the subarray array[0..k]. Method #1 clearly does not do this: it only reads data from the subarray array[k..n].

It also clearly isn't finding the maximum from that subarray, because it puts data into smallArray, sorts it, and returns the value from index 0; the maximum would be at index k - 1. But the value at index 0 is also not the minimum, since data only gets put into smallArray if it's bigger than what's already there.

The actual behaviour of method #1 can be investigated using examples. For convenience, I've changed the signature to take array and k as parameters:

• findLarger(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 3) is 5: the third-largest of 4, 5, 6, 7.

• findLarger(new int[] { 1, 2, 3, 7, 6, 5, 4 }, 3) is also 5: the third-largest of 7, 6, 5, 4.

• findLarger(new int[] { 7, 6, 5, 4, 3, 2, 1 }, 3) is 2: the third-largest of 4, 3, 2, 1.

• findLarger(new int[] { 1, 2, 3, 7, 6, 5, 4 }, 1) is 7: the first-largest of 2, 3, 7, 6, 5, 4.

For these examples, it consistently returns the kth largest element in the subarray array[k..n]. However, in other cases, it doesn't:

• findLarger(new int[] { -1, -2, -3, -4, -5, -6 }, 2) is 0, not one of -3, -4, -5, -6.
• findLarger(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 5) is 0, not one of 6, 7.

So the full statement of what method #1 does is: it returns the kth largest positive element from the subarray array[k..n], or 0 if this sub-array contains fewer than k positive numbers. The special case of returning 0, and the use of k for two unrelated purposes, suggests that this method was supposed to solve the more straightforward problem of returning the kth largest element, but that it was written incorrectly.

Further evidence for this is that a very simple change to the algorithm makes it unconditionally return the kth largest element: instead of initialising smallArray with zeroes, copy the first k elements from array and sort them.

 // changed: copy first k elements from array, and sort
 int[] smallArray = Arrays.copyOfRange(array, 0, k);
 Arrays.sort(smallArray);
 for (int index = k; index < array.length; index++){
 if (array[index] > smallArray[0]){
 smallArray[0] = array[index];
 Arrays.sort(smallArray);
 }
 }
 return smallArray[0];

Even more evidence is the similarity with the code in this other Stack Overflow question, which is meant to find the kth largest element, and which does the copyOfRange and sort instead of just new int[k].

---

So now we can talk about the efficiency of alternatives to the fixed version of method #1.

• The time complexity of method #1 is O(nk log k).

• Method #1 can be improved to O(nk) by changing Arrays.sort in the inner loop to shift the first element to its correct position in O(k) time; this works because only the first element will be out of order, so a full sort is unnecessary.

• The obvious way to find the kth largest element is to sort the array and return the value at index n - k. This takes O(n log n) time; method #1 is only better when k log k < log n, i.e. when k is small compared to n.

• You can do better - the quickselect algorithm takes just O(n) time on average, which is clearly optimal for this problem. However, it has a rare worst-case complexity of O(n2).