Каков самый быстрый способ отсортировать массив из 7 целых чисел?

Я не так много знаю о техасском холдеме: имеет ли значение, какие масти P1 и P2, или имеет значение только то, одной масти они или нет? Если имеет значение только масть (P1) == масть (P2), тогда вы можете разделить эти два случая, у вас есть только 13x12 / 2 различных возможностей для P1 / P2, и вы можете легко предварительно рассчитать таблицу для двух случаев.

В противном случае я бы предложил что-то вроде этого:

(* C1 < C2 < P1 *)
for C1:=0 to P1-2 do 
   for C2:=C1+1 to P1-1 do 
      Cards[0] = C1;
      Cards[1] = C2;
      Cards[2] = P1;
      (* generate C3...C7 *)

(* C1 < P1 < C2 *)
for C1:=0 to P1-1 do 
   for C2:=P1+1 to 51 do 
      Cards[0] = C1;
      Cards[1] = P1;
      Cards[2] = C2;
      (* generate C3...C7 *)

(* P1 < C1 < C2 *)
for C1:=P1+1 to 51 do 
   for C2:=C1+1 to 51 do 
      Cards[0] = P1;
      Cards[1] = C1;
      Cards[2] = C2;
      (* generate C3...C7 *)

(это просто демонстрация для одной карты P1, вам придется расширить ее для P2, но я думаю, что это просто. Хотя вам придется много печатать ...) Таким образом, сортировка не займет никакого времени вообще. Сгенерированные перестановки уже заказаны.

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

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

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

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

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

Как только у вас есть перестановка, легко отсортировать ее в минимальном наборе свопов.

Поскольку последние 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;

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

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

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

Вы также можете развернуть циклы, которые сэкономят вам, возможно, 8 операторов или выполнение, но сделают всю процедуру примерно в 4-5 раз длиннее, что может испортить коэффициент попадания в кеш инструкций.

Учитывая P (от 0 до 2), C (от 0 до 5) и копирование в H (от 0 до 6) с уже отсортированным 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 операторов (но все же быстрее, чем любой другой подход к сортировке).

Для семи чисел самый эффективный алгоритм, который существует в отношении количества сравнений, - это алгоритм Форда-Джонсона. Фактически, wikipedia ссылается на легко найденную в 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 и просто создадите для петли соответственно для каждого варианта, в котором P1 и P2 могут появиться в списке.

Например, отсортируйте P1 и P2 так, чтобы P1 ‹P2. Сделаем Po1 и Po2 позициями от 0 до 6 P1 и P2 в списке. Затем сделайте это:

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 комбинаций).

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

Для 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 элементов будет больше, но его не так уж сложно сгенерировать.

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

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

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

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;

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

Преобразуйте исходные карты в биты 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;
}

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

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

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

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

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

Но длинный ответ короткий, используйте сортировку по ведру.

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

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

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

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

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

Учитывая, что последние 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;

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

Ваше здоровье

Вот ваша основная сортировка 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;

Если вы ищете оптимальную сортировку с очень низкими накладными расходами, вам следует создать сеть сортировки. Вы можете сгенерировать код для сети из 7 целых чисел, используя алгоритм Бозе-Нельсона.

Это гарантирует фиксированное количество сравнений и такое же количество свопов в худшем случае.

Сгенерированный код некрасивый, но оптимальный.

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

С маленькими числами двоичное разделение является излишним, и в любом случае уместно тройное разделение: одна новая карта в основном будет разделена на две и три, а именно. 2 + 3 или 3 + 2, две карты на одиночные и парные, например 2 + 1 + 2.

Таким образом, наиболее эффективный по времени подход к размещению новой карты меньшего размера - это сравнение с [1] (то есть пропустить [0]), а затем поиск влево или вправо, чтобы найти карту, которую она должна сместить, затем поменять местами и переместиться вправо. (смещение, а не пузыри), сравнивая с большей новой картой, пока вы не найдете, куда она идет. После этого вы будете двигаться вперед по двое (вставлены две карточки). Переменные, содержащие новые карты (и свопы), должны быть регистрами.

Подход поиска будет быстрее, но потребует больше памяти.

Используйте сеть сортировки, как в этом коде C ++:

template<class T> 
inline void sort7(T data) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
//DD = Define Data, create a local copy of the data to aid the optimizer.
#define DD1(a)   register auto data##a=*(data+a);
#define DD2(a,b) register auto data##a=*(data+a);register auto data##b=*(data+b);
//CB = Copy Back
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(3,4) SORT2(3,4)
  DD2(5,6) SORT2(5,6)
  DD1(0) SORT2(0,2)
  SORT2(3,5) 
  SORT2(4,6) 
  SORT2(0,1)
  SORT2(4,5) 
  SORT2(2,6) CB1(6)
  SORT2(0,4) 
  SORT2(1,5)
  SORT2(0,3) CB1(0) 
  SORT2(2,5) CB1(5)
  SORT2(1,3) CB1(1) 
  SORT2(2,4) CB1(4)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Используйте функцию выше, если вы хотите передать ей итератор или указатель, и используйте функцию ниже, если вы хотите передать ей семь аргументов один за другим. Кстати, использование шаблонов позволяет компиляторам генерировать действительно оптимизированный код, поэтому не используйте template<>, если вам не нужен код C (или код другого языка).

template<class T>
inline void sort7(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5, T& e6) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(3,4) SORT2(3,4)
  DD2(5,6) SORT2(5,6)
  DD1(0) SORT2(0,2)
  SORT2(3,5)
  SORT2(4,6)
  SORT2(0,1)
  SORT2(4,5)
  SORT2(2,6) CB1(6)
  SORT2(0,4)
  SORT2(1,5)
  SORT2(0,3) CB1(0)
  SORT2(2,5) CB1(5)
  SORT2(1,3) CB1(1)
  SORT2(2,4) CB1(4)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}