2 Arrays: searching and sorting

Arrays are one of the fundamental data structures in programming. This is because they are natively supported by the computer, and have good performance: reading or writing an element of the array takes very little time. Many important algorithms use arrays.

Note to Python programmers: in Python, arrays are called lists, and are written like this: [1,2,3]. There is one difference between arrays and Python lists: in most programming languages, any given array has a fixed size. However, Python lists can change in size – for example, the append method adds a new element to the list, increasing its size. In this chapter, we will work with arrays that have a fixed size. Python lists are so-called dynamic arrays.

In this chapter we will study two algorithmic problems and how to solve them efficiently using arrays:

Searching

Given a list of items, check if a given item is present in the list. There are two kinds of search problems:

Membership testing: The search algorithm is given an item to search for, and should return true or false depending on whether the item is found. For example, a spellchecker: given a list of all valid English words, search the list for a given string.

Lookup: The items are typically objects, and each object has a field called the key. The search algorithm is given a key, and should return the item having that key (or a reference to the item, such as the position in the list). For example, a database: given a list of people, find the person having a given personal identity number.

Sorting

Given a list of items, put them in ascending order. Again, there are two kinds of sorting problems:

Natural sorting: Here, the items have some kind of natural order. For example, sorting a list of words in alphabetical order.

Key-based sorting: Here, each item has a key, and we want to sort the items so that the keys come in ascending order. For example, sorting a list of towns by population.

Note that if we search or sort according to a key, it doesn’t have to be explicitly stored in the object, but can instead be calculated on demand. E.g., if we want to sort a list of words case-insensitively, we can use a lower-case transformation when doing the comparisons. This is usually done by a comparator (in Java), or by a key function (in Python).

This chapter concentrates on membership testing and natural sorting, but all the algorithms in this chapter work just as well for lookup and key-based sorting.