Skip to content

Home

Jump to bottom
Teresa Chow edited this page Jan 6, 2025 · 18 revisions

Push_swap notes

42 School: Rank 2

This document contains my notes on 42 Common Core curriculum project "push_swap".

Table of contents

Subject instructions · References & further reading

Subject instructions

Mandatory

This project is about sorting data on a stack, with a limited set of instructions, using the lowest possible number of actions. Its goal is reaching an optimized data sorting solution.

General

  • Basic rules
Program name push_swap
Turn in files Makefile, *.h, *.c
Makefile NAME, all, clean, fclean, re
Arguments stack a: a list of integers
  • External functions allowed
Function name Header file Notes / Description
read

sys/types.h

sys/uio.h

unistd.h

 ssize_t read(int fildes, void *buf, size_t nbyte);
write unistd.h
malloc stdlib.h
free stdlib.h
exit
All functions of the MiniLibX mlx.h
ft_printf libft/ft_printf/ft_printf.h and/or any equivalent coded by ourselves
All functions of the libft library libft/libft/libft.h coded by ourselves (1st project of 42's Common Core curriculum)

Rules

There are 2 stacks named a and b.

At the beginning:

  • stack a contains a random amount of negative and/or positive integers, which cannot be duplicated.
  • stack b is empty.

The goal is to sort numbers in ascending order into stack a using the following operations:

Swap

sa (swap a) – swap the first 2 elements at the top of stack a.

sb (swap b)– swap the first 2 elements at the top of stack b.

ss (swap both) – sa and sb at the same time.

Push

pa (push a) – take the first element at the top of stack b and put it at the top of stack a.

pb (push b) – take the first element at the top of stack a and put it at the top of stack b.

Rotate

ra (rotate a) – shift up all elements of stack a by 1: the first element becomes the last one.

rb (rotate b) – shift up all elements of stack b by 1: the first element becomes the last one.

rr (rotate both) – ra and rb at the same time.

Reverse rotate

rra (reverse rotate a) – shift down all elements of stack a by 1: the last element becomes the first one.

rrb (reverse rotate b) – shift down all elements of stack b by 1: the last element becomes the first one.

rrr (reverse rotate both) : rra and rrb at the same time.

Benchmark

  • sort 100 random numbers in fewer than 700 operations (minimum validation standard)

  • sort 500 random numbers in fewer than 5500 operations (maximum validation standard)

References & further reading

Stack datatype

Sorting algorithm

Analysis of algorithms
Sorting algorithm

Approaches to the subject I found interesting to explore

Other useful links

Clone this wiki locally