Version: 6
Навигатор по разделам:
| Summary: This project will make you sort data on a stack, with a limited set of instructions, using the lowest possible number of actions. To succeed you’ll have to manipulate various types of algorithms and choose the most appropriate solution (out of many) for an optimized data sorting. | Резюме: Этот проект заставит вас сортировать данные в стеке с ограниченным набором инструкций, используя минимально возможное количество действий. Чтобы добиться успеха, вам придется манипулировать различными типами алгоритмов и выбирать наиболее подходящее решение (из многих) для оптимизированной сортировки данных. | | --- | --- |
| The Push swap project is a very simple and a highly straightforward algorithm project: data must be sorted.
| Проект Push swap — это очень простой и очень простой алгоритмический проект: данные должны быть отсортированы. | | --- | --- | | You have at your disposal a set of integer values, 2 stacks, and a set of instructions to manipulate both stacks. | В вашем распоряжении набор целочисленных значений, 2 стека и набор инструкций для управления обоими стеками. | | Your goal? Write a program in C called push_swap which calculates and displays on the standard output the smallest program, made of Push swap language instructions, that sorts the integers received as arguments.
| Ваша цель? Напишите на C программу с именем push_swap, которая вычисляет и выводит на стандартный вывод самую маленькую программу, составленную из инструкций языка подкачки Push, которая сортирует целые числа, полученные в качестве аргументов. | | Easy? We’ll see... | Легко ? Посмотрим... |
| Writing a sorting algorithm is always a very important step in a developer’s journey. It is often the first encounter with the concept of complexity | Написание алгоритма сортировки всегда является очень важным шагом на пути разработчика. Часто это первое столкновение с понятием сложности. |
|---|---|
| Sorting algorithms and their complexity are part of the classic questions discussed during job interviews. It’s probably a good time to look at these concepts since you’ll have to face them at some point. | Алгоритмы сортировки и их сложность являются частью классических вопросов, обсуждаемых на собеседованиях. Вероятно, сейчас самое время взглянуть на эти концепции, поскольку в какой-то момент вам придется с ними столкнуться. |
| The learning objectives of this project are rigor, use of C, and use of basic algorithms. Especially focusing on their complexity. | Учебными целями этого проекта являются строгость, использование C и использование основных алгоритмов. Особенно обращая внимание на их сложность. |
| Sorting values is simple. To sort them the fastest way possible is less simple. Especially because from one integers configuration to another, the most efficient sorting solution can differ. | Сортировка значений проста. Отсортировать их самым быстрым способом не так просто. Тем более, что от одной конфигурации целых чисел к другой наиболее эффективное решение для сортировки может отличаться. |
| • Your project must be written in C. | Ваш проект должен быть написан на C. |
|---|---|
| • Your project must be written in accordance with the Norm. If you have bonus | |
| files/functions, they are included in the norm check and you will receive a 0 if there | |
| is a norm error inside. | Ваш проект должен быть написан в соответствии с Нормой. Если у вас есть бонус |
| файлы/функции, они включены в нормальную проверку, и вы получите 0, если есть | |
| это ошибка нормы внутри. | |
| • All heap allocated memory space must be properly freed when necessary. No leaks | |
| will be tolerated. | При необходимости все пространство памяти, выделенное в куче, должно быть должным образом освобождено. Нет утечек |
| будут терпеть. | |
| • If the subject requires it, you must submit a Makefile which will compile your | |
| source files to the required output with the | |
flags -Wall, -Wextra and -Werror, use |
|
cc, and your Makefile must not relink. |
Если предмет требует этого, вы должны отправить Makefile, который скомпилирует ваш |
| исходные файлы в требуемый вывод с | |
| флаги -Wall, -Wextra и -Werror, использовать | |
| cc, и ваш Makefile не должен перелинковываться. | |
| • Your Makefile must at least contain the rules $(NAME), all, clean, fclean and | |
| re. |
| Ваш Makefile должен как минимум содержать правила $(NAME), all, clean, fclean и re. | | • To turn in bonuses to your project, you must include a rule bonus to your Makefile, which will add all the various headers, librairies or functions that are forbidden on the main part of the project. Bonuses must be in a different file _bonus.{c/h} if the subject does not specify anything else. Mandatory and bonus part evaluation is done separately.
| Чтобы включить бонусы в свой проект, вы должны включить бонус правила в свой Makefile, который добавит все различные заголовки, библиотеки или функции, которые запрещены на основная часть проекта. Бонусы должны быть в другом файле _bonus.{c/h}, если в теме больше ничего не указано. Обязательная и бонусная часть оценки делается отдельно. | | • If your project allows you to use your libft, you must copy its sources and its associated Makefile in a libft folder with its associated Makefile. Your project’s Makefile must compile the library by using its Makefile, then compile the project.
| Если ваш проект позволяет вам использовать ваш libft, вы должны скопировать его исходный код и связанный Makefile в папке libft с соответствующим Makefile. Ваш проект Makefile должен скомпилировать библиотеку, используя ее Makefile, а затем скомпилировать проект. | | • We encourage you to create test programs for your project even though this work won’t have to be submitted and won’t be graded. It will give you a chance to easily test your work and your peers’ work. You will find those tests especially useful during your defence. Indeed, during defence, you are free to use your tests and/or the tests of the peer you are evaluating.
| Мы рекомендуем вам создавать тестовые программы для вашего проекта, даже если эта работа не нужно будет отправлять и не будет оцениваться. Это даст вам шанс чтобы легко проверить свою работу и работу своих сверстников. Вы найдете эти тесты особенно полезно во время вашей защиты. Действительно, во время защиты вы можете использовать свои тесты и/или тесты сверстника, которого вы оцениваете. | | • Submit your work to your assigned git repository. Only the work in the git repository will be graded. If Deepthought is assigned to grade your work, it will be done after your peer-evaluations. If an error happens in any section of your work during Deepthought’s grading, the evaluation will stop. | Отправьте свою работу в назначенный репозиторий git. Оцениваться будет только работа в репозитории git. Если Deepthought будет назначен для оценки вашей работы, это будет сделано после вашей коллегиальной оценки. Если во время оценивания Deepthought произойдет ошибка в каком-либо разделе вашей работы, оценка будет остановлена. |
V.1 The rules / Правила
| • You have 2 stacks named a and b. | У вас есть 2 стека с именами a и b. |
|---|---|
| • At the beginning: | С начала: |
| - The stack a contains a random amount of negative and/or positive numbers which cannot be duplicated. | |
Стек a содержит случайное количество отрицательных и/или положительных чисел, которые не могут быть продублированы. |
|
| - The stack b is empty. | Стек b пуст. |
| • The goal is to sort in ascending order numbers into stack a. To do so you have the following operations at your disposal: | Цель состоит в том, чтобы отсортировать числа в порядке возрастания в стеке a. Для этого в вашем распоряжении следующие операции: |
| sa (swap a): Swap the first 2 elements at the top of stack a. | |
| Do nothing if there is only one or no elements. | sa (swap a): поменять местами первые 2 элемента в верхней части стека a. |
| Ничего не делать, если есть только один элемент или его нет. | |
| sb (swap b): Swap the first 2 elements at the top of stack b. | |
| Do nothing if there is only one or no elements. | sb (swap b): поменять местами первые 2 элемента в верхней части стека b. |
| Ничего не делать, если есть только один элемент или его нет. | |
| ss : sa and sb at the same time. | ss : sa и sb одновременно. |
| pa (push a): Take the first element at the top of b and put it at the top of a. | |
| Do nothing if b is empty. | pa (push a): взять первый элемент в верхней части b и поместить его в верхнюю часть a. |
Ничего не делать, если b пусто. |
|
| pb (push b): Take the first element at the top of a and put it at the top of b. | |
| Do nothing if a is empty. | pb (push b): взять первый элемент в верхней части a и поместить его в верхнюю часть b. |
Ничего не делать, если a пусто. |
|
| ra (rotate a): Shift up all elements of stack a by 1. | |
| The first element becomes the last one. | ra (rotate a): сдвинуть вверх все элементы стека a на 1. |
| Первый элемент становится последним. | |
| rb (rotate b): Shift up all elements of stack b by 1. The first element becomes the last one. | rb (rotate b): сдвинуть вверх все элементы стека b на 1. Первый элемент становится последним. |
| rr : ra and rb at the same time. | rr : ra и rb одновременно. |
| rra (reverse rotate a): Shift down all elements of stack a by 1. | |
| The last element becomes the first one. | rra (обратное вращение a): сдвинуть вниз все элементы стека a на 1. |
| Последний элемент становится первым. | |
| rrb (reverse rotate b): Shift down all elements of stack b by 1. The last element becomes the first one. | rrb (обратное вращение b): сдвиг вниз всех элементов стека b на 1. Последний элемент становится первым. |
| rrr : rra and rrb at the same time. | ррр : рра и ррб одновременно. |
V.2 Example / Пример