Sorting and Searching in C++ Language
introduced the fundamentals of making and using vectors. In this chapter we explore some common algorithms for ordering elements within a vector and for locating elements by their value rather than by their index
Sorting
We will use the generic term sequence to refer to either a vector or an array. Sorting—arranging the elements within a sequence into a particular order—is a common activity. For example, a sequence of integers may be arranged in ascending order (that is, from smallest to largest). A sequence of words (strings) may be arranged in lexicographical (commonly called alphabetic) order. Many sorting algorithms exist, and some perform much better than others. We will consider one sorting algorithm that is relatively easy to implement.
// n is A's length
for (int i = 0; i < n - 1; i++) {
// Examine all the elements
// A[j], where j > i.
// If any of these A[j] is less than A[i],
// then exchange A[i] with the smallest of these elements.
}The directive at Step 2 beginning with “Examine all the elements A[ j], where j > i” also requires a loop. We continue refining our implementation with: The directive at Step 2 beginning with “Examine all the elements A[ j], where j > i” also requires a loop. We continue refining our implementation with:
The directive at Step 2 beginning with “Examine all the elements A[ j], where j > i” also requires a loop. We continue refining our implementation with:
// n is A's length
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Examine all the elements
// A[j], where j > i.
}
// If any A[j] is less than A[i],
// then exchange A[i] with the smallest of these elements.
}In order to determine if any of the elements is less than A[i], we introduce a new variable named small. The purpose of small is to keep track of the position of the smallest element found so far. We will set small equal to i initially because we wish to locate any element less than the element found at position i.
// n is A's length
for (int i = 0; i < n - 1; i++) {
// small is the position of the smallest value we've seen
// so far; we use it to find the smallest value less than A[i]
int small = i;
for (int j = i + 1; j < n; j++) {
if (A[j] < A[small])
small = j; // Found a smaller element, update small
}
// If small changed, we found an element smaller than A[i]
if (small != i)
// exchange A[small] and A[i]
}#include <iostream>
#include <vector>
/*
* swap(a, b)
* Interchanges the values of memory
* referenced by its parameters a and b.
* It effectively interchanges the values
* of variables in the caller's context.
*/
void swap(int & a, int & b) {
int temp = a;
a = b;
b = temp;
}
/*
* selection_sort
* Arranges the elements of vector a into ascending order.
* a is a vector that contains integers.
*/
void selection_sort(std::vector < int > & a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
// Note: i,small, and j represent positions within a
// a[i], a[small], and a[j] represents the elements at
// those positions.
// small is the position of the smallest value we've seen
// so far; we use it to find the smallest value less
// than a[i]
int small = i;
// See if a smaller value can be found later in the vector
for (int j = i + 1; j < n; j++)
if (a[j] < a[small])
small = j; // Found a smaller value
// Swap a[i] and a[small], if a smaller value was found
if (i != small)
swap(a[i], a[small]);
}
}
/*
* print
* Prints the contents of a vector of integers.
* a is the vector to print.
* a is not modified.
*/
void print(const std::vector < int > & a) {
int n = a.size();
std::cout << '{';
if (n > 0) {
std::cout << a[0]; // Print the first element
for (int i = 1; i < n; i++)
std::cout << ',' << a[i]; // Print the rest
}
std::cout << '}';
}
int main() {
std::vector < int > list {23,-3,4,215,0,-3,2,23,100,88,-10};
std::cout << "Before: ";
print(list);
std::cout << '\n';
selection_sort(list);
std::cout << "After: ";
print(list);
std::cout << '\n';
}Before: {23,-3,4,215,0,-3,2,23,100,88,-10}
After: {-10,-3,-3,0,2,4,23,23,88,100,215}Flexible Sorting
What if we want to change the behavior of the sorting function in so that it arranges the elements in descending order instead of ascending order? It is actually an easy modification; simply change the line
#include <iostream>
#include <vector>
/*
* less_than(a, b)
* Returns true if a < b; otherwise, returns
* false.
*/
bool less_than(int a, int b) {
return a < b;
}
/*
* greater_than(a, b)
* Returns true if a > b; otherwise, returns
* false.
*/
bool greater_than(int a, int b) {
return a > b;
}
/*
* selection_sort(a, compare)
* Arranges the elements of a in an order determined
* by the compare function.
* a is a vector of integers.
* compare is a function that compares the ordering of
* two integers.
*/
void selection_sort(std::vector < int > & a, bool( * compare)(int, int)) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
// Note: i,small, and j represent positions within a
// a[i], a[small], and a[j] represents the elements at
// those positions.
// small is the position of the smallest value we've seen
// so far; we use it to find the smallest value less
// than a[i]
int small = i;
// See if a smaller value can be found later in the vector
for (int j = i + 1; j < n; j++)
if (compare(a[j], a[small]))
small = j; // Found a smaller value
// Swap a[i] and a[small], if a smaller value was found
if (i != small)
std::swap(a[i], a[small]); // Uses std::swap
}
}
/*
* print
* Prints the contents of an integer vector
* a is the vector to print.
* a is not modified.
*/
void print(const std::vector < int > & a) {
int n = a.size();
std::cout << '{';
if (n > 0) {
std::cout << a[0]; // Print the first element
for (int i = 1; i < n; i++)
std::cout << ',' << a[i]; // Print the rest
}
std::cout << '}';
}
int main() {
std::vector < int > list{ 23, -3, 4, 215, 0, -3, 2, 23, 100, 88, -10 };
std::cout << "Original: ";
print(list);
std::cout << '\n';
selection_sort(list, less_than);
std::cout << "Ascending: ";
print(list);
std::cout << '\n';
selection_sort(list, greater_than);
std::cout << "Descending: ";
print(list);
std::cout << '\n';
}//Output
Original: {23,-3,4,215,0,-3,2,23,100,88,-10}
Ascending: {-10,-3,-3,0,2,4,23,23,88,100,215}
Descending: {215,100,88,23,23,4,2,0,-3,-3,-10}
