7.1 Introduction

Entire books have been written on sorting and searching with computers. We introduce the topic here only to stress, once again, that writing programs is not the target of computer science; solving problems efficiently and effectively with the limited resources found in a computer is the real goal.

It turns out that computers spend a tremendous amount of time sorting. Just as we discussed different algorithms for computing prime numbers, we will now discuss three basic, comparison-based sorting algorithms. None of these are truly efficient. Efficient comparison-based sorting is beyond the scope of this introductory text. Additionally, we introduce a radix sort, one that capitalizes on the nature of the elements stored, rather than individual comparison between elements.

The sorting problem is described as follows:

Given a list of elements provided as input in any arbitrary order, these elements having an established ordinal value, namely a collating sequence, reorder them so that they appear according to their ordinal value from lowest to highest.

For example, consider the following list of numbers as input: 5, 3, 7, 5, 2, 9. A sorted output corresponding to this input is: 2, 3, 5, 5, 7, 9.

In the following subsections, we will describe three comparison-based sorting algorithms and briefly compare them to demonstrate how to determine which one is the best. The implementation of each sorting algorithm will be presented in the context of grades for a final exam in a programming class. We want to provide a sorted list of the final scores, shown as percentages, to the students given an unsorted list. In each case, we describe the algorithm in plain language and then provide a corresponding Ruby implementation. Once the algorithms are presented, we discuss how we measure the notion of “best.”

     1 # Code for selection sort
     2 # 35 students in our class
     3 NUM_STUDENTS = 35
     4 # Max grade of 100%
     5 MAX_GRADE = 100
     6 num_compare = 0 
     7 arr = Array.new(NUM_STUDENTS)
     8 
     9 # Randomly populate arr
    10 for i in (0..NUM_STUDENTS - 1)
    11   # Maximum possible grade is 100%, keep in mind that rand(5) returns 
           possible values 0-4, so 
           we must add 1 to MAX_GRADE
    12   arr[i] = rand(MAX_GRADE + 1)
    13 end
    14 
    15 # Output current values of arr
    16 puts "Input list:"
    17 for i in (0..NUM_STUDENTS - 1)
    18   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    19 end
    20 
    21 # Now let's use a selection sort. We first find the lowest number in the 
    22 # array and then we move it to the beginning of the list
    23 for i in (0..NUM_STUDENTS - 2)
    24   min_pos = i
    25   for j in (i + 1)..(NUM_STUDENTS - 1)
    26     num_compare = num_compare + 1
    27     if (arr[j] < arr[min_pos])
    28       min_pos = j
    29     end
    30   end
    31   # Knowing the min, swap with current first element (at position i)
    32   temp = arr[i]
    33   arr[i] = arr[min_pos]
    34   arr[min_pos] = temp
    35 end
    36 
    37 # Now output the sorted array
    38 puts "Sorted list:"
    39 for i in (0..NUM_STUDENTS - 1)
    40   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    41 end
    42 
    43 puts "Number of Comparisons ==> " + num_compare.to_s  

     1 # Code for insertion sort
     2 # Declare useful constants
     3 NUM_STUDENTS = 35
     4 MAX_GRADE = 100
     5 num_compare = 0 
     6 arr = Array.new(NUM_STUDENTS)
     7 
     8 # Randomly populate arr
     9 
    10 for i in (0..NUM_STUDENTS - 1)
    11   arr[i] = rand(MAX_GRADE + 1)
    12 end
    13 
    14 # Output randomly generated array
    15 puts "Input array:"
    16 for i in (0..NUM_STUDENTS - 1)
    17   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    18 end
    19 
    20 # Now let's use an insertion sort
    21 # Insert lowest number in the array at the right place in the array
    22 for i in (0..NUM_STUDENTS - 1)
    23   # Now start at current bottom and move toward arr[i]
    24   j = i
    25   done = false
    26   while ((j > 0) and (! done))
    27     num_compare = num_compare + 1
    28     # If the bottom value is lower than values above it, swap it until it
    29     # lands in a place where it is not lower than the next item above it
    30     if (arr[j] < arr[j - 1]) 
    31       temp = arr[j - 1]
    32       arr[j - 1] = arr[j]
    33       arr[j] = temp
    34     else
    35       done = true
    36     end
    37     j = j - 1
    38   end 
    39 end
    40 
    41 # Now output the sorted array
    42 puts "Sorted array:"
    43 for i in (0..NUM_STUDENTS - 1)
    44   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    45 end
    46 puts "Number of Comparisons ==> " + num_compare.to_s

     1 # Code for bubble sort
     2 NUM_STUDENTS = 35
     3 # Max grade of 100%
     4 MAX_GRADE = 100
     5 num_compare = 0 
     6 arr = Array.new(NUM_STUDENTS)
     7 
     8 # Randomly put some final exam grades into arr
     9 
    10 for i in (0..NUM_STUDENTS - 1)
    11   arr[i] = rand(MAX_GRADE + 1)
    12 end
    13 
    14 # Output randomly generated array
    15 puts "Input array:"
    16 for i in (0..NUM_STUDENTS - 1)
    17   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    18 end
    19 
    20 # Now let's use bubble sort. Swap pairs iteratively as we loop through the 
    21 # array from the beginning of the array to the second-to-last value
    22 for i in (0..NUM_STUDENTS - 2)
    23   # From arr[i + 1] to the end of the array
    24   for j in ((i + 1)..NUM_STUDENTS - 1)
    25     num_compare = num_compare + 1
    26     # If the first value is greater than the second value, swap them
    27     if (arr[i] > arr[j])
    28       temp = arr[j]
    29       arr[j] = arr[i]
    30       arr[i] = temp
    31     end
    32   end
    33 end
    34 
    35 # Now output the sorted array
    36 puts "Sorted array:"
    37 for i in (0..NUM_STUDENTS - 1)
    38   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    39 end
    40 puts "Number of Comparisons ==> " + num_compare.to_s

     1 # Code for radix sort
     2 NUM_STUDENTS = 35
     3 MAX_GRADE = 100
     4 arr = Array.new(NUM_STUDENTS)
     5 
     6 # Randomly put some grades into the array *as strings*
     7 for i in (0..NUM_STUDENTS - 1)
     8   arr[i] = rand(MAX_GRADE + 1).to_s
     9 end
    10 
    11 # Output array and find the maximum number of digits in the generated array
    12 puts "Input array: "
    13 max_length = 0
    14 for i in (0..NUM_STUDENTS - 1)
    15   puts "arr[" + i.to_s + "] ==> " + arr[i]
    16   if arr[i].length > max_length
    17     max_length = arr[i].length
    18   end
    19 end
    20 puts "Max length ==> " + max_length.to_s
    21 
    22 # Add 0 padding based on the max length, simplifying the sort algorithm
    23 for i in (0..NUM_STUDENTS - 1)
    24   arr[i] = arr[i].rjust(max_length, "0")
    25 end
    26 
    27 # Now let's use a radix sort. Go through each digit and 
    28 # add each element to an array corresponding to the digits.
    29 for i in (0..max_length - 1)
    30   # Clear out and reset the bucket
    31   buckets = Hash.new()
    32   for j in 0..9
    33     buckets[j.to_s] = Array.new()
    34   end
    35 
    36   # Add each number to its respective digit bucket
    37   for j in 0..NUM_STUDENTS - 1
    38     num = arr[j]
    39     digit = num[max_length - 1 - i]
    40     buckets[digit].push(num)
    41   end
    42   # Flatten the buckets into a one-dimensional array
    43   arr = buckets.values.flatten
    44 end
    45 
    46 # Now output the sorted array
    47 puts "Sorted array:"
    48 for i in (0..NUM_STUDENTS - 1)
    49   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    50 end

7.2 Complexity Analysis

To evaluate an algorithm, a common approach is to analyze its complexity. That is, we essentially count the number of steps involved in executing the algorithm.

An intuitive explanation of complexity analysis is the following. We caution you that our explanation is clearly an oversimplification, but it suffices for our purposes. Given a certain input size, assuming that to process a single element takes one unit of time, how many units of time are involved in processing n elements of input? This is essentially what complexity analysis attempts to answer. As can be seen, it is unnecessary to determine exactly the computer time involved in each step; instead, we simply determine the number of logical steps that occur in a given algorithm. In reality, we can have families of steps (say, one family is addition and subtraction, the other multiplication and division). We then count how many steps of each family are required.

A simple example will be to evaluate the complexity of computing a²+ab+b² for a large number, say, n, of pairs of a and b. Computing directly, we should have 3n multiplications and 2n additions. However, we can compute the same expression using (a + b)² – ab, which can be done in 2n multiplications and 2n additions (note that we consider addition and subtraction to be in the same family of steps). Thus, the second expression is better than the original. For very large values of n, this may make a significant difference in computation time. This is a very simple example, but it provides a background for our discussions of the complexity of sorting algorithms.

In complexity analysis, we forgo constants; thus, the distinctions between n and n – 1 in terms of complexity are nonexistent. More so, we often assume that all computations are of the same family of operations. In terms of our complexity analysis, it does not matter whether the list shrinks or grows; for simplicity, assume it shrinks.

Now consider the three presented comparison-based sorting algorithms. For all, the outer loop has n steps, and for the inner loop the size of the list shrinks by one with each pass. So the first time it takes n steps, the next time n – 1, the next time n – 2, and so on. Thus, the number of steps is:

n + (n – 1) + (n – 2) + ... + 3 + 2 = 2 + 3 + ... + (n – 2) + (n – 1) + n

If you add 1 to the rewriting of the sum, it becomes a well-known arithmetic series, and its total is $\frac{{\displaystyle n(n+1)}}{{\displaystyle 2}}$. So the total number of steps for these sorts is $\frac{{\displaystyle n(n+1)}}{{\displaystyle 2}}-1$.

Clearly, for any n > 0, $\frac{{\displaystyle n(n+1)}}{{\displaystyle 2}}-1$ is less than n²; however, the complexity is still considered roughly n². The official notation is $\mathit{O}\left({\mathit{n}}^2\right)$ and is pronounced “on the order of” or “big oh.” The reason the complexity is $\mathit{O}\left({\mathit{n}}^2\right)$ is because complexity is only an approximation, and clearly the dominant portion of $\frac{{\displaystyle n(n+1)}}{{\displaystyle 2}}-1$ is n². For our purposes, if you grasp the concept of the dominant portion to determine complexity, you are ahead of the game.

For the complexity analogies, cn², where c is a constant, is considered $\mathit{O}\left({\mathit{n}}^2\right)$ for any finite c. For actual computations, however, the value of c may be important. Again, refer to a book on complexity theory to understand, in detail, this important concept. For a reading list on algorithms and complexity, see Appendix A.

7.3 Searching

Searching a list of names or numbers is another very common computer science task. There are many search algorithms, but the key in developing a search algorithm is to determine which type of candidate search process matches the particular need. The following are the two questions (parameters) that affect our search algorithm selection:

• Is the list we are searching sorted or unsorted?

• Are the searched list elements unique, or are there duplicate values within the list?

     1 # Code for linear search
     2 NUM_STUDENTS = 35
     3 MAX_GRADE = 100
     4 arr = Array.new(NUM_STUDENTS)
     5 value_to_find = 8
     6 i = 1
     7 found = false
     8 
     9 # Randomly put some student grades into arr
    10 for i in (0..NUM_STUDENTS - 1)
    11   arr[i] = rand(MAX_GRADE + 1)
    12 end
    13 
    14 puts "Input List:"
    15 for i in (0..NUM_STUDENTS - 1)
    16   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    17 end
    18 i = 0
    19 # Loop over the list until it ends or we have found our value
    20 while ((i < NUM_STUDENTS) and (not found))
    21   # We found it :)
    22   if (arr[i] == value_to_find)
    23     puts "Found " + value_to_find.to_s + " at position " + i.to_s + " of 
           the list."
    24     found = true
    25   end
    26   i = i + 1
    27 end
    28 
    29 # If we haven't found the value at this point, it doesn't exist in our list
    30 if (not found)
    31   puts "There is no " + value_to_find.to_s + " in the list."
    32 end

     1 # Code for binary search
     2 NUM_STUDENTS = 30
     3 MAX_GRADE = 100
     4 arr = Array.new(NUM_STUDENTS)
     5 # The value we are looking for
     6 value_to_find = 7
     7 low = 0
     8 high = NUM_STUDENTS - 1
     9 middle = (low + high) / 2
    10 found = false
    11 
    12 # Randomly put some exam grades into the array
    13 for i in (0..NUM_STUDENTS - 1)
    14   new_value = rand(MAX_GRADE + 1)
    15   # make sure the new value is unique
    16   while (arr.include?(new_value))
    17     new_value = rand(MAX_GRADE + 1)
    18   end
    19   arr[i] = new_value
    20 end
    21 # Sort the array (with Ruby's built-in sort)
    22 arr.sort!
    23 
    24 print "Input List: "
    25 for i in (0..NUM_STUDENTS - 1)
    26   puts "arr[" + i.to_s + "] ==> " + arr[i].to_s
    27 end
    28 
    29 while ((low <= high) and (not found)) 
    30   middle = (low + high) / 2
    31   # We found it :)
    32   if arr[middle] == value_to_find 
    33     puts "Found grade " + value_to_find.to_s + "% at position " + middle.to_s
    34     found = true
    35   end
    36 
    37   # If the value should be lower than middle, search the lower half,
    38   # otherwise, search the upper half
    39   if (arr[middle] < value_to_find)
    40     low = middle + 1
    41   else
    42     high = middle - 1
    43   end
    44 end
    45 
    46 if (not found)
    47   puts "There is no grade of " + value_to_find.to_s + "% in the list."
    48 end

7.4 Summary

We discussed the various sorting schemes, both comparison-based and non-comparison-based, and the strengths of each. We introduced the field of complexity analysis, a tool used to quantify the performance of an algorithm. Finally, we discussed searching and provided a real-world example of searching techniques.

Specifically, we described four elementary sorting algorithms. The first three presented—selection, insertion, and bubble sort—are comparison based. That is, elements are compared against one another to determine a sorted ordering. The fourth algorithm, radix sort, differs substantially. Instead of comparing elements, radix sort orders the elements according to their representation, starting from the rightmost digit. Once all digits of the element representation are processed, the list is sorted. The complexity of these sorting algorithms is presented in Table 7-1, where n represents the number of elements in the list and k represents the number of digits needed to represent the largest element. The best-case scenario occurs when the original list is already sorted; the worst-case scenario occurs when the original list is in reserve order; and the average-case scenario represents an original random ordering.

Likewise, we presented two searching algorithms: linear and binary search. Linear search can be used to search any list, whereas binary search requires a sorted list. The complexity of these searching algorithms is presented in Table 7-2, where n represents the number of elements in the list searched. The best-case scenario occurs when the first element encountered is the element sought; the worst-case scenario occurs when the sought after element is missing; and the average-case scenario represents a random list.

7.5 Exercises

1. Radix sort, as presented, works for integers. Modify the algorithm in Example 7-4 to sort English names.

2. For each input sequence provided in the following list, state which presented comparison-based sort or sorts would require the fewest steps. Explain why.

   1. 5 2 4 3 1

   2. 1 2 3 4 5

   3. 5 4 3 2 1

3. You are provided a lengthy unsorted list and told to search it.

   1. Which search algorithm would you use?

   2. If you were told that you will need to search the list many times, would your search strategy change? If so, how?

   3. At which point would you change your approach if you were to change it?

4. The complexity of the comparison-based sorting algorithms presented, on the average case, is $\mathit{O}\left({\mathit{n}}^2\right)$. Design a comparison-based sorting algorithm with a lower complexity. What is the underlying premise that lowers its complexity?

5. Generate a 100-element list containing integers in the range 0–10. Sort the list with selection sort and with radix sort.

   1. Which is faster? Why?

   2. Try this again, but with 10,000 elements. Note the relative difference. Why does it exist?