-
Notifications
You must be signed in to change notification settings - Fork 41
Pseudocode Format
Luke Ceddia edited this page Nov 2, 2020
·
8 revisions
\\Code{
main
// Sort array A[left]..A[right] in ascending order
Quicksort(A, left, right)
\\Expl{ We need left and right indices because the code is recursive
and both may be different for recursive calls.
\\Expl}
if left < right
\\Expl{ Terminating condition (if there are less than two
elements in the array segment do nothing).
\\Expl}
\\In{
Choose pivot \\Ref ChoosePivot
\\Expl{ There are various ways to choose the "pivot", which is
used to distinguish (relatively) small elements and
(relatively) large elements in the partitioning process.
\\Expl}
Partition array segment \\Ref Partition
\\Expl{ This is where most of the work of Quicksort gets done.
We start with an unordered array segment and finish
with an array segment containing the pivot in its final
place, A[i], and two partitions, one containing only
elements smaller than or equal to the pivot, and the other
containing only elements larger than or equal to the pivot.
There are various ways this can be coded, often with
some subtle points.
\\Expl}
Quicksort FirstHalf \\Ref QuicksortFirstHalf
\\Expl{ Sort elements left of (smaller or equal to) the pivot,
which is in A[i].
\\Expl}
Quicksort SecondHalf \\Ref QuicksortSecondHalf
\\Expl{ Sort elements right of (greater or equal to) the pivot,
which is in A[i].
\\Expl}
\\In}
\\Code}
\\Code{
QuicksortFirstHalf
Quicksort(A, left, i - 1)
\\Code}
\\Code{
QuicksortSecondHalf
Quicksort(A, i + 1, right)
\\Code}
\\Code{
ChoosePivot
Put the left, right and middle elements in increasing order \\Ref SortLMR
\\Expl{ This method of choosing a pivot uses the median of the left,
right and middle elements of the array segment. Sorting the left,
middle and right elements ensure the median is in the middle
plus A[left] and A[right] are in their correct partitions, so
they can be skipped in the rest of the partitioning.
\\Expl}
Swap(A[mid], A[right-1]) // put median in A[right-1]
pivot <- A[right-1]
\\Expl{ Using the median of the left, right and middle elements for the
pivot leads to very good performance for sorted and reverses sorted
inputs and the theoretical worse case is rarely encountered.
\\Expl}
\\Code}
\\Code{
SortLMR
mid <- (left+right)/2 // index of middle element
if A[left] > A[mid]
\\In{
Swap(A[left], A[mid])
\\In}
if A[mid] > A[right]
\\In{
Swap(A[right], A[mid])
if A[left] > A[mid]
\\In{
Swap(A[left], A[mid])
\\In}
// now A[left] <= A[mid] <= A[right]
\\In}
\\Code}
\\Code{
Partition
Set index i at left the of array segment and j at the right \\Ref init_iAndj
\\Expl{ i scans from left to right stopping at large elements and
j scans from right to left stopping at small elements.
\\Expl}
while i < j
\\Expl{ When the indices cross, all the large elements at the left of
the array segment have been swapped with small elements from the
right of the array segment. The coding here can be simplified
if we use "break" or similar to exit from this loop.
\\Expl}
\\In{
Repeatedly increment i until A[i] >= pivot
\\Expl{ Stopping at elements equal to the pivot results in better
performance when there are many equal elements and because
the pivot is in A[right] this also acts as a sentinel so we
dont increment beyond the right of the array segment.
\\Expl}
Repeatedly decrement j until A[j] <= pivot or j < i
\\Expl{ Stopping at elements equal to the pivot results in better
performance when there are many equal elements. If the
indices cross we exit the outer loop; this also stops us
decrementing beyond the left of the array segment.
\\Expl}
if j > i
\\Expl{ If the indices cross, we exit the loop.
\\Expl}
\\In{
swap(A[i], A[j])
\\Expl{ Swap the larger element (A[i]) with the smaller
element (A[j]).
\\Expl}
\\In}
\\In}
Put the pivot in its final place \\Ref SwapP
\\Code}
\\Code{
init_iAndj
i <- left
\\Expl{ i is incremented before use, so A[left+1] is the first
element in the left to right scan (A[left] <= pivot already).
\\Expl}
j <- right - 1
\\Expl{ j is decremented before use, so A[right-2] is the first
element in the right to left scan (A[right-1] is the pivot).
\\Expl}
\\Code}
\\Code{
SwapP
swap(A[i], A[right])
\\Expl{ The pivot element, in A[right], is swapped with A[i]. All
elements to the left of A[i] must be less then or equal to
the pivot and A[i] plus all elements to its right must be
greater than or equal to the pivot.
\\Expl}
\\Code}
\\Code{
Main
HeapSort(A, n) // Sort array A[1]..A[n] in ascending order.
\\Expl{ We are not using A[0] (for languages that start array indices at 0).
\\Expl}
\\In{
BuildHeap(A, n) \\Ref BuildHeap
\\Expl{ First reorder the array elements so they form a (max) heap
(no element is larger than its parent). The root node, A[1],
is therefore the largest element.
\\Expl}
SortHeap(A, n) \Ref SortHeap
\\Expl{ Convert the heap into a sorted array. The largest element is
put in the correct position A[n] first and we work backward
from there, putting the next-largest element in its place,
etc, shrinking the heap by one element at each step.
\\Expl}
\\In}
\\Code}
\\Code{
BuildHeap
// build heap
for k <- Index of last non-leaf downto 1 \\Ref BHForLoop
\\Expl{ We use bottom-up heap creation, to build the heap from the bottom
up (tree view) and right to left (array view). The leaves are
already heaps of size 1, so nothing needs to be done with them.
Working backward through the heap, and starting from the last
non-leaf node, we form heaps of up to size 3 (from 2 leaves plus
their parent k), then 7 (2 heaps of size 3 and their parent k)
etc, until the whole array is a single heap.
\\Expl}
\\In{
DownHeap(A, k, n) \\Ref DownHeapk
\\Expl{ DownHeap is where smaller heaps are combined to form larger
heaps. The children of node k are already heaps, so we need
only be concerned about where A[k] fits in.
\\Expl}
\\In}
\\Code}
\\Code{
BHForLoop
for k <- n/2 downto 1
\\Expl{ Using root index 1, the last non-leaf has index n/2 (rounded down
to the nearest integer).
\\Expl}
\\Code}
\\Code{
DownHeapk
// DownHeap(A, k, n)
\\Expl{ DownHeap is where smaller heaps are combined to form larger heaps.
The children of node k are already heaps, so we need only be
concerned about where A[k] fits in.
\\Expl}
i <- k
\\Expl{ Set index i to the root of the subtree that we are now going to
make into a heap.
\\Expl}
heap <- False // 'heap' is a flag
while not (IsLeaf(A[i]) or heap)
\\Expl{ Traverse down the heap until the current node A[i] is a leaf.
We also terminate the loop if the children of A[i] are in the
correct order relative to the parent, since we know that subtrees
lower down already meet the heap condition. We use the heap flag
to test the heap condition.
\\Expl}
\\In{
j <- IndexOfLargestChild(A, i, n) \\Ref IndexOfLargestk
\\Expl{ Find the larger of the two children of the node.
\\Expl}
if A[i] >= A[j]
\\In{
heap <- True
\\Expl{ The heap condition is satisfied (the root is larger
than both children), so exit from while loop.
\\Expl}
\\In}
else
\\In{
Swap(A[i], A[j]) // Swap root element with (larger) child
i <- j
\\In}
\\In}
\\Code}
\\Code{
IndexOfLargestk
if 2*i < n and A[2*i] < A[2*i+1]
\\Expl{ The left child of A[i] is A[2*i] and the right child (if there is
a right child) is A[2*i+1]; set j to the index of the larger child.
\\Expl}
\\In{
j <- 2*i+1
\\In}
else
\\In{
j <- 2*i
\\In}
\\Code}
\\Code{
SortHeap
// Sort heap
while n > 1
\\Expl{ A[1] always has the largest value not yet processed in the
sorting phase. A[n] is the last array element in the heap-ordered
array that is not yet sorted. Repeatedly swap these two values,
so that the largest element is now in the last place, decrement n
and re-establish the heap condition for the remaining heap (which
now has one less element). Repeat this procedure until n=1, that
is, only one node remains.
\\Expl}
\\In{
Swap(A[n], A[1])
n <- n-1
DownHeap(A, 1, n) \\Ref DownHeap1
\\Expl{ Now that the root node has been swapped to the end, A[1] may
no longer be the largest element in the (reduced size) heap.
Use the DownHeap operation to restore the heap condition.
\\Expl}
\\In}
\\Note{ This is very similar to DownHeapk.
\\Note}
\\Code
DownHeap1
// DownHeap(A, 1, n)
i <- 1
\\Expl{ Set index i to the root of the subtree that we are now going to
examine.
\\Expl}
heap <- False // 'heap' is a flag
while not (IsLeaf(A[i]) or heap) do
\\Expl{ Traverse down the heap until the current node A[i] is a leaf.
We also terminate the loop if the children of A[i] are in the
correct order relative to the parent, since we know that subtrees
lower down already meet the heap condition. We use the heap flag
to test the heap condition.
\\Expl}
\\In{
j <- IndexOfLargestChild(A, i, n) \\Ref IndexOfLargest0
\\Expl{ Find the larger of the two children of the node.
\\Expl}
if A[i] >= A[j] // Parent is larger than the largest child
\\In{
heap <- True
\\Expl{ The heap condition is satisfied, that is, the root is
larger than both children, so we exit from the while loop.
\\Expl}
\\In}
else
\\In{
Swap(A[i], A[j]) // Swap root element with (larger) child
i <- j
\\In}
\\In}
\\Code}
\\Code{
Main
BST_Build(keys) // return the BST that results from inserting nodes
// with keys 'keys', in the given order, into an
// initially empty BST
t <- Empty
for each k in keys
\\In{
t <- BST_Insert(t, k) \\Ref Insert
\\In}
\\Code}
\\Code{
Insert
BST_Insert(t, k) // Insert key k in BST t, maintaining the BST invariant
\\In{
n <- new Node // create a new node to hold key k
n.key <- k
n.left <- Empty // it will be a leaf, that is,
n.right <- Empty // it has empty subtrees
if t = Empty
\\In{
return n // in this case, the result is a tree with just one node
\\Expl{ If the tree is initially empty, the resulting BST is just
the new node, which has key k, and empty sub-trees.
\\Expl}
\\In}
Locate the node p that should be the parent of the new node n. \\Ref Locate
if k < p.key
\\Expl{ The new node n (whose key is k) will be a child of p. We just
need to decide whether it should be a left or a right child of p.
\\Expl}
\\In{
p.left <- n // insert n as p's left child
\\In}
else
\\In{
p.right <- n // insert n as p's right child
\\In}
return t
\\In}
\\Code}
\\Code{
Locate
c <- t // c traverses the path from the root to the insertion point
\\Expl{ c is going to follow a path down to where the new node is to
be inserted. We start from the root (t).
\\Expl}
repeat
\\In{
p <- c // when the loop exits, p will be c's parent
\\Expl{ Parent p and child c will move in lockstep, with p always
trailing one step behind c.
\\Expl}
if k < c.key
\\Expl{ The BST condition is that nodes with keys less than the current
node's key are to be found in the left subtree, and nodes whose
keys are greater (or the same) are to be in the right subtree.
\\Expl}
\\In{
c <- c.left
\\In}
else
\\In{
c <- c.right
\\In}
\\In}
until c = Empty
\\Expl{ At the end of this loop, c has located the empty subtree where new
node n should be located, and p will be the parent of the new node.
\\Expl}
\\Code}
By AIA Organization