Как отсортировать массив, используя минимальное количество записей?

В интервью моему другу был задан вопрос:

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

Ответы

Ответ 1

Если массив короче (т.е. меньше, чем около 100 элементов), Сортировка выбора часто является лучшим выбором, если вы также хотите уменьшить количество записей.

Из Википедии:

Другим ключевым отличием является то, что сортировка выбора всегда выполняет Θ (n) свопы, в то время как сортировка вставки выполняется Θ (n 2) свопы в среднем и худшем случаев. Поскольку свопы требуют написания к массиву, сортировка сортировки предпочтительнее, если запись в память значительно дороже, чем чтение. Это обычно имеет место, если элементы огромны, но ключи маленький. Еще один пример, где письмо времена имеют решающее значение, хранящийся массив в EEPROM или Flash. Там нет другого алгоритм с меньшим перемещением данных.

Для больших массивов/списков Quicksort и друзья будут обеспечивать лучшую производительность, но, возможно, скорее всего, потребуется больше записей, чем сортировка.

Если вам интересно это фантастический сайт визуализации вида, который позволяет вам смотреть, как определенные алгоритмы сортировки выполняют свою работу, а также "расы" разные алгоритмы сортировки друг против друга.

Ответ 2

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

Алгоритм, который в два раза больше, чем сортировка выбора, "cycle" sort, который не меняет местами. Сортировка циклов даст максимум n записей в сортировке. Количество записей абсолютно минимизировано. Он будет записывать только один номер в конечный пункт назначения, и только тогда, если он еще не существует.

Он основан на идее, что все перестановки являются продуктами циклов, и вы можете просто циклически перебирать каждый цикл и записывать каждый элемент в соответствующее место один раз.

import java.util.Random;
import java.util.Collections;
import java.util.Arrays;

public class CycleSort {
  public static final <T extends Comparable<T>> int cycleSort(final T[] array) {
    int writes = 0;

    // Loop through the array to find cycles to rotate.
    for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) {
      T item = array[cycleStart];

      // Find where to put the item.
      int pos = cycleStart;
      for (int i = cycleStart + 1; i < array.length; i++)
        if (array[i].compareTo(item) < 0) pos++;

      // If the item is already there, this is not a cycle.
      if (pos == cycleStart) continue;

      // Otherwise, put the item there or right after any duplicates.
      while (item.equals(array[pos])) pos++;
      {
        final T temp = array[pos];
        array[pos] = item;
        item = temp;
      }
      writes++;

      // Rotate the rest of the cycle.
      while (pos != cycleStart) {
        // Find where to put the item.
        pos = cycleStart;
        for (int i = cycleStart + 1; i < array.length; i++)
          if (array[i].compareTo(item) < 0) pos++;

        // Put the item there or right after any duplicates.
        while (item.equals(array[pos])) pos++;
        {
          final T temp = array[pos];
          array[pos] = item;
          item = temp;
        }
        writes++;
      }
    } 
    return writes;
  }

  public static final void main(String[] args) {
    final Random rand = new Random();

    final Integer[] array = new Integer[8];
    for (int i = 0; i < array.length; i++) { array[i] = rand.nextInt(8); }

    for (int iteration = 0; iteration < 10; iteration++) {
      System.out.printf("array: %s ", Arrays.toString(array));
      final int writes = cycleSort(array);
      System.out.printf("sorted: %s writes: %d\n", Arrays.toString(array), writes);
      Collections.shuffle(Arrays.asList(array));
    }
  }
}

Несколько примеров запуска  :

array: [3, 2, 6, 1, 3, 1, 4, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [1, 3, 4, 1, 3, 2, 4, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 4
array: [3, 3, 1, 1, 4, 4, 2, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [1, 1, 3, 2, 4, 3, 6, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [3, 2, 3, 4, 6, 4, 1, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [6, 2, 4, 3, 1, 3, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [6, 3, 2, 4, 3, 1, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 5
array: [4, 2, 6, 1, 1, 4, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [4, 3, 3, 1, 2, 4, 6, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [1, 6, 4, 2, 4, 1, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [5, 1, 2, 3, 4, 3, 7, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 5
array: [5, 1, 7, 3, 2, 3, 4, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6
array: [4, 0, 3, 1, 5, 2, 7, 3] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 8
array: [4, 0, 7, 3, 5, 1, 3, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [3, 4, 2, 7, 5, 3, 1, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [0, 5, 3, 2, 3, 7, 1, 4] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6
array: [1, 4, 3, 7, 2, 3, 5, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [1, 5, 0, 7, 3, 3, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [0, 5, 7, 3, 3, 4, 2, 1] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 4
array: [7, 3, 1, 0, 3, 5, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7

Ответ 3

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

Алгоритм должен выглядеть следующим образом:

i = 0

do
   search for the minimum in range [i..n)
   swap a[i] with a[minPos]
   i = i + 1
repeat until i = n.

Поиск минимума может стоить вам почти ничего, своп стоит вам 3 записи, я ++ стоит вам 1..

Это называется выбор сортировки, как указано золой. (Извините, я не знал, что это сортировка:()

Ответ 4

Один вариант для больших массивов выглядит следующим образом (предполагая n элементов):

  • Инициализировать массив с n элементами с номером 0..n-1
  • Сортировка массива с использованием любого алгоритма сортировки. В качестве функции сравнения сравните элементы во входном наборе с соответствующими номерами (например, чтобы сравнить 2 и 4, сравните 2-й и 4-й элементы в наборе входных данных). Это превращает массив с шага 1 в перестановку, которая представляет отсортированный порядок набора входных данных.
  • Итерации через элементы в перестановке, выписывая блоки в порядке, заданном массивом. Для этого требуется ровно n записей, минимум.

Чтобы сортировать на месте, на шаге 3 вы должны идентифицировать циклы в перестановке и "повернуть" их по мере необходимости, чтобы привести к упорядоченному порядку.

Ответ 5

Если числа находятся в определенном диапазоне, задача может выполняться в O (n) времени вычисления, что является частным случаем упорядочения, его делается путем создания массива и отображения каждого числа в указанную позицию.

Если числа не находятся в диапазоне, наилучшие способы сделать это - использовать QuickSort или HeapSort, который сортирует int O (Log2N), но некоторые предпочитают QuickSort, как я.

Вы можете найти реализацию QuickSort на любом языке практически в любом месте, просто в Google, и вы найдете его в считанные секунды.

Адаптация HeapSort доступна при организации внешних данных, означает данные, которые не хранятся в памяти, но на жестком диске, наиболее распространенные при работе с огромными массивами.

Надеюсь, что смогу помочь С наилучшими пожеланиями и удачи!

Ответ 6

Упорядочение, которое я имел в виду в O (n), похоже на сортировку выбора (предыдущий пост), полезный, когда у вас есть небольшой диапазон ключей (или вы заказываете числа между двумя диапазонами)

Если у вас есть массив чисел, где числа будут между -10 и 100, тогда вы можете создать массив из 110 и быть уверенным, что все числа будут в нем входить, если вы будете рассматривать повторяющиеся числа, то идея такая же, но у вас будут списки вместо чисел в отсортированном массиве

псевдо-идея такова:

N: max value of your array
tosort //array to be sorted
sorted = int[N]

for i = 0 to length(tosort)
do
   sorted[tosort[i]]++;
end

finalarray = int[length(tosort)]

k = 0
for i = 0 to N
do
  if ( sorted[i] > 0 )
    finalarray[k] = i
    k++;
  endif
end

finalarray будет иметь окончательный отсортированный массив, и у вас будут операции записи O (N), где N - диапазон массива. Еще раз, это полезно при использовании ключей внутри определенного диапазона, но, возможно, в вашем случае.

С наилучшими пожеланиями и удачи!