Question: 1. Suppose given an array of size n, with sorted values.
2. In iteration i, a new random-generated value is given, and inserted into the end of the array.
3. The array is then resorted, and discard the least value item.
4. After iteration n, the retained array will contain the largest value items.

For example, in Java syntax, it will be something like:

```
List l = new ArrayList();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

Random rand = new Random();
for (int i=0; i < n; i++) {
  l.add(new Integer(rand.nextInt(1000)));
}    
Collections.sort(l);
l.remove(0);

```

But it seems it's inefficient. Any better algorithm?

Answer: 
[**Collections.binarySearch()**](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20java.lang.Object))

[**ArrayList.ensureCapcity()**](http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html#ensureCapacity(int))

Your pseudocode inserts a set of new items N into sorted list A of size S and then discards the smallest item. Use **Collections.binarySearch()** to find the insertion point. *[Read the note the performance impact if your List is does not support RandomAccess. ArrayList does support RandomAccess.]*

```
List<Integer> l = new ArrayList<Integer>();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

l.ensureCapacity(l.size()+n);

Random rand = new Random();
for (int i=0; i < n; i++) {
  final Integer newInt = Integer.rand.nextInt(1000);
  int insertPoint = Collections.binarySearch(l, newInt);
  if (insertPoint < 0)  insertPoint = -(insertPoint + 1);
  l.add(insertPoint, newInt);
}
l.remove(0);

```

But, are you sure you wanted to discard just 1 item? Or did you mean to insert a set of new items N into sorted list A of size S and keep just the S largest items. In that case, keep track of the min value:

```
int min = l.get(0);
l.ensureCapacity(l.size()+n);

Random rand = new Random();
for (int i=0; i < n; i++) {
  final Integer newInt = Integer.rand.nextInt(1000);
  if (newInt > min) {
    int insertPoint = Collections.binarySearch(l, newInt);
    if (insertPoint < 0)  insertPoint = -(insertPoint + 1);
    l.add(insertPoint, newInt);
  }
}

```

However, if N is large, you may be better off sorting N into an sorted array by itself, discarding the smaller of N(0) or A(0), and then merging the two sorted arrays together [left as an exercise for the reader].

If you end up using an actual array, see [Arrays.binarySearch](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html#binarySearch(byte[],%20byte)) and [System.arraycopy](http://java.sun.com/j2se/1.4.2/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)).
Do you really need an online one item at a time algorithm? Or are you actually parsing a larger collection of data and just want the top n items? If it's the latter, look at [partial qsort](http://www.siam.org/meetings/analco04/abstracts/CMartinez.pdf).