Menu Introduction Bibliography

Basics Arrays Linked Lists Timing Estimates Summary

Sorting Insertion Sort Shell Sort Quick Sort Comparison External Sorts

Dictionaries Hash Tables Binary Trees Red-Black Trees Skip Lists Comparison

Summary

As we have seen, sorted arrays may be searched efficiently using a binary search. However, we must have a sorted array to start with. In the next section various ways to sort arrays will be examined. It turns out that this is computationally expensive, and considerable research has been done to make sorting algorithms as efficient as possible.

Linked lists improved the efficiency of insert and delete operations, but searches were sequential and time-consuming. Algorithms exist that do all three operations efficiently, and they will be the discussed in the section on dictionaries.