PROJECT DOSSIER // [PUSH SWAP]VIEW SOURCEBACK TO PROJECTS →

01 // PROJECT AT A GLANCE

PUSH SWAP

C

Sorting a list with only two stacks and a handful of allowed operations.

The problem is sorting numbers, but under very restrictive rules: you only have two stacks and a few elementary moves, a bit like a game of patience. The goal is not only to get there, but to get there in as few moves as possible — which turns a sorting exercise into a genuine optimisation problem.

A push_swap binary sorting a list of integers through two stacks and a restricted operation set, using a decimal radix sort that emits the instructions as it goes.

PRIMARYC
DELIVERYTEAM RECORD
VERIFICATIONmake
SOURCEINSPECTOR READY
MEDIA ATTACHMENTS (Images, Photos, Videos)

02 // PROJECT SIGNALS

DATE:
2018
PRIMARY LANG:
C
GRADE:
A
DURATION:
2 weeks
SECONDARY:
—
STACK:
Makefile / gcc

03 // KEY OUTCOMES

  • A radix sort adapted to an operation set that allows neither direct access nor arbitrary comparison
  • Two circular doubly linked lists to make rotation and transfer constant time
  • Instructions emitted as they go, with no intermediate list in memory

BEYOND THE BRIEF

  • Radix sort (radix.c) over the binary representation of the values, instead of a naive insertion sort
  • A reduced bubble sort kept for very small lists, where radix does not pay off

04 // SOURCE TREE

READING SOURCE…