Как отсортировать почти отсортированный массив в максимально сжатые сроки?(Java)

Question

У меня есть массив значений, который почти, но не совсем отсортирован, с несколькими смещенными значениями (скажем, 50 из 100000).Как отсортировать его наиболее эффективно?(производительность здесь абсолютно важна и должна быть намного быстрее, чем O (N)).

Я знаю о smoothsort, но я не могу найти реализацию Java.Кто-нибудь знает, реализовано ли это уже?Или что я могу использовать для этой задачи вместо smoothsort?

Answer 1

На самом деле, Википедия содержит Java-реализацию smoothsort.Вы можете найти его здесь:

http://en.wikipedia.org/wiki/Smoothsort.

Answer 2

Сорт Коктейля

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

Answer 3

Как отметил Botz3000, вы не можете выполнить такую операцию быстрее, чем O(N).Самым основным элементом любого алгоритма было бы найти те записи в массиве, которые вышли из строя.Для этого требуется O (N), даже до того, как вы решите, что с ними делать.

Если действительно количество элементов "не по порядку" на порядки меньше общего количества элементов, вы могли бы использовать следующий алгоритм (предполагая связанный список):

1. Найдите все элементы, вышедшие из строя, и извлеките их из исходного списка в отдельный список, O(N)
2. В результате получается два списка:отсортированный список и краткий извлеченный список
3. Для каждого из извлеченных элементов вставьте их в отсортированный список.Это было бы O (log (N)) для каждого, итого равно O(Xlog (N)), где X - количество извлеченных элементов.Если X очень мало по отношению к N, то в итоге вы получите в общей сложности O (N).

Answer 4

Для этого существует много хороших алгоритмов.

Smoothsort - мое личное любимое блюдо...Я действительно рассчитал все математически здесь если вам интересно, почему это работает так хорошо.

Довольно хорошим алгоритмом для уже отсортированных данных является естественная сортировка слиянием, который представляет собой восходящую версию mergesort, которая работает, обрабатывая входные данные как последовательность отсортированных поддиапазонов, затем выполняя несколько проходов по диапазону, объединяя соседние отсортированные диапазоны.Он выполняется за O (n) время, если данные уже отсортированы (поскольку он может обнаружить, что существует только один отсортированный диапазон), и O (n lg n) в худшем случае.Этот алгоритм работает довольно хорошо, если данные "отсортированы по блокам".;то есть он состоит из множества отсортированных блоков, расположенных прямо рядом друг с другом.

Прямая сортировка вставкой определенно хорошо работает для данных, отсортированных в основном, но может очень сильно ухудшиться при большом количестве входных данных.Некоторые действительно хорошие сорта (например самоанализ) на самом деле используйте это свойство insertion sort для выполнения "шага очистки" входных данных.

Answer 5

[Sun] JDK7 имеет (или будет иметь) реализацию Тим сортирует (из Python).Это сортировка слиянием, которая использует преимущества порядка, уже существующего в массиве.

Answer 6

Smoothsort или Timsort - отличные алгоритмы, и их было бы разумно использовать.

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

Answer 7

Просто для того, чтобы выложить это на стол, хорошо реализованная пузырьковая сортировка, безусловно, была бы здесь самым простым алгоритмом.С наихудшим случаем O (n * m), где m - число перемещений.Часть m сильно зависит от схемы перемещений, обычно общая сложность будет равна O (n).

Answer 8

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

Answer 9

Внедрите то, что мы называли в школе а Вид оболочки.Это подмассивы с сортировкой пузырьков.Подмассив с шагом k представляет собой массив элементов с обозначениями 0, k, 2k, 3k...

Если вы выберете k = 3i + 1 и выполните несколько пузырьковых сортировок, начиная с более высоких i-s вплоть до 0, время будет меньше в почти отсортированном массиве.

Answer 10

Это оригинальная Java - реализация Smoothsort , которая раньше была доступна через Статья в Википедии.

// by keeping these constants, we can avoid the tiresome business
// of keeping track of Dijkstra's b and c. Instead of keeping
// b and c, I will keep an index into this array.

static final int LP[] = { 1, 1, 3, 5, 9, 15, 25, 41, 67, 109,
    177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891,
    35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457,
    1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703,
    48315633, 78176337, 126491971, 204668309, 331160281, 535828591,
    866988873 // the next number is > 31 bits.
};

public static <C extends Comparable<? super C>> void sort(C[] m,
    int lo, int hi) {
  int head = lo; // the offset of the first element of the prefix into m

  // These variables need a little explaining. If our string of heaps
  // is of length 38, then the heaps will be of size 25+9+3+1, which are
  // Leonardo numbers 6, 4, 2, 1. 
  // Turning this into a binary number, we get b01010110 = 0x56. We represent
  // this number as a pair of numbers by right-shifting all the zeros and 
  // storing the mantissa and exponent as "p" and "pshift".
  // This is handy, because the exponent is the index into L[] giving the
  // size of the rightmost heap, and because we can instantly find out if
  // the rightmost two heaps are consecutive Leonardo numbers by checking
  // (p&3)==3

  int p = 1; // the bitmap of the current standard concatenation >> pshift
  int pshift = 1;

  while (head < hi) {
    if ((p & 3) == 3) {
      // Add 1 by merging the first two blocks into a larger one.
      // The next Leonardo number is one bigger.
      sift(m, pshift, head);
      p >>>= 2;
      pshift += 2;
    } else {
      // adding a new block of length 1
      if (LP[pshift - 1] >= hi - head) {
        // this block is its final size.
        trinkle(m, p, pshift, head, false);
      } else {
        // this block will get merged. Just make it trusty.
        sift(m, pshift, head);
      }

      if (pshift == 1) {
        // LP[1] is being used, so we add use LP[0]
        p <<= 1;
        pshift--;
      } else {
        // shift out to position 1, add LP[1]
        p <<= (pshift - 1);
        pshift = 1;
      }
    }
    p |= 1;
    head++;
  }

  trinkle(m, p, pshift, head, false);

  while (pshift != 1 || p != 1) {
    if (pshift <= 1) {
      // block of length 1. No fiddling needed
      int trail = Integer.numberOfTrailingZeros(p & ~1);
      p >>>= trail;
      pshift += trail;
    } else {
      p <<= 2;
      p ^= 7;
      pshift -= 2;

      // This block gets broken into three bits. The rightmost
      // bit is a block of length 1. The left hand part is split into
      // two, a block of length LP[pshift+1] and one of LP[pshift].
      // Both these two are appropriately heapified, but the root
      // nodes are not necessarily in order. We therefore semitrinkle
      // both of them

      trinkle(m, p >>> 1, pshift + 1, head - LP[pshift] - 1, true);
      trinkle(m, p, pshift, head - 1, true);
    }

    head--;
  }
}

private static <C extends Comparable<? super C>> void sift(C[] m, int pshift,
    int head) {
  // we do not use Floyd's improvements to the heapsort sift, because we
  // are not doing what heapsort does - always moving nodes from near
  // the bottom of the tree to the root.

  C val = m[head];

  while (pshift > 1) {
    int rt = head - 1;
    int lf = head - 1 - LP[pshift - 2];

    if (val.compareTo(m[lf]) >= 0 && val.compareTo(m[rt]) >= 0)
      break;
    if (m[lf].compareTo(m[rt]) >= 0) {
      m[head] = m[lf];
      head = lf;
      pshift -= 1;
    } else {
      m[head] = m[rt];
      head = rt;
      pshift -= 2;
    }
  }

  m[head] = val;
}

private static <C extends Comparable<? super C>> void trinkle(C[] m, int p,
    int pshift, int head, boolean isTrusty) {

  C val = m[head];

  while (p != 1) {
    int stepson = head - LP[pshift];

    if (m[stepson].compareTo(val) <= 0)
      break; // current node is greater than head. Sift.

    // no need to check this if we know the current node is trusty,
    // because we just checked the head (which is val, in the first
    // iteration)
    if (!isTrusty && pshift > 1) {
      int rt = head - 1;
      int lf = head - 1 - LP[pshift - 2];
      if (m[rt].compareTo(m[stepson]) >= 0
          || m[lf].compareTo(m[stepson]) >= 0)
        break;
    }

    m[head] = m[stepson];

    head = stepson;
    int trail = Integer.numberOfTrailingZeros(p & ~1);
    p >>>= trail;
    pshift += trail;
    isTrusty = false;
  }

  if (!isTrusty) {
    m[head] = val;
    sift(m, pshift, head);
  }
}