DS&A

Comparisons and Swaps

We have seen two search algorithms on lists — linear search and binary search. Both algorithms find the index of a given target value in a list. But they make different assumptions about the data in the list: linear search works on any list, whereas binary search only works if the list is in order.

But it’s not just that. There is another, more subtle assumption: that we could use the < and > operations to compare the list elements with the target. In contrast, linear search only needs the == operation.

Comparisons

Algorithms are composed out of simpler operations, so when we’re designing and implementing an algorithm we need to know what operations are available. The operations depend on what types are used:

• Linear search works on a list, with any element type.
• Binary search also works on a list, but the element type must support a comparison operation.

Integers can be compared numerically, and strings can be compared alphabetically. Other types might be compared in other ways, and a type might support more than one comparison operation — for example, objects representing users could be compared by ID number or by username.

Like other kinds of operations, a comparison operation has inputs and an output. The < operation takes two numbers as inputs, and the output is a Boolean; the > and == operations are similar. However, it’s often simpler to think of comparison as just one operation which tests whether the first input is less than, equal to, or greater than the second one.(1)

Use the model below to compare pairs of values:

Verify that the list is in order, and simulate the binary search algorithm.

Sorting

Sorting means putting things in order. To make this a computational problem, we should be more specific:

• Problem: given a list, put its elements in order in-place.
  • Input: a list, whose elements support a comparison operation.
  • Output: none.(2)
• Example: [1, 3, 2, 5, 4] becomes [1, 2, 3, 4, 5].
• Example: ["foo", "bar", "baz"] becomes ["bar", "baz", "foo"].

If all we want is to sort lists, then that’s easy — almost every programming language has a built-in way to sort a list. Here’s how to do it in Python:

>>> numbers = [1, 3, 2, 5, 4]
>>> numbers.sort()
>>> numbers
[1, 2, 3, 4, 5]
>>> words = ['foo', 'bar', 'baz']
>>> words.sort()
>>> words
['bar', 'baz', 'foo']

That is, Python’s lists have a sort method. However, we’re also interested in algorithms — how operations are implemented; how they actually work. That includes sorting.

Sorting is a very common problem, with many applications. It’s easy for humans, but it’s not obvious how a computer should do it. In fact, there are hundreds of different sorting algorithms and none is clearly the best.

In this post we’ll just consider in-place sorting; another common problem is to sort the elements into a new list, without modifying the original list. We’ll see some algorithms for both problems in later posts.

Swapping

An in-place sorting algorithm will need to permute the list elements. Lists don’t have a basic operation to “move” a value from one index to another; but we can rearrange elements using the get and set operations.(3)

It will be useful to swap list elements, like in the model below:

This model shows what we want to do, but in reality, swapping is not one of the basic operations supported by a list. Using the get and set operations, after we get a value, it is still there — and when we set at a different index, it overwrites the current value at that index. This is more like “copying” than “swapping”:

You should notice that it’s impossible to swap two values just by copying from one index to another — the old value at the new index is lost. However, by using a variable to temporarily keep a copy of the other value, we can achieve a swap with three copies.

Try putting the list in order now!

Footnotes

1. In fact, many programming languages do have comparison functions like this.
2. The list will be sorted in-place — no new list needs to be created and returned.
3. Alternatively, we could use the insert and remove operations, but those are less efficient on list data structures, especially array-lists.

• Tags: 
• sorting, algorithms, problems