For heapsort, use the usual array representation of a max-heap, indexed from zero, with children . Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are
start                    [2,7,3,2,8,1]
sift at index 2          [2,7,3,2,8,1]
sift at index 1          [2,8,3,2,7,1]
sift at index 0          [8,7,3,2,2,1]
At index zero, the value 2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.
Removed maximumAfter root exchangeAfter restoring heap order
1,7,3,2,2 | 87,2,3,1,2 | 8
2,2,3,1 | 7,83,2,2,1 | 7,8
1,2,2 | 3,7,82,1,2 | 3,7,8
2,1 | 2,3,7,82,1 | 2,3,7,8
1 | 2,2,3,7,81 | 2,2,3,7,8
The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.
For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate 2 is handled:
pivot 2:  [1]       | 2 | [7,3,2,8]
pivot 7:  [3,2]     | 7 | [8]
pivot 3:  [2]       | 3 | []
Empty and singleton lists are already sorted. Returning from the recursive calls gives
Q [3,2]       = [2] ++ [3] ++ []       = [2,3]
Q [7,3,2,8]   = [2,3] ++ [7] ++ [8]   = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]
For counting sort, count keys through . After reading each input key, the count vector is
initial: (0,0,0,0,0,0,0,0)
read 2:  (0,1,0,0,0,0,0,0)
read 7:  (0,1,0,0,0,0,1,0)
read 3:  (0,1,1,0,0,0,1,0)
read 2:  (0,2,1,0,0,0,1,0)
read 8:  (0,2,1,0,0,0,1,1)
read 1:  (1,2,1,0,0,0,1,1)
The cumulative counts are . For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key at position , and decrement . The successive placements are 1 at , 8 at , the later 2 at , 3 at , 7 at , and the earlier 2 at . The final answer for all three sorting algorithms is
(1)

Ancestors (11)

  1. 5
  2. Functional programming, data structures and algorithms, procedural programming, and digital hardware
  3. 2005
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version