Perhaps the most dramatic algorithmic improvement made possible by using appropriate data structures occurs in sorting. Selection sort is a simple-to-code algorithm that repeatedly extracts the smallest remaining element from the unsorted part of the set:

SelectionSort(

A)For

i= 1 tondo

Sort[i] = Find-Minimum fromADelete-Minimum from

AReturn(

Sort)

Selection sort is typically implemented by partitioning the input
array into sorted and unsorted regions.
To find the smallest item, we perform a linear sweep through the unsorted
portion of the array.
The smallest item is then swapped with the *i*th item in the array
before moving on the next iteration.
Selection sort performs *n* iterations, where the average iteration
takes *n*/2 steps, for a total of time.

But what if we improve the data structure?
It takes *O*(1) time to remove a particular item from an unsorted array
once it has been located,
but *O*(*n*) time to find the smallest item.
These two are exactly the operations supported by priority queues.
So what happens if we replace the
data structure with a better priority queue
implementation, either a heap or a balanced binary tree.
Operations within the loop now take time each, instead of *O*(*n*).
By using such a priority queue implementation,
selection sort is sped up to from .
The name typically given to this algorithm, *heapsort*,
obscures the relationship between them, but heapsort is nothing but
an implementation of selection sort with the right data structure.

Mon Jun 2 23:33:50 EDT 1997