7.7 Sorting and Searching arrays

In this section, we use the built-in C++ Standard Library sort function to arrange the elements in an array into ascending order and the built-in binary_search function to determine whether a value is in the array.

7.7.1 Sorting

Sorting data—placing it into ascending or descending order—is one of the most important computing applications. A bank sorts all checks by account number so that it can prepare individual bank statements at the end of each month. Telephone companies sort their phone directories by last name—and within all entries with the same last name, sort those by first name—to make it easy to find phone numbers. Virtually every organization must sort some data and, in many cases, massive amounts of it. Sorting data is an intriguing problem that has attracted some of the most intense research efforts in the field of computer science. In Chapter 20, we investigate and implement several sorting schemes, discuss their performance and introduce Big O (pronounced “Big Oh”) notation for characterizing how hard each scheme works to accomplish its task.

7.7.2 Searching

Often it may be necessary to determine whether an array contains a value that matches a certain key value. The process of finding a particular element of an array is called searching. In Chapter 20, we investigate and implement two search algorithms—the simple but slow linear search for searching an unordered array and the more complex but much faster binary search for searching an ordered array.

7.7.3 Demonstrating Functions sort and binary_search

Figure 7.15 begins by creating an unsorted array of strings (lines 12–13) and displaying the contents of the array (lines 17–19). Next, line 21 uses C++ Standard Library function sort to sort the elements of the array colors into ascending order. The sort function’s arguments specify the range of elements that should be sorted—in this case, the entire array. The arguments colors.begin() and colors.end() represent the array’s beginning and end, respectively—we’ll discuss the complete details of begin and end in Chapter 15. As you’ll see, function sort can be used to sort the elements of several different types of data structures. Lines 25–27 display the contents of the sorted array.

Fig. 7.15 Sorting and searching arrays.

Alternate View 

 1   // Fig. 7.15: fig07_15.cpp
 2   // Sorting and searching arrays.
 3   #include <iostream>
 4   #include <iomanip>
 5   #include <array>
 6   #include <string>
 7   #include <algorithm> // contains sort and binary_search
 8   using namespace std;
 9
10   int main() {
11      const size_t arraySize{7}; // size of array colors
12      array<string, arraySize> colors{"red", "orange", "yellow",
13         "green", "blue", "indigo", "violet"};
14
15      // output original array
16      cout << "Unsorted array:
";
17      for (string color : colors) {
18         cout << color << " ";
19      }
20
21      sort(colors.begin(), colors.end()); // sort contents of colors
22
23      // output sorted array
24      cout << "
Sorted array:
";
25      for (string item : colors) {
26         cout << item << "";
27      }
28
29      // search for "indigo" in colors
30      bool found{binary_search(colors.begin(), colors.end(), "indigo")};
31      cout << "

"indigo" " << (found ? "was" : "was not")
32         << " found in colors" << endl;
33
34      // search for "cyan" in colors
35      found = binary_search(colors.begin(), colors.end(), "cyan");
36      cout << ""cyan" " << (found ? "was" : "was not")
37         << " found in colors" << endl;
38   }


Unsorted array:
red orange yellow green blue indigo violet
Sorted array:
blue green indigo orange red violet yellow

"indigo" was found in colors
"cyan" was not found in colors

Lines 30 and 35 use binary_search to determine whether a value is in the array. The sequence of values first must be sorted in ascending order—binary_search does not verify this for you. The function’s first two arguments represent the range of elements to search and the third is the search key—the value to locate in the array. The function returns a bool indicating whether the value was found. In Chapter 16, we’ll use the C++ Standard function find to obtain the location of a search key in an array.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset