Что самый быстрый путь состоит в том, чтобы отсортировать массив 7 целых чисел?

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

Ура

Учитывая, что последние 5 элементов всегда сортируются:

for i := 0 to 1 do begin
  j := i;
  x := array[j];
  while (j+1 <= 6) and (array[j+1] < x) do begin
    array[j] := array[j+1];
    inc(j);
  end;
  array[j] := X;
end;

В ответы. Учитывая его требования к скорости и крошечный размер набора данных, я не стал бы выполнять ЛЮБЫЕ циклы.

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

Я задаюсь вопросом, правильный ли это подход. Как вы собираетесь анализировать комбинацию из 7 карт ?? Я думаю, вы все равно собираетесь преобразовать его в какое-то другое представление для анализа. Разве массив 4x13 не был бы более полезным представлением? (И это сделало бы сортировочный выпуск спорное, во всяком случае.)

Предполагая, что вы требуется массив карт в конце.

Сопоставьте исходные карты с битами в 64-битном целом числе (или любом целом с> = 52 битами).

Если во время начального сопоставления массив сортируется, не используйте Не меняйте его.

Разделите целое число на полубайты - каждый будет соответствовать значениям от 0x0 до 0xf.

Используйте полубайты в качестве индексов для соответствующих отсортированных подмассивов. Вам понадобится 13 наборов из 16 подмассивов (или всего 16 подмассивов и используйте второе косвенное обращение, или выполняйте битовые операции вместо поиска ответа; что быстрее, зависит от платформы).

непустые подмассивы в окончательный массив.

Вы можете использовать больше, чем полубайты, если хотите; байты дадут 7 наборов по 256 массивов и увеличат вероятность того, что непустые массивы потребуют объединения.

Предполагается, что ветки дороги, а доступ к кэшируемым массивам дешев.

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

// for general case of 7 from 52, rather than assuming last 5 sorted
uint32_t card_masks[16][5] = {
    { 0, 0, 0, 0, 0 },
    { 1, 0, 0, 0, 0 },
    { 2, 0, 0, 0, 0 },
    { 1, 2, 0, 0, 0 },
    { 3, 0, 0, 0, 0 },
    { 1, 3, 0, 0, 0 },
    { 2, 3, 0, 0, 0 },
    { 1, 2, 3, 0, 0 },
    { 4, 0, 0, 0, 0 },
    { 1, 4, 0, 0, 0 },
    { 2, 4, 0, 0, 0 },
    { 1, 2, 4, 0, 0 },
    { 3, 4, 0, 0, 0 },
    { 1, 3, 4, 0, 0 },
    { 2, 3, 4, 0, 0 },
    { 1, 2, 3, 4, 0 },
};

void sort7 ( uint32_t* cards) {
    uint64_t bitset = ( ( 1LL << cards[ 0 ] ) | ( 1LL << cards[ 1LL ] ) | ( 1LL << cards[ 2 ] ) | ( 1LL << cards[ 3 ] ) | ( 1LL << cards[ 4 ] ) | ( 1LL << cards[ 5 ] ) | ( 1LL << cards[ 6 ] ) ) >> 1;

    uint32_t*   p    = cards;
    uint32_t    base = 0;

    do {
        uint32_t* card_mask = card_masks[ bitset & 0xf ];

        // you might remove this test somehow, as well as unrolling the outer loop
        // having separate arrays for each nibble would save 7 additions and the increment of base
        while ( *card_mask )
            *(p++) = base + *(card_mask++);

        bitset >>= 4;
        base += 4;
    } while ( bitset );
}

void print_cards ( uint32_t* cards ) {
    printf ( "[ %d %d %d %d %d %d %d ]\n", cards[0], cards[1], cards[2], cards[3], cards[4], cards[5], cards[6] );
}

int main ( void ) {
    uint32_t cards[7] = { 3, 9, 23, 17, 2, 42, 52 };

    print_cards ( cards );
    sort7 ( cards );
    print_cards ( cards );

    return 0;
}

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

object Sort7 {
  def left(i: Int) = i * 4
  def right(i: Int) = i * 4 + 1
  def up(i: Int) = i * 4 + 2
  def value(i: Int) = i * 4 + 3

  val a = new Array[Int](7 * 4)
  def reset = {
    0 until 7 foreach { 
      i => {
        a(left(i)) = -1
        a(right(i)) = -1
        a(up(i)) = -1
        a(value(i)) = scala.util.Random.nextInt(52)
      }
    }
  }

  def sortN(i : Int) {
    var index = 0
    def getNext = if (a(value(i)) < a(value(index))) left(index) else right(index)
    var next = getNext
    while(a(next) != -1) {
      index = a(next)
      next = getNext
    }
    a(next) = i
    a(up(i)) = index
  }

  def sort = 1 until 7 foreach (sortN(_))

  def print {
    traverse(0)
    def traverse(i: Int): Unit = {
      if (i != -1) {
        traverse(a(left(i)))
        println(a(value(i)))
        traverse(a(right(i)))
      }
    }
  }
}

Поскольку последние 5 элементов уже отсортированы, код может быть написан только для изменения положения первых 2 элементов. Поскольку вы используете Паскаль, я написал и протестировал алгоритм сортировки, который может выполняться 2118760 раз примерно за 62 миллисекунды.

procedure SortT7Cards(var Cards: T7Cards);
const
  CardsLength = Length(Cards);
var
  I, J, V: Integer;
  V1, V2: Integer;
begin
  // Last 5 items will always be sorted, so we want to place the first two into
  // the right location.
  V1 := Cards[0];
  V2 := Cards[1];
  if V2 < V1 then
  begin
    I := V1;
    V1 := V2;
    V2 := I;
  end;

  J := 0;
  I := 2;
  while I < CardsLength do
  begin
    V := Cards[I];
    if V1 < V then
    begin
      Cards[J] := V1;
      Inc(J);
      Break;
    end;
    Cards[J] := V;
    Inc(J);
    Inc(I);
  end;
  while I < CardsLength do
  begin
    V := Cards[I];
    if V2 < V then
    begin
      Cards[J] := V2;
      Break;
    end;
    Cards[J] := V;
    Inc(J);
    Inc(I);
  end;
  if J = (CardsLength - 2) then
  begin
    Cards[J] := V1;
    Cards[J + 1] := V2;
  end
  else if J = (CardsLength - 1) then
  begin
    Cards[J] := V2;
  end;
end;

Это самый быстрый метод: поскольку 5-карточный list уже отсортирован, отсортируйте список из двух карт (сравнение и обмен), а затем объедините два списка, что составляет O (k * (5 + 2). В этом случае (k) обычно будет 5: цикл test (1), compare (2), copy (3), приращение списка ввода (4) и приращение списка вывода (5). Это 35 + 2,5. Добавьте инициализацию цикла, и вы получите 41,5 операторов, всего .

Вы также можете развернуть циклы, что сэкономит вам, возможно, 8 операторов или выполнение, с уже отсортированным C () (по возрастанию):

If P(0) > P(1) Then
    // Swap:
    T = P(0)
    P(0) = P(1)
    P(1) = T
    // 1stmt + (3stmt * 50%) = 2.5stmt
End

P(2), C(5) = 53    \\ Note these are end-of-list flags
k = 0     \\ P() index
J = 0     \\ H() index
i = 0     \\ C() index
// 4 stmt

Do While (j) < 7 
    If P(k) < C(I) then
        H(j) = P(k)
        k = k+1
    Else
        H(j) = C(i)
        j = j+1
    End if
    j = j+1
    // 5stmt * 7loops = 35stmt
Loop

И обратите внимание, что это быстрее, чем другой алгоритм, который был бы «самым быстрым», если бы вам нужно было по-настоящему отсортировать все 7 карточек: используйте битовую маску (52) для отображения & установите для всех 7 карт этот диапазон из всех возможных 52 карт (битовая маска), а затем просканируйте битовую маску, чтобы найти 7 установленных бит. Это в лучшем случае требует 60–120 операторов (но все же быстрее, чем любой другой подход к сортировке).

В псевдокоде:

int64 temp = 0;
int index, bit_position;

for index := 0 to 6 do
   temp |= 1 << cards[index];

for index := 0 to 6 do
begin
   bit_position = find_first_set(temp);
   temp &= ~(1 << bit_position);
   cards[index] = bit_position;
end;

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

Примечание: Вторая часть также может быть реализована путем перебора битов за линейное время, но на практике это может быть не быстрее:

index = 0;
for bit_position := 0 to 51 do
begin
   if (temp & (1 << bit_position)) > 0 then
   begin
      cards[index] = bit_position;
      index++;
   end;
end;

Для семи чисел наиболее эффективный алгоритм, существующий в отношении количества сравнений, - это алгоритм Форда-Джонсона. Фактически, википедия ссылается на статью, которую легко найти в Google, в которой утверждается, что книга Форда-Джонсона является лучшей для 47 чисел. К сожалению, ссылки на Форда-Джонсона не так-то легко найти, и алгоритм использует некоторые сложные структуры данных.

Он появляется в "Искусство компьютерного программирования", том 3, Дональда Кнута, если у вас есть доступ к нему. книга.

Там есть статья, описывающая FJ и более эффективную версию памяти здесь .

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

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

Order the two cards so that P1 > P2
Insert P1 going from the high end to the low end
(list) Insert P2 going from after P1 to the low end
(array) Insert P2 going from the low end to the high end

Как вы это сделаете, будет зависеть от структуры данных. С массивом вы будете менять местами каждый элемент, поэтому поместите P1 на 1-й, P2 и 7-й (в порядке убывания), а затем поменяйте местами P1 вверх, а затем P2 вниз. В списке вам просто нужно исправить указатели соответствующим образом.

Однако еще раз, из-за особенностей вашего кода, действительно лучше, если вы последуете предложению nikie и просто сгенерируете циклы for соответственно для каждого варианта, в котором P1 и P2 могут появляться в списке.

Например, отсортируйте P1 и P2 так, чтобы P1

Loop Po1 from 0 to 5
Loop Po2 from Po1 + 1 to 6
If (Po2 == 1) C1start := P2 + 1; C1end := 51 - 4
If (Po1 == 0 && Po2 == 2) C1start := P1+1; C1end := P2 - 1
If (Po1 == 0 && Po2 > 2) C1start := P1+1; C1end := 51 - 5
If (Po1 > 0) C1start := 0; C1end := 51 - 6
for C1 := C1start to C1end
  // Repeat logic to compute C2start and C2end
  // C2 can begin at C1+1, P1+1 or P2+1
  // C2 can finish at P1-1, P2-1, 51 - 3, 51 - 4 or 51 -5
  etc

Затем вы вызываете функцию, передающую Po1, Po2, P1, P2, C1, C2, C3, C4, C5, и заставляете эту функцию возвращать все возможные перестановки на основе Po1 и Po2 (это 36 комбинаций).

Лично я считаю, что это самое быстрое из возможных. Вы полностью избавляетесь от необходимости заказывать что-либо, потому что данные будут предварительно заказаны. В любом случае вы будете проводить некоторые сравнения для вычисления начала и конца, но их стоимость сведена к минимуму, поскольку большинство из них будет на самых внешних циклах, поэтому они не будут часто повторяться. И их можно даже лучше оптимизировать за счет большего количества дублирования кода.

Loop Po1 from 0 to 5
Loop Po2 from Po1 + 1 to 6
If (Po2 == 1) C1start := P2 + 1; C1end := 51 - 4
If (Po1 == 0 && Po2 == 2) C1start := P1+1; C1end := P2 - 1
If (Po1 == 0 && Po2 > 2) C1start := P1+1; C1end := 51 - 5
If (Po1 > 0) C1start := 0; C1end := 51 - 6
for C1 := C1start to C1end
  // Repeat logic to compute C2start and C2end
  // C2 can begin at C1+1, P1+1 or P2+1
  // C2 can finish at P1-1, P2-1, 51 - 3, 51 - 4 or 51 -5
  etc

Затем вы вызываете функцию, передающую Po1, Po2, P1, P2, C1, C2, C3, C4, C5, и заставляете эту функцию возвращать все возможные перестановки на основе Po1 и Po2 (это 36 комбинаций).

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

Loop Po1 from 0 to 5
Loop Po2 from Po1 + 1 to 6
If (Po2 == 1) C1start := P2 + 1; C1end := 51 - 4
If (Po1 == 0 && Po2 == 2) C1start := P1+1; C1end := P2 - 1
If (Po1 == 0 && Po2 > 2) C1start := P1+1; C1end := 51 - 5
If (Po1 > 0) C1start := 0; C1end := 51 - 6
for C1 := C1start to C1end
  // Repeat logic to compute C2start and C2end
  // C2 can begin at C1+1, P1+1 or P2+1
  // C2 can finish at P1-1, P2-1, 51 - 3, 51 - 4 or 51 -5
  etc

Затем вы вызываете функцию, передающую Po1, Po2, P1, P2, C1, C2, C3, C4, C5, и заставляете эту функцию возвращать все возможные перестановки на основе Po1 и Po2 (это 36 комбинаций).

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

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

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

Вот ваша основная сортировка O (n). Я не уверен, как он сравнивается с другими. Он использует развернутые циклы.

char card[7]; // the original table of 7 numbers in range 0..51
char table[52]; // workspace

// clear the workspace
memset(table, 0, sizeof(table));

// set the 7 bits corresponding to the 7 cards
table[card[0]] = 1;
table[card[1]] = 1;
...
table[card[6]] = 1;

// read the cards back out
int j = 0;
if (table[0]) card[j++] = 0;
if (table[1]) card[j++] = 1;
...
if (table[51]) card[j++] = 51;

JRL имеет в виду сортировку по корзине. Поскольку у вас есть конечный дискретный набор возможных значений, вы можете объявить 52 сегмента и просто отбросить каждый элемент в корзину за время O (1). Следовательно, сортировка по ведру - O (n). Без гарантии конечного числа различных элементов самая быстрая теоретическая сортировка - это O (n log n), что и есть такие вещи, как сортировка слиянием и быстрая сортировка. Это'

Взгляните на это:

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

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

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

Использовать минимальную сортировку. Ищите сразу минимальный и максимальный элементы и помещайте их в результирующий массив. Повторить трижды. (РЕДАКТИРОВАТЬ: Нет, я не буду пытаться измерять скорость теоретически: _))

var
cards,result: array[0..6] of integer;
i,min,max: integer;

begin
   n=0;
   while (n<3) do begin
      min:=-1;
      max:=52;
      for i from 0 to 6 do begin
          if cards[i]<min then min:=cards[i]
          else if cards[i]>max then max:=cards[i]
      end
      result[n]:=min;
      result[6-n]:=max;
      inc(n);
   end
   for i from 0 to 6 do 
       if (cards[i]<52) and (cards[i]>=0) then begin
           result[3] := cards[i];
           break;
       end
    { Result is sorted here! }
end

Не знаю, как вы это реализуете, но вы могли бы иметь массив из 52 вместо 7 и просто вставить карту в ее слот напрямую когда вы его получите, потому что не может быть дубликатов, таким образом вам никогда не придется сортировать массив. Это может быть быстрее в зависимости от того, как оно используется.

Для 7 элементов есть только несколько вариантов. Вы можете легко написать генератор, который производит метод сортировки всех возможных комбинаций из 7 элементов. Что-то вроде этого метода для 3 элементов:

if a[1] < a[2] {
    if a[2] < a[3] {
        // nothing to do, a[1] < a[2] < a[3]
    } else {
         if a[1] < a[3] {
             // correct order should be a[1], a[3], a[2]
             swap a[2], a[3]
         } else {
             // correct order should be a[3], a[1], a[2]
             swap a[2], a[3]
             swap a[1], a[3]
         }
    }
} else {
    // here we know that a[1] >= a[2]
    ...
}

Конечно метод для 7 элементов будет больше, но его не так сложно сгенерировать.

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

WRT ваше редактирование, если вы уже в основном в порядке сортировки (последние 5 элементов уже отсортированы), сортировка вставкой - определенно лучший способ. В почти отсортированном наборе данных он каждый раз превосходит быструю сортировку, даже для больших наборов. (Особенно для больших наборов! Это лучший сценарий вставки и худший вариант быстрой сортировки.)

Всего 5040 перестановок 7 элементов. Вы можете программно сгенерировать программу, которая найдет ту, которая представлена ​​вашим вводом, за минимальное количество сравнений. Это будет большое дерево инструкций if-then-else , каждая из которых сравнивает фиксированную пару узлов, например if (a [3] <= a [6]) .

Сложная часть - решить, какие 2 элемента сравнивать в конкретном внутреннем узле. Для этого вы должны принять во внимание результаты сравнений в узлах-предках от корневого до конкретного узла (например, a [0] <= a [1], а не a [2] <= a [7 ], a [2] <= a [5] ) и набор возможных перестановок, удовлетворяющих сравнениям. Сравните пару элементов, которые разделяют набор на как можно более равные части (минимизируйте размер большей части).

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

Я полагаю, для того, чтобы это было действительно эффективно, нам понадобится структура типа связанного списка, которая поддерживает операции: InsertAtPosition () и DeleteAtPosition () и будет эффективной при этом.