#include <iostream>
#include <Windows.h>
void selection_sort(int*,int);
void output_array(int*, int);
int main() {
using namespace std;
int numbers[] = { 4, 6, 8, 2, 7, 5, 0,1, 3, 9 };
int length = 10;
selection_sort(numbers, length);
output_array(numbers, length);
Sleep(10000);
return 0;
}
void output_array(int* start, int length) {
for (int i = 0; i < length; i ) {
std::cout << *(start i) << " ";
}
std::cout << std::endl;
}
void selection_sort(int* start, int length) {
for (int i = 0; i < length; i ) {
int max = *start;
int max_i = 0;
for (int j = 1; j < (length - i); j ) {
//find out the maximum
if (max < *(start j)) {
max = *(start j);
max_i = j;
}
}
//put it at the end
for (int k = max_i; k < (length - i -1); k ) { //The problem is HERE
*(start k) = *(start k 1);
}
*(start length - i) = max;
}
}
Perhaps it is a problem simple enough, but why when it comes to the last for loop, k is undefined? Is it because max_i is not a compile-time constant? Variables Program at this step This doesn't make sense to me.
When it comes to the second largest number, k behaves as expected.
CodePudding user response:
It seems I have got it. length
is 10, max_i
is 9, i
is 0 till 9. Your loop becomes
for (int k = 9; k < (10 - i -1); k ) {
*(start k) = *(start k 1);
}
k < 9 - i
never gets true and the loop never runs. You have an error in the program logic.
CodePudding user response:
In the following line:
*(start length - i) = max;
i
has the range 0
to length - 1
this means the above line evaluates at the extreme values of i
to:
*(start 1) = max;
And:
*(start length) = max;
This means you both never write to the first element in your array and you also write after the last element in the array. The latter means your program has undefined behaviour, in this particular case as start
is on the stack it will likely cause other variables on the stack to be corrupted.
The correct code is:
*(start length - i - 1) = max;
Which results in:
*(start) = max;
And:
*(start length - 1) = max;
On an unrelated note you can also use the simpler syntax:
start[length - i - 1] = max;
CodePudding user response:
void selection_sort(int* start, int length) {
for (int i = 0; i < length; i ) {
int max = *start;
int max_i = 0;
for (int j = 1; j < (length - i); j ) {
//find out the maximum
if (max < *(start j)) {
max = *(start j);
max_i = j;
}
}
//put it at the end
for (int k = max_i; k < (length - i -1); k ) {
*(start k) = *(start k 1);
}
// The problem was here, you wanted to access memory that does not belong to you.
*(start length - i - 1) = max;
}