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

Push_swap — первый алгоритмический проект Школы 42. Мы можем реализовать любой алгоритм для сортировки чисел, но лучшие получают более высокую оценку.

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

Этот алгоритм позволил мне получить высшую оценку за проект, и вы увидите, что его очень легко понять!

Понимание push_swap

Числа задаются в качестве аргументов программы на C, и мы должны преобразовать их с помощью функции atoi.

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

typedef struct node
{
  int   nb;
  struct node *next;
  struct node *prev;
} t_node;
  • nb — целое число в нашем стеке.
  • next — следующий элемент структуры в нашем двусвязном списке.
  • prev — предыдущий элемент структуры в нашем двусвязном списке.

Для сортировки чисел мы можем использовать 2 стопки (стек A и стек B, как показано ниже). Связанный список представляет стек A, и мы можем создать другой связанный список для стека B и присвоить ему NULL, поскольку он пуст.

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

  • sa: поменять местами первые два элемента стека A.
  • sb: поменять местами первые два элемента стека B.
  • ra: первый элемент стека A становится последним.
  • rb: первый элемент стека B становится последним.
  • rr: повернуть стек A и B (ra и rb).
  • rra: последний элемент стека A становится первым.
  • rrb: последний элемент стека B становится первым.
  • rrr: повернуть A и B в обратном порядке (rra и rrb).
  • pa: поместить в стек A.
  • pb: поместить в стек B.

Каждое движение должно отображаться в stdout, а отсортированные числа должны храниться в стеке A в конце программы. Стек B — это просто временный стек, помогающий нам сортировать небольшие диапазоны чисел.

Сортировка 3 чисел

Небольшая часть кода посвящена обработке 3 чисел. Вы увидите, что это будет очень полезно для алгоритма, используемого для сортировки 5 чисел.

Вам нужно отсортировать только 3 числа, поэтому 3! = 3 * 2 * 1 = 6 возможных комбинаций. Это очень легко реализовать, и вы можете сделать это в одиночку, но не забывайте, что вы никогда не должны использовать для этого более 3 ходов.

Сортировка 5 номеров

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

Обычный способ сделать это — поместить первые 2 числа в стек B, а затем повторно использовать написанный ранее код для сортировки 3 оставшихся чисел в стеке A. После этого все, что вам нужно сделать, отталкивает числа из стека B в стек A.

В зависимости от того, как вы это сделаете, вы можете превысить 12 ходов, что является максимумом, разрешенным 42 School для 5 номеров.

Не волнуйтесь, вы можете использовать мой тестер, чтобы убедиться, что вы не превысите 12 номеров. Он проверяет все комбинации из 5 чисел (5! = 120 комбинаций), так что у вас не будет сюрпризов во время оценки.

Алгоритм для больших стеков (100–500 чисел)

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

Этот стек, называемый stack C, не отображает никаких сообщений, и checker не знает об этом — это как внутренний связанный список, который мы будем использовать для определенного цель.

Push_swap — это не введение во временную сложность. Наоборот, это алгоритм, который должен максимально эффективно подстраиваться под требования субъекта: делать как можно меньше перемещений между стопками.

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

Для этого вам нужно клонировать числа A стека с помощью следующей функции. Обратите внимание, что тип стека C — int *, а не t_node *, потому что мы просто используем целые числа и не выполняем никакого перемещения.

int *stack_dup(t_node *stack)
{
  int  i;
  t_node *node;
  int *array;
  
  i = 0;
  node = stack;
  array = malloc(sizeof(int) * stack_size(stack));
  if (!array)
    return (NULL);
  while (node->next != stack)
  {
    array[i++] = node->nb;
    node = node->next;
  }
  array[i] = node->nb;
  return (array);
}

Эта функция подтверждает, что вы используете циклический двусвязный список, как и я. Не стесняйтесь редактировать его в соответствии с вашей структурой кода.

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

void    swap(int *a, int *b)
{
    int tmp;
    
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int *array, int start, int end)
{
    int pivot;
    int i;
    int j;

    pivot = array[end];
    i = start - 1;
    j = start;
    while (j <= end - 1) 
    {
        if (array[j] < pivot)
        {
            i++;
            swap(&array[i], &array[j]);
        }
        j++;
    }
    swap(&array[i + 1], &array[end]);
    return (i + 1);
}

void    quicksort(int *array, int start, int end)
{
    int pivot_index;

    if (start < end)
    {
        pivot_index = partition(array, start, end);
        quicksort(array, start, pivot_index - 1);
        quicksort(array, pivot_index + 1, end);
    }
}

Теперь мы знаем точное положение каждого числа в итоговом связанном списке даже до того, как напечатаем одно движение. Благодаря стеку C (массиву целых чисел) теперь мы можем присвоить каждому элементу в стеке A целое число, представляющее его позицию в отсортированном массиве. Назовем его index.

typedef struct node
{
 int   nb;
 int   index; // Position in the sorted array.
 struct node *next;
 struct node *prev;
} t_node;

На данный момент нам просто нужно написать ядро алгоритма. Но перед этим позвольте мне объяснить вам, как это работает!

Зная, что у нас уже есть конечная позиция каждого элемента в стеке A, мы можем поместить все числа в стек B (с помощью pb). Таким образом, мы можем вычислить для каждого элемента в стеке B, сколько ходов потребуется, чтобы поместить его в нужное место в стеке A.

Как вы можете видеть на рисунке, сначала мы выберем 6, потому что это тот, который делает наименьшее количество движений для правильного размещения в стеке A . Теперь мы можем выполнить правильные движения, чтобы сделать ход 6 в хорошей позиции.

Нам просто нужно выполнить следующие шаги в цикле, пока все числа не будут сохранены обратно в стек A:

  • Подсчитайте для каждого элемента в стеке B, сколько ходов потребуется, чтобы переместить его в отсортированную позицию в стеке A.
  • Выберите, чтобы вернуть в стек A число, требующее наименьшего количества ходов.
  • Повторяйте до тех пор, пока стек B не станет пустым.

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

typedef struct node
{
   int   nb;
   int   index;
   struct node *next;
   struct node *prev;
   int   value;
   int   sa;
   int   sb;
   int   ra;
   int   rb;
   int   rra;
   int   rrb;
} t_node;

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

Чтобы решить эту проблему, вам нужно найти индекс минимального значения в стеке A, а затем выполнить правильное количество ra или rra. (используйте ra если индекс ‹ stack_a_size или используйте rra если индекс ≥ stack_a_size) для соблюдения допустимого возрастающего порядка.

Вы можете найти полный код моего алгоритма push_swap в моей учетной записи GitHub: https://github.com/julien-ctx/push-swap

Оптимизация push_swap для максимальной оценки

Вот еще несколько вещей, которые вы ДОЛЖНЫ сделать, чтобы повысить производительность вашего алгоритма и иметь 100/100:

  • При выборе наилучшего числа для возврата в стек A, всякий раз, когда у вас одновременно есть ra и rb или rra и rrb одновременно, не забывайте использовать rr или ррр. Они помогут вам получить максимальную оценку в проекте push_swap.
  • Вместо того, чтобы помещать все в стек B в начале программы, вы можете найти самую длинную последовательность чисел, которая уже отсортирована в том порядке, в котором они будут отсортированы в конце. Вы должны сохранять отсортированную последовательность только в том случае, если она имеет тот же порядок в стеке C, а не числа, которые расположены только в порядке возрастания!

Тестирование вашего алгоритма сортировки

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

Этот тестер был сделан мной и позволяет вам проверить как ваш парсинг, так и ваш алгоритм на нескольких последовательностях чисел (3, 4, 5, 100, 500 чисел). Целые числа генерируются случайным образом, чтобы избежать какой-либо систематической ошибки в тестах.

Вы можете использовать простую команду Bash для запуска тестера:

  • Для Mac:
git clone [email protected]:julien-ctx/push-swap-tester.git && mv push-swap-tester/tester.py . && mv push-swap-tester/checker_Mac . && rm -rf push-swap-tester && chmod 777 checker_Mac && make && python3 tester.py
  • Для Linux:
git clone [email protected]:julien-ctx/push-swap-tester.git && mv push-swap-tester/tester.py . && mv push-swap-tester/checker_linux . && rm -rf push-swap-tester && chmod 777 checker_linux && sed -i -- 's/checker_Mac/checker_linux/g' tester.py && make && python3 tester.py

Понравилась ли вам эта статья? Вы можете сообщить мне об этом разными способами:

  • Похлопайте статье.
  • Напишите, что вы думаете о моей истории.
  • Подписаться на мой аккаунт.

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