Сортировать «отсортированный» массив

Question

1. Предположим, задан массив размера n с отсортированными значениями.
2. На итерации i дается новое случайное значение, которое вставляется в конец массива.
3. Затем массив восстанавливается и отбрасывает элемент наименьшего значения.
4. После итерации n сохраненный массив будет содержать элементы с наибольшим значением.

Например, в синтаксисе Java это будет что-то вроде:

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);

Но, похоже, это неэффективно. Есть лучший алгоритм?

Answer 1

Используйте бинарную вставку (работает как бинарный поиск) для нового значения. Откажитесь от самых маленьких. Должно быть довольно быстро.

Кстати, это может быть реализовано как удобный метод расширения:

private static int GetSortedIndex( this IList list, IComparer comparer, object item, int startIndex, int endIndex )
{
  if( startIndex > endIndex )
  {
    return startIndex;
  }
  var midIndex = startIndex + ( endIndex - startIndex ) / 2;
  return comparer.Compare( list[midIndex], item ) < 0 ?
    GetSortedIndex( list, comparer, item, midIndex + 1, endIndex ) :
    GetSortedIndex( list, comparer, item, startIndex, midIndex - 1 );
}

public static void InsertSorted( this IList list, IComparer comparer, object item )
{
  list.Insert( list.GetSortedIndex( comparer, item ), item );
}

Java-эквивалент

public static void main(String[] args)
{
   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 < 10; i++) {
       Integer rnd = new Integer(rand.nextInt(1000));
       int pos = Collections.binarySearch(l,rnd);
       if(pos < 0) pos = ~pos;
       l.add(pos,rnd);
   }    
   System.out.println(l);
}

Answer 2

Используйте TreeSet вместо List, он будет поддерживать порядок так, чтобы наибольшее значение всегда было SortedSet # last () . При использовании 1.6+ вы можете использовать NavigableSet методы; pollLast () вернется и удалит самое высокое значение.

NavigableSet<Integer> set = new TreeSet<Integer>();

//... setup data

Integer highest = set.pollLast();

set.add(rand.nextInt(1000));

Integer newHighest = set.pollLast();

Answer 3

Я очень удивлен, что никто еще не упомянул об этом ... Структура данных, которую вы ищете, это очередь с приоритетами . Это, без сомнения, самый эффективный способ решения этой задачи. Очередь приоритетов может быть реализована с использованием ряда различных методов (см. Связанную статью), но наиболее распространенным является двоичная куча . В самобинарном многообразии (что довольно типично) вставка и удаление занимают O(log n) время.

Кажется, что в библиотеке Java есть встроенный универсальный класс , PriorityQueue<E>, так что, похоже, вы можете использовать его напрямую. Не удивительно, что этот тип основан на структуре данных кучи, хотя и более специфичен, чем я не могу сказать. В любом случае, он должен быть очень подходящим для использования.

Answer 4

Используйте min-heap для хранения данных, и после каждой вставки нового случайного значения удаляйте min в O (1) раз.

После n итераций выполните n extract-min для получения отсортированного списка.

Answer 5

Очень простой оптимизацией было бы сравнить самое низкое значение в отсортированном массиве (таким образом, должно быть первым элементом) с новым значением перед его вставкой. Если новое значение больше этого значения, замените элемент новым значением и затем примените массив.

Answer 6

Collections.binarySearch ()

ArrayList.ensureCapcity ()

Ваш псевдокод вставляет набор новых элементов N в отсортированный список A размера S, а затем отбрасывает наименьший элемент. Используйте Collections.binarySearch () , чтобы найти точку вставки. [Прочтите примечание о влиянии на производительность, если ваш список не поддерживает RandomAccess. ArrayList поддерживает 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);

Но вы уверены, что хотите сбросить только 1 предмет? Или вы хотели вставить набор новых элементов N в отсортированный список A размера S и оставить только самые большие элементы S. В этом случае следите за минимальным значением:

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);
  }
}

Однако, если N большое, вам может быть лучше самостоятельно отсортировать N в отсортированный массив, отбросив меньший из N (0) или A (0), а затем объединить два отсортированных массива [оставлено как упражнение для читателя].

Если в конечном итоге вы используете реальный массив, см. Arrays.binarySearch и System.arraycopy .

Answer 7

Самый быстрый алгоритм, который я могу придумать, состоит в том, чтобы заменить наименьший элемент новым, если необходимо, и переместить новый на свое место, многократно меняя местами соседние элементы.

РЕДАКТИРОВАТЬ: Код предполагает, что массив отсортирован в порядке убывания, и, следовательно, последний элемент является наименьшим.

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;
    }
}

Answer 8

Это будет держать размер 4 и делать то, что вы хотите, как я понимаю.

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);
}    

Answer 9

Я не знаю, можете ли вы изменить структуру данных или какие другие операции вам нужно поддерживать, но куча лучше подходит для описываемых вами операций.

Answer 10

Если вы работаете с ArrayList, вы можете заменить последний номер в массиве новым, если новый номер больше, прежде чем сортировать массив.

Java Collections.sort использует сортировку слиянием, которая не является наиболее эффективным способом сортировки в этой ситуации. Вы хотите использовать двоичный поиск, чтобы найти точку вставки, а затем сдвинуть все последующие числа на единицу.

РЕДАКТИРОВАТЬ: Все это можно сделать с помощью всего лишь массива, например:

public static int addDiscard(int[] list, int number)
{
    if (number > list[list.length - 1])
    {
        int index = findInsertionIndex(list, number); // use binary search
        for (int i = list.length - 1; i > index; i--)
        {
            list[i] = list[i - 1];
        }
        list[index] = number;
    }
}