selection sort

[4ET0pfjN]

Hi, I am trying to get my selection sort to work and I wanted to debug to ensure it's printing the correct current smallest element, but it's just an infinite loop when I run it that keeps printing zero, from what I see the logic looks right. Please do not give me
a new algorithm but let me know what I'm doing wrong.

I understand selection sort is to find the smallest elem to swap with the current top of the list, then we shrink the list to
to compare each pass, so the new top to compare with is the next element in line etc.

#include <iostream>

using namespace std;

int main()
{
	int *list = new int[5];
	list[0] = 2;
	list[1] = 4;
	list[2] = 6;
	list[3] = 0;
	list[4] = 1;
	
	//SORTED: 0 1 2 4 6 
	
	int smallestIndex = 0;
	int curSmallestElem = 1999999999;
	
	for ( int i = 0; i < 5; i++ )//FOR THE CURRENT TOP ELEMENT
	{
		// find the cur smallest elem and move it to current front of list (swap)
	    for ( int j = 0; j < 5; j++ )//WE ALWAYS SHRINK THE LIST TO SORT BECAUSE WE DON'T WANT TO COMPARE THE SORTED SIDE (the left side!)
		{
			if ( list[j] < list[i] && list[j] < curSmallestElem)
			{
				curSmallestElem = list[j];//WE UPDATE CURRENT smallest elem if we find a smaller elem!
				
				smallestIndex = j;//KEEP UPDATING cur smallest index
				cout <<"Index of cur smallest elem: "<<smallestIndex<<endl;
			}
		}
		
		//NOW SWAP ****UPDATED*** 
		int tmp = list[i];//so we don't lose track of it during swapping!
		list[i] = curSmallestElem;
		list[smallestIndex] = tmp;
	}

	return 0;
}

[codekiddy]

Hi, I've put comments into your code to find where you was wrong :D

// C++Forum.cpp : Defines the entry point for the console application.
//

#include <iostream>

using namespace std;

int main()
{
	int *list = new int[5];
	list[0] = 2;
	list[1] = 4;
	list[2] = 6;
	list[3] = 0;
	list[4] = 1;
	
	//SORTED: 0 1 2 4 6 
	
	int smallestIndex = 0;
	int curSmallestElem = 1999999999;
	
	for ( int i = 0; i < 5; i++ )//FOR THE CURRENT TOP ELEMENT
	{
		// find the cur smallest elem and move it to current front of list (swap)
	    for ( int j = 0; j < 5; j++ )//WE ALWAYS SHRINK THE LIST TO SORT BECAUSE WE DON'T WANT TO COMPARE THE SORTED SIDE
		{
			if ( list[j] < list[i] && list[j] < curSmallestElem)
			{
				curSmallestElem = list[j];//WE UPDATE CURRENT smallest elem if we find a smaller elem!
				smallestIndex = j;//KEEP UPDATING cur smallest index
			}
		}
		
		//NOW SWAP
		// CHANGE i = curSmallestElem to curSmallestElem = i
		curSmallestElem = i;  //HERE WAS THE PROBLEM (ALLWAYS 0) INFINITE LOOP
		cout <<curSmallestElem<<endl;
		
		smallestIndex = list[i];
		
	}
	delete[] list;  // delete added!
	cin.ignore();  // stop cmd here 
	return 0;
}

[4ET0pfjN]

Actually, can you take a look at this swap part:

//NOW SWAP
	int tmp = list[i];//so we don't lose track of it during swapping!
	list[i] = curSmallestElem;
	list[smallestIndex] = tmp;
	cout <<"Cur smallest elem: "<<curSmallestElem<<endl;
        curSmallestElem = 1999999999;//RESET curSmallestElem 

There's no more infinite loop, but it prints:

Cur smallest elem: 0
Cur smallest elem: 0
Cur smallest elem: 0
Cur smallest elem: 0
Cur smallest elem: 0

[codekiddy]

It print's out zerros cos curSmallestElem is always zerro.

you're posted code has no sence, what are you trying to do?
first example does what you want so why do you want reformulate it?

[Peter87]

I think your first swap was better.

You don't really need to have the variable curSmallestElem because you can always get it by doing list[smallestIndex]. The inner loop should start at i+1 and set smallestIndex=i; at the beginning of the outer loop. In the if statement you should remove list[j] < list[i], what was that doing there?

#include <iostream>

using namespace std;

int main()
{
	int *list = new int[5];
	list[0] = 2;
	list[1] = 4;
	list[2] = 6;
	list[3] = 0;
	list[4] = 1;
	
	//SORTED: 0 1 2 4 6 
	
	for ( int i = 0; i < 5; i++ )//FOR THE CURRENT TOP ELEMENT
	{
		int smallestIndex = i;

		// find the cur smallest elem and move it to current front of list (swap)
		for ( int j = i+1; j < 5; j++ )//WE ALWAYS SHRINK THE LIST TO SORT BECAUSE WE DON'T WANT TO COMPARE THE SORTED SIDE
		{
			if ( list[j] < list[smallestIndex] )
			{
				smallestIndex = j;//KEEP UPDATING cur smallest index
			}
		}
		
		//NOW SWAP
		// CHANGE i = curSmallestElem to curSmallestElem = i
		int tmp = list[i];//so we don't lose track of it during swapping!
		list[i] = list[smallestIndex];
		list[smallestIndex] = tmp;

		
	}
	for (int i=0;i<5;i++)
		cout <<list[i]<<' ';
	cout <<'\n';
	delete[] list;  // delete added!
	cin.ignore();  // stop cmd here 
	return 0;
}

[4ET0pfjN]

Your right, I don't need curSmallestElem, thanks for that Peter87, but now when I print out the "sorted", why is it in reverse order b/c in my algorithm I did specify to put the smallest elem at the smallest index, didn't I? And also, it's sorted as: 4, 6, 2, 1, 0, so the 4 and 6 out of order, why?

Also, do I only use the delete operator with dynamic arrays like the one I have, and then other data types it is assumed C++ compiler automatically clears the memory? (eg: int a = 5; and at end of program, variable a ceases to exist automatically garbage cleanup?)

here is the code

int smallestIndex = 0;
	
	for ( int i = 0; i < 5; i++ )//FOR THE CURRENT TOP ELEMENT
	{
		// find the cur smallest elem and move it to current front of list (swap)
	    for ( int j = 0; j < 5; j++ )//WE ALWAYS SHRINK THE LIST TO SORT BECAUSE WE DON'T WANT TO COMPARE THE SORTED SIDE (the left side!)
		{
			if ( list[j] < list[i] && list[j] < list[smallestIndex] )
			{
				smallestIndex = j;//KEEP UPDATING cur smallest index
				//cout <<"Index of cur smallest elem: "<<smallestIndex<<endl;
			}
		}
		
		//NOW SWAP
		int tmp = list[i];//so we don't lose track of it during swapping!
		list[i] = list[smallestIndex];
		list[smallestIndex] = tmp;
	
	}
	
	//NOW OUTPUT the sorted list
for ( int k = 0; k < 5; k++ )
{
	cout <<list[k]<<", ";
}

[Peter87]

Did you notice that I updated my previous post?
You should always call delete to free memory allocated with new but you don't need to dynamically allocate the array here. You can just declare the array as int list[5]; and you will not have to use delete.