Looking For The Error In My Selection Sort Algorithm

[npsgaming]

I have put together some code for a homework assignment and I have almost got it working. There are a few key items that are missing or not fully functional and I am fresh out of ideas on how to attack it. The code is to take 9 digits/integers from a user's input and through a "selection sort" put them in order from least to greatest. I am also supposed to show the array for each step the code takes (each time a number moves).

/*%%%%%%%%%%%%%%%%%%%%%%
Selection Sort Algorithm
%%%%%%%%%%%%%%%%%%%%%%*/


#include <iostream>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <string>
#include <cstdlib>

using namespace std;

const int arraysize = 9; //size of the array to sort. is the target number.
int values[ arraysize ]; //values here is the variable [arraysize] tells us how many entries are in this array "values"
int temp_lower,temp_upper;
void arraybuilder()
{
	cout << "Please enter 9 integers. Don't forget to hit enter after each integer: " << endl; //prompt for values to enter.

	for ( int i = 0; i < arraysize; i++ ) //loop 1 tracks how many times the system has run and if there have been 10 entries yet. 
		cin >> values[ i ]; //if there are less than 10 entries in the array "values" add another.

	cout <<"unsorted array:\n"; //display for the user the values they have entered. 


}
//Use the function prototypes:
void insertSort()
{
	cout<<endl;
  for(int o=0; o<arraysize;o++)
  {
	  temp_lower=values[o];
	  int p=o-1;
	  while(values[p]>values[p+1]&&p>=0)
	  {
		  temp_upper=values[p];
		  cout<<"verify "<<temp_lower<<" and "<<temp_upper<<" and "<<values[o]<<" and "<<values[o+1]<<endl; //This line is not necessary but helps to determine what values are in the variables.
		  p--;
	  }
	  values[p+1]=temp_lower;
  }
}

void printArray()
{
	cout<<endl;
  for(int o=0; o<arraysize;o++)
  {
	  cout<<setw(4)<<values[o];
  }
}
int main()
{
	 arraybuilder();
	 cout<<endl<<"Part 1."<<endl;
	 printArray();
	 cout<<endl<<"Part 2."<<endl;
	 insertSort();
	 cout<<endl<<"Part 3."<<endl;
	 printArray();
	 cout<<endl<<"Part 4. Done."<<endl;

cout << "\nSelection Sort Array:\n"; //prints sorted array for user. 
for (int l = 0; l < arraysize; l++ )
		cout << setw( 4 ) << values[ l ];

	cout << endl;
  system("pause");
  return 0;
}

This is what I have so far. We were told to use "void prototypes" for every function. And when I debug the code/run it I enter the integers 9-1 in the opposite order giving "worst case scenario" but the output is always 8,7,6,5,4,3,2,1,1 which makes me think the problem is something incredibly simple but I can't see it.

[npsgaming]

I am still looking for the error and am still coming up blank. Anyone have an idea?

[deceptikon]

I see a few problems with the sorting algorithm:

int p = o - 1;

When the loop first starts, o is 0, but the next thing the code does is compare values[p] with values[p + 1]. That's the same as saying values[-1] > values[0] , which is an out of bounds array access. The test for p >= 0 should come first to protect against an invalid access.

temp_upper = values[p];

temp_upper is only assigned to in the function, so this line effectively does nothing.

The algorithm looks like half of insertion sort and half of selection sort, which totals to nothing at all. ;) The process of selection sort is for each element, find the smallest or largest remaining element and swap the two. If moving from right to left, look for the largest, and if moving from left to right, look for the smallest. It looks like this for left to right:

void selectSort()
{
    // For each element in the array
        // Starting with the next element
            // Look for a smaller value
        
        // If the current element isn't the smallest
            // Swap with the smaller value that was found
}

Filling in the comments with actual code is straightforward once you understand the logic:

void selectSort()
{
    // For each element in the array
    for (int i = 0; i < arraysize; i++)
    {
        int min_index = i;
        
        // Starting with the next element
        for (int j = i + 1; j < arraysize; j++)
        {
            // Look for a smaller value
            if (values[j] < values[min_index])
            {
                min_index = j;
            }
        }
        
        // If the current element isn't the smallest
        if (min_index != i)
        {
            // Swap with the smaller value that was found
            swap(&values[i], &values[min_index]);
        }
    }
}