next up previous contents index CD CD Algorithms
Next: Incremental Insertion Up: Approaches to Sorting Previous: Approaches to Sorting

Data Structures

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:  


For i = 1 to n do

Sort[i] = Find-Minimum from A

Delete-Minimum from A


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 ith 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 tex2html_wrap_inline24033 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 tex2html_wrap_inline24039 time each, instead of O(n). By using such a priority queue implementation, selection sort is sped up to tex2html_wrap_inline24043 from tex2html_wrap_inline24045 . 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