Chapter 4. Sorting Algorithms

Sorting from the LLP perspective: every comparison-based sort solves a forbidden-index problem on the inversion-vector lattice.

This page: LLP forms. View classical forms »

LLP-Sort-Adjacent: forbidden = inversion

LLP-Sort-Adjacent keeps the array $A$ itself as its state vector: index $j$ is forbidden when $A[j] > A[j+1]$ (an inversion at the seam $(j, j+1)$), and the advance rule swaps $A[j]$ and $A[j+1]$. Once no index remains forbidden, $A$ is sorted.

Time complexity: $O(n^2)$, where $n$ is the size of the array.

LLP-Sort-Pairwise

A more eager LLP form: $j$ is forbidden when some $k > j$ exists with $A[j] > A[k]$. The advance picks such a $k$ and swaps. Reaches the same sorted array as LLP-Sort-Adjacent but with a different schedule.

Time complexity: $O(n^2)$, where $n$ is the size of the array.

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.