Selection Sort algorithm in depth with C++
To represent this sorting algorithm we can visualize an array of unsorted integers. From there we start by marking the first integer and calling it Small. All the other numbers in the array will then be to the right of Small. We will then compare Small with all the other integers to the right. Checking if they are less than Small, and if so, we will be replacing the variable Small with the lowest value found.
Let's imagine we have a array of integers 7, 8, 5, 4, 9, 2. In that case Small will be equal to 7 (Being the blue arrow). Now let's compare Small with the numbers to the right (The yellow arrow). Checking if they are in fact less than Small.
So with the example above, we will first be checking if 8 < 7. If that's true, then we will have to switch Small = 7 with Small = 8. In this case, that simply isn't true. So we will have to move on with comparing Small = 7 with the other integers in the list.
For the next step we can see that 5 will be less than 7, which means that we will have to set Small = 5. From there we will repite the process and try to look for something smaller than 5.
One thing that is important to know here is that Small is an external variable. It isn't something that will override anything in the array of integers yet. Moving on with trying to find the smallest value we will eventually land on 2. Small will then be set equal to 2. From there, we will have to get the value Small = 2 to be in front of the array of integers.
Because we cannot just say that array[0] = Small. That'll make us override 7 and leave us with a replica of the number 2. In this case, both at the start and at the end.
We would rather have to swap the values with eachother. Moving 2 at the start and 7 at the end.
By that we are fulfilling the idea of swapping the two integers with eachother. Now for the next round we will move one up and select Small = 8. Then comparing Small with the rest of the integers to the right.
From there we will check if 5 < 8 and see that it's true. So we'll change Small = 5. In other words, repeating the process from above. So instead of doing that manually, let's take a look at the C++ code for the selection sort algorithm.
By looking over the code we can see that we're first taking in two parameters, one being an array of integers and the other an integer. The array would be the actual array with integers having to be sorted, and the integer variable len would be the length of the array.
From there we will have a for-loop that goes from 0 to (len - 1). If we imagine the array having a length on 10, the loop will go from 0 to 9. Where the last integer would be seen as already sorted by the end, since the last integer will have the highest value. That'll save us one operation.
Furthermore, after the for-loop we can see that we have a variable called small. This variable will have the same function as displayed above when the array was sorted manually. The variable small will be set as small = i. Which will give small = 0 for the first round. From there we will run another for-loop that starts from j = i + 1. For the first round, j = 1. This for-loop will also go all the way up to j < 10.
In many ways one can see the blue arrow as the first for-loop, whilst the yellow arrow as the second for-loop. It's also worth to point out that since the second for-loop is inside the first for-loop, the second for-loop has to go all the way up from j = i + 1 to j < len for every time the first for-loop is executed. This will happen when i = 0, i = 1, i = 2 and all the way up to i = (len - 1). Visually we can see this as the blue arrow being fixed at one integer whilst the yellow arrow going through all the rest of the integers.
The reason for doing this is what happens inside the second for-loop. Here we can see that there's an if-statement saying that if arr[j] < arr[small] then small = j. This will be the same as checking if the yellow arrow is less than the blue arrow. If it is, then small has to be set to the lowest value. But let's take a further look into that.
Let's imagine that our array with a length of 10 has the numbers 1, 7, 4, 0, 9, 4, 8, 8, 2, 4. Then small = i = 0 will give arr[small] = 1. Simultaneously will we get j = i + 1 = 1 and arr[j] = 7. So in other words, we're checking if 7 < 1. In this case, that isn't true. But, if it were to be true we would have set small = j.
After the second for-loop has ended we want to swap arr[small] with arr[i]. Manually we did this with the numbers 2 and 7 above. Basically arr[i] is the value from the index we started at with the first for-loop, whilst arr[small] is the lowest value we found. We could read it as "The array's position small will be swapped with the space on i". Visually we can see an example of this as.
Letting small be the yellow arrow and i be the blue arrow. Another way we could write the swap function manually would be.
But let's see this in action with a complete program.
Firstly, we can create two more functions for our program. One being a way to generate an array with random integers, and the other being a way of displaying the array. We can start with the generating of random integers.
Here we can see that we're taking in two parameters, one being the array and the other the length of the array. Then we're having a for-loop that fills the array up with random integers from 0 - 9. Moving on to displaying the array.
Pretty much the same concept, but instead of filling the array we're printing it out. Now, we could go into main and make the program run.
So what we're doing here is that we are creating an array with the size of 10. Then we send it to get filled. In this case, let's imagine the array gets filled with the integers 1, 7, 4, 0, 9, 4, 8, 8, 2, 4. After that we are printing out the array. For having it then sent to the selection sorth algorithm. After it's done there, it'll be 0, 1, 2, 4, 4, 4, 7, 8, 8, 9. Which is also what we are finally printing out.
Let's imagine we have a array of integers 7, 8, 5, 4, 9, 2. In that case Small will be equal to 7 (Being the blue arrow). Now let's compare Small with the numbers to the right (The yellow arrow). Checking if they are in fact less than Small.
For the next step we can see that 5 will be less than 7, which means that we will have to set Small = 5. From there we will repite the process and try to look for something smaller than 5.
One thing that is important to know here is that Small is an external variable. It isn't something that will override anything in the array of integers yet. Moving on with trying to find the smallest value we will eventually land on 2. Small will then be set equal to 2. From there, we will have to get the value Small = 2 to be in front of the array of integers.
Because we cannot just say that array[0] = Small. That'll make us override 7 and leave us with a replica of the number 2. In this case, both at the start and at the end.
We would rather have to swap the values with eachother. Moving 2 at the start and 7 at the end.
By that we are fulfilling the idea of swapping the two integers with eachother. Now for the next round we will move one up and select Small = 8. Then comparing Small with the rest of the integers to the right.
From there we will check if 5 < 8 and see that it's true. So we'll change Small = 5. In other words, repeating the process from above. So instead of doing that manually, let's take a look at the C++ code for the selection sort algorithm.
void selectionSort(int arr[], int len) {
for (int i = 0; i
< (len - 1); i++) {
int small = i;
for (int j = i +
1; j < len; j++) {
if (arr[j] < arr[small])
{
small = j;
}
}
swap(arr[small], arr[i]);
}
}
By looking over the code we can see that we're first taking in two parameters, one being an array of integers and the other an integer. The array would be the actual array with integers having to be sorted, and the integer variable len would be the length of the array.
From there we will have a for-loop that goes from 0 to (len - 1). If we imagine the array having a length on 10, the loop will go from 0 to 9. Where the last integer would be seen as already sorted by the end, since the last integer will have the highest value. That'll save us one operation.
Furthermore, after the for-loop we can see that we have a variable called small. This variable will have the same function as displayed above when the array was sorted manually. The variable small will be set as small = i. Which will give small = 0 for the first round. From there we will run another for-loop that starts from j = i + 1. For the first round, j = 1. This for-loop will also go all the way up to j < 10.
In many ways one can see the blue arrow as the first for-loop, whilst the yellow arrow as the second for-loop. It's also worth to point out that since the second for-loop is inside the first for-loop, the second for-loop has to go all the way up from j = i + 1 to j < len for every time the first for-loop is executed. This will happen when i = 0, i = 1, i = 2 and all the way up to i = (len - 1). Visually we can see this as the blue arrow being fixed at one integer whilst the yellow arrow going through all the rest of the integers.
The reason for doing this is what happens inside the second for-loop. Here we can see that there's an if-statement saying that if arr[j] < arr[small] then small = j. This will be the same as checking if the yellow arrow is less than the blue arrow. If it is, then small has to be set to the lowest value. But let's take a further look into that.
if (arr[j] < arr[small]) {
small = j;
}
Let's imagine that our array with a length of 10 has the numbers 1, 7, 4, 0, 9, 4, 8, 8, 2, 4. Then small = i = 0 will give arr[small] = 1. Simultaneously will we get j = i + 1 = 1 and arr[j] = 7. So in other words, we're checking if 7 < 1. In this case, that isn't true. But, if it were to be true we would have set small = j.
After the second for-loop has ended we want to swap arr[small] with arr[i]. Manually we did this with the numbers 2 and 7 above. Basically arr[i] is the value from the index we started at with the first for-loop, whilst arr[small] is the lowest value we found. We could read it as "The array's position small will be swapped with the space on i". Visually we can see an example of this as.
Letting small be the yellow arrow and i be the blue arrow. Another way we could write the swap function manually would be.
int temp = arr[i];
arr[i] = arr[small];
arr[small] = temp;
But let's see this in action with a complete program.
Firstly, we can create two more functions for our program. One being a way to generate an array with random integers, and the other being a way of displaying the array. We can start with the generating of random integers.
void fill(int arr[], int len) {
for (int i = 0; i
< len; i++) {
arr[i] = rand() % 10;
}
}
Here we can see that we're taking in two parameters, one being the array and the other the length of the array. Then we're having a for-loop that fills the array up with random integers from 0 - 9. Moving on to displaying the array.
void print(int arr[], int len) {
for (int i = 0; i
< len; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
Pretty much the same concept, but instead of filling the array we're printing it out. Now, we could go into main and make the program run.
int main(){
int const length =
10;
int array[length];
fill(array, length);
print(array, length);
print(array, length);
selectionSort(array, length);
print(array, length);
print(array, length);
return 0;
}
So what we're doing here is that we are creating an array with the size of 10. Then we send it to get filled. In this case, let's imagine the array gets filled with the integers 1, 7, 4, 0, 9, 4, 8, 8, 2, 4. After that we are printing out the array. For having it then sent to the selection sorth algorithm. After it's done there, it'll be 0, 1, 2, 4, 4, 4, 7, 8, 8, 9. Which is also what we are finally printing out.
Comments
Post a Comment