There are many different cases in which sorting an array can be useful. Algorithms (such as searching to see if a number exists in an array) can often be made simpler and/or more efficient when the input data is sorted. Furthermore, sorting is often useful for human readability, such as when printing a list of names in alphabetical order.
Sorting is generally performed by repeatedly comparing pairs of array elements, and swapping them if they meet some criteria. The order in which these elements are compared differs depending on which sorting algorithm is used, and the criteria depends on how the list will be sorted (ascending or descending order). To swap two elements, we can use the swap() function from the C++ standard library. Swap is defined in the algorithm header, and lives in the std namespace.
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <algorithm> // for swap#include <iostream>int main(){ using namespace std; int x = 2; int y = 4; cout << "Before swap: x = " << x << ", y = " << y << endl; swap(x, y); // swap also lives in std namespace cout << "After swap: x = " << x << ", y = " << y << endl;} |
This program prints:
Note that after the swap, the values of x and y have been interchanged!
Selection sort
There are many ways to sort an array. Selection sort is probably the easiest sort to understand, which makes it a good candidate for teaching even though it is one of the slower sorts.
Selection sort performs the following steps:
1) Starting at index 0, search the entire array to find the smallest value
2) Swap the smallest value found with the value at index 0
3) Repeat steps 1 & 2 starting from the next index
1) Starting at index 0, search the entire array to find the smallest value
2) Swap the smallest value found with the value at index 0
3) Repeat steps 1 & 2 starting from the next index
In other words, we’re going to find the smallest element in the array, and put it in the first position. Then we’re going to find the next smallest element, and put it in the second position. This process will be repeated until we run out of elements.
Here is an example of this algorithm working on 5 elements. Let’s start with a sample array:
{ 30, 50, 20, 10, 40 }
First, we find the smallest element, starting from index 0:
{ 30, 50, 20, 10, 40 }
We then swap this with the element at index 0:
{ 10, 50, 20, 30, 40 }
Now that the first element is sorted, we can ignore it. Consequently, we find the smallest element, starting from index 1:
{ 10, 50, 20, 30, 40 }
And swap it with the element in index 1:
{ 10, 20, 50, 30, 40 }
Find the smallest element starting at index 2:
{ 10, 20, 50, 30, 40 }
And swap it with the element in index 2:
{ 10, 20, 30, 50, 40 }
Find the smallest element starting at index 3:
{ 10, 20, 30, 50, 40 }
And swap it with the element in index 3:
{ 10, 20, 30, 40, 50 }
Finally, find the smallest element starting at index 4:
{ 10, 20, 30, 40, 50 }
And swap it with the element in index 4 (which doesn’t do anything):
{ 10, 20, 30, 40, 50 }
Done!
{ 10, 20, 30, 40, 50 }
Here’s how this algorithm is implemented in C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| const int nSize = 5;int anArray[nSize] = { 30, 50, 20, 10, 40 };// Step through each element of the arrayfor (int nStartIndex = 0; nStartIndex < nSize; nStartIndex++){ // nSmallestIndex is the index of the smallest element // we've encountered so far. int nSmallestIndex = nStartIndex; // Search through every element starting at nStartIndex+1 for (int nCurrentIndex = nStartIndex + 1; nCurrentIndex < nSize; nCurrentIndex++) { // If the current element is smaller than our previously found smallest if (anArray[nCurrentIndex] < anArray[nSmallestIndex]) // Store the index in nSmallestIndex nSmallestIndex = nCurrentIndex; } // Swap our start element with our smallest element swap(anArray[nStartIndex], anArray[nSmallestIndex]);} |
The most confusing part of this algorithm is the nested loop. The outside loop (nStartIndex) steps through each element one by one. The inner loop (nCurrentIndex) finds the smallest element in the array starting from nStartIndex and sets the variable nSmallestIndex to point to it. The smallest index is then swapped with the start index. Then the outer loop (nStartIndex) advances one element, and the process is repeated.
Quiz
1) Selection sort the following array: { 30, 60, 20, 50, 40, 10 }. Show the array after each swap that takes place.
2) Rewrite the selection sort code above to sort in descending order (largest numbers first). Although this may seem complex, it is actually surprisingly simple.
0 comments: