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: 
The fastest algorithm I can think of would be to replace the smallest element with the new one, if needed, and push the new one to its proper place by repeatedly swapping with adjacent elements.

**EDIT:** The code assumes that the array is sorted in descending order, and thus the last element is the smallest.

```
void Insert(int[] array, int newValue)
{
    // If the new value is less than the current smallest, it should be
    // discarded
    if (new_value <= array[array.length-1])
        return;

    array[array.length-1] = newValue;
    for (int i = array.length-1; i > 0; --i)
    {
        if (newValue <= array[i-1])
            break;

        // Swap array[i] with array[i-1]
        array[i] = array[i-1];
        array[i-1] = newValue;
    }
}

```
This will keep the size at 4 and do what you want as I understand it.

```
SortedSet<Integer> set = new TreeSet<Integer>();
set.add(2);
set.add(3);
set.add(6);
set.add(9);
Random rand = new Random();
for (int i=0; i < n; i++) {
  int i = rand.nextInt(1000);
  set.remove(set.first());
  set.add(i);
}    

```