hero-image

Push_swap

Push_swap

Push_swap is a highly efficient C project focused on sorting data on a stack, with a limited set of instructions, using the lowest possible number of actions. It requires manipulating various types of algorithms and choosing the most appropriate solution for an optimized data sorting.

Project Requirements

  • Goal: Sort stack a in ascending order using stack b as a helper.
  • Operations: sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr.
  • Error Handling: Must handle non-numeric parameters, duplicates, and integer overflows/underflows (INT_MIN/MAX).
  • Performance: Optimized to sort 100 numbers in fewer than 700 moves and 500 numbers in fewer than 5500 moves (standard 42 benchmarks).
  • Memory: No memory leaks; all stack nodes must be freed upon exit.

The Algorithm Strategy

My implementation uses a hybrid approach to ensure maximum efficiency depending on the stack size:

1. Coordinate Compression (Indexing)

Before sorting, the program replaces each number with its relative rank (0 to N-1). This “Indexing” step allows the sorting algorithm to handle negative numbers and very large values identically.

void	indexing(t_node **stack)
{
	t_node	*curr_node;
	int		index;

	index = 0;
	curr_node = get_min(stack);
	while (curr_node)
	{
		curr_node->index = index++;
		curr_node = get_min(stack);
	}
}

2. Small Sets: Hard Sort

For stacks of 5 numbers or fewer, I implemented a “Hard Sort” which uses specific, hardcoded logic to find the optimal move sequence for every possible permutation.

3. Large Sets: Bitwise Radix Sort

For larger datasets, I implemented a Radix Sort algorithm. By looking at the binary representation of the indices, the algorithm pushes numbers to stack b based on whether a specific bit is 0 or 1, then pushes them back to a. This results in a very predictable and efficient O(n * log(n)) complexity.

void	radin_sort(t_node **stack_a, t_node **stack_b)
{
	int	i;
	int	j;
	int	size;
	int	max_bit;

	size = stack_size(*stack_a);
	max_bit = max_bits(stack_a);
	i = 0;
	while (i < max_bit)
	{
		j = 0;
		while (j++ < size)
		{
			if ((((*stack_a)->index >> i) & 1) == 1)
				ra(stack_a);
			else
				pb(stack_a, stack_b);
		}
		while (stack_size(*stack_b) != 0)
			pa(stack_a, stack_b);
		i++;
	}
}

Error Handling & Parsing

The parser ensures that every input is a valid integer. It checks for:

  • Duplicates: No two numbers can be the same.
  • Overflows: Numbers must fit within a 32-bit int.
  • Invalid Characters: Only digits and signs (+/-) are permitted.
static int	valid_arg(char *str)
{
	int	i;

	i = 0;
	if (str[i] == '-' || str[i] == '+')
		i++;
	if (!str[i])
		return (0);
	while (str[i])
	{
		if (str[i] < '0' || str[i] > '9')
			return (0);
		i++;
	}
	return (1);
}

Usage

1. Build

make

2. Run

./push_swap 2 1 3 6 5 8

3. Visualizer (Optional)

To see the algorithm in action, you can pipe the output to a visualizer:

ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker_linux $ARG

Skills Learned

  • Algorithm Complexity: Analyzing time (O) and space complexity.
  • Data Structures: Implementing and manipulating doubly linked lists.
  • Bitwise Logic: Using bit-shifting and masking for advanced sorting.
  • Testing: Unit testing against thousands of random permutations to ensure stability.

Author

arri