Overview The cost analysis system is the heart of the Push Swap algorithm’s efficiency. It calculates the exact number of operations needed to move each element to its target position, enabling the algorithm to always choose the optimal move.
Node Initialization Process Before calculating costs, nodes must be properly initialized with position and target information.
init_nodes_a() Location: init_a_to_b.c:104-111void init_nodes_a (t_list * a , t_list * b ) { current_index (a); current_index (b); set_target_a (a, b); cost_analysis_a (a, b); set_cheapest (a); }
This function is called before moving elements from Stack A to Stack B. It performs five critical steps:
Update indices for Stack A - Recalculate positions after any changesUpdate indices for Stack B - Ensure B’s positions are currentSet target nodes - Find where each A node should go in BCalculate costs - Compute operation count for each moveMark cheapest - Flag the most efficient node to move
init_nodes_b() Location: init_b_to_a.c:43-48void init_nodes_b (t_list * a , t_list * b ) { current_index (a); current_index (b); set_target_b (a, b); }
Simpler version used when moving elements back from Stack B to Stack A. Cost analysis is not needed here because elements are moved in order from the top of B.
Position Indexing current_index() Location: init_a_to_b.c:15-34void current_index (t_list * stack ) { int i; int median; i = 0 ; if ( ! stack) return ; median = stack_len (stack) / 2 ; while (stack) { stack -> index = i; if (i <= median) stack -> above_median = true ; else stack -> above_median = false ; stack = stack -> next ; i ++ ; } }
Purpose: Assigns position indices and median flags to all nodes.Key Points:
Index 0 = top of stack
Median = stack_len / 2
Nodes at index ≤ median are marked above_median = true
Nodes at index > median are marked above_median = false
Why it matters: The above_median flag determines rotation direction:
Above median → use forward rotation (ra/rb) - shorter path
Below median → use reverse rotation (rra/rrb) - shorter path
Example For a stack with 7 elements:
Index: 0 1 2 3 4 5 6 Values: [5] [2] [9] [1] [7] [3] [8] Median: 7/2 = 3 above_median: true true true true false false false
Elements at indices 0-3: Use ra (4 rotations max)
Elements at indices 4-6: Use rra (3 rotations max)
Target Node Selection set_target_a() - A to B Location: init_a_to_b.c:36-62static void set_target_a (t_list * a , t_list * b ) { t_list * current_b; t_list * target_node; long best_match_index; while (a) { best_match_index = LONG_MIN; current_b = b; while (current_b) { if ( current_b -> nbr < a -> nbr && current_b -> nbr > best_match_index) { best_match_index = current_b -> nbr ; target_node = current_b; } current_b = current_b -> next ; } if (best_match_index == LONG_MIN) a -> target_node = find_max (b); else a -> target_node = target_node; a = a -> next ; } }
Strategy: Find the largest value in B that is smaller than the current A node .Algorithm:
Initialize best_match_index to LONG_MIN
Scan all nodes in Stack B
For each B node that is smaller than the A node:
If it’s larger than best_match_index, update the target
If no smaller value exists, target becomes find_max(b) (wrap around)
Example: Stack A: [7] [3] [9] Stack B: [5] [1] [8] For node 7 in A: - B values: 5 (< 7), 1 (< 7), 8 (> 7) - Best match: 5 (largest value < 7) - Target: node with value 5 For node 3 in A: - B values: 5 (> 3), 1 (< 3), 8 (> 3) - Best match: 1 (only value < 3) - Target: node with value 1 For node 9 in A: - B values: 5 (< 9), 1 (< 9), 8 (< 9) - Best match: 8 (largest value < 9) - Target: node with value 8
set_target_b() - B to A Location: init_b_to_a.c:15-41static void set_target_b (t_list * a , t_list * b ) { t_list * current_a; t_list * target_node; long best_match_index; while (b) { best_match_index = LONG_MAX; current_a = a; while (current_a) { if ( current_a -> nbr > b -> nbr && current_a -> nbr < best_match_index) { best_match_index = current_a -> nbr ; target_node = current_a; } current_a = current_a -> next ; } if (best_match_index == LONG_MAX) b -> target_node = find_min (a); else b -> target_node = target_node; b = b -> next ; } }
Strategy: Find the smallest value in A that is larger than the current B node .Algorithm: Mirror of set_target_a() with reversed logic:
Initialize best_match_index to LONG_MAX
Scan all nodes in Stack A
For each A node that is larger than the B node:
If it’s smaller than best_match_index, update the target
If no larger value exists, target becomes find_min(a) (wrap around)
Cost Calculation cost_analysis_a() Location: init_a_to_b.c:64-82static void cost_analysis_a (t_list * a , t_list * b ) { int len_a; int len_b; len_a = stack_len (a); len_b = stack_len (b); while (a) { a -> push_cost = a -> index ; if ( ! ( a -> above_median )) a -> push_cost = len_a - ( a -> index ); if ( a -> target_node -> above_median ) a -> push_cost += a -> target_node -> index ; else a -> push_cost += len_b - ( a -> target_node -> index ); a = a -> next ; } }
Purpose: Calculate the total number of operations needed to move each node from Stack A to its target position in Stack B.Component 1: Cost to Reach Node in A a -> push_cost = a -> index; if ( ! (a -> above_median)) a -> push_cost = len_a - (a -> index);
If above median:
Use forward rotation: ra
Cost = index (distance from top)
Example: Index 2 requires 2 ra operations
If below median:
Use reverse rotation: rra
Cost = stack_length - index
Example: Index 5 in stack of 7 requires 7-5=2 rra operations
Component 2: Cost to Reach Target in B if (a -> target_node -> above_median) a -> push_cost += a -> target_node -> index; else a -> push_cost += len_b - (a -> target_node -> index);
Same logic applied to the target node’s position in Stack B.
Total Cost total_cost = cost_to_reach_node_in_A + cost_to_reach_target_in_B + 1
(The +1 is implicit for the final pb operation)
Cost Calculation Example Scenario: Stack A (len=7): [5] [2] [9] [1] [7] [3] [8] 0 1 2 3 4 5 6 Median A: 3 Stack B (len=5): [4] [6] [10] [0] [11] 0 1 2 3 4 Median B: 2
Calculate cost for node with value 7 (index 4 in A):
Cost in A:
Index: 4
Above median? No (4 > 3)
Cost: 7 - 4 = 3 operations (rra)
Find target in B:
Looking for largest value < 7
Options: 4, 6, 0 (10 and 11 are > 7)
Best match: 6 (at index 1)
Cost in B:
Target index: 1
Above median? Yes (1 ≤ 2)
Cost: 1 operation (rb)
Total cost:
A cost: 3
B cost: 1
Total: 4 operations
Actual operations needed: rra (position 7 at top of A) rra rra rb (position 6 at top of B) pb (push 7 to B)
Total: 5 operations (4 rotations + 1 push)
Finding the Cheapest Node set_cheapest() Location: init_a_to_b.c:84-102void set_cheapest (t_list * stack ) { long cheapest_value; t_list * cheapest_node; if ( ! stack) return ; cheapest_value = LONG_MAX; while (stack) { if ( stack -> push_cost < cheapest_value) { cheapest_value = stack -> push_cost ; cheapest_node = stack; } stack = stack -> next ; } cheapest_node -> cheapest = true ; }
Purpose: Find and mark the node with the lowest push_cost.Process:
Initialize cheapest_value to LONG_MAX
Traverse the entire stack
Track the node with minimum push_cost
Set cheapest = true for that node
Important: Only ONE node is marked as cheapest at any given time.get_cheapest() Location: stack_utils.c:30-41t_list * get_cheapest (t_list * stack ) { if ( ! stack) return ( NULL ); while (stack) { if ( stack -> cheapest ) return (stack); stack = stack -> next ; } return ( NULL ); }
Purpose: Retrieve the node marked as cheapest.Returns: Pointer to the node with cheapest = true, or NULL if none found.Optimization: Simultaneous Rotations The cost calculation doesn’t account for one major optimization: simultaneous rotations .
When Both Stacks Rotate Together If both the node and its target are:
Both above median → use rr (rotate both)
Both below median → use rrr (reverse rotate both)
This is handled in move_a_to_b() (sort_big_stacks.c:37-51):
if (cheapest_node -> above_median && cheapest_node -> target_node -> above_median) rotate_both (a, b, cheapest_node); else if ( ! (cheapest_node -> above_median) && ! (cheapest_node -> target_node -> above_median)) rev_rotate_both (a, b, cheapest_node);
Benefit: Instead of 4 rotations in A + 2 rotations in B = 6 operations, we get 2 simultaneous rotations + 2 more in A = 4 operations total.Why Not Include This in Cost Calculation? Answer: Simplicity and consistency. The cost calculation provides a comparable metric across all nodes. The actual optimization is applied during execution, which doesn’t change the relative ranking of which node is cheapest.Complete Cost Analysis Flow
current_index(): O(n) - traverses stack onceset_target_a(): O(n × m) - for each A node, scan all B nodescost_analysis_a(): O(n) - traverses A stack onceset_cheapest(): O(n) - traverses A stack once Total per iteration: O(n × m) where n = size of A, m = size of B
O(1) - All calculations are done in-place on existing node structures. No additional data structures are allocated.
The cost analysis provides an exact count of operations needed, not an approximation. This guarantees that the algorithm always chooses the truly optimal move at each step.
The cost analysis is recalculated before every single move from A to B. This ensures that costs stay accurate as stack compositions change, leading to consistently optimal decisions throughout the sorting process.
