Selection Sort

[smco9]

This is suppose to be a simple selection sort but I think I'm missing something because my output isn't completed sorted right.

void SelectionSort(data list[], int length)
{
	int index;
	int smallestIndex;
	int minIndex;
	data temp;

	for( index = 0; index < length; index++)
	{
		smallestIndex = index;
		for(minIndex = index + 1; minIndex < length; minIndex++)
		{
			if( list[minIndex].stateCity < list[smallestIndex].stateCity)
			{
				smallestIndex = minIndex;
				temp = list[smallestIndex];
				list [smallestIndex] = list[index];
				list[index] = temp;
			
			} // end if
		} // end for loop with minIndex
	} // end for loop index
} // end function SelectionSort

output is AZ, CA, CA, CA, FL, DC, etc. it skips every two or three and throws one out of order.

Can anyone figure out what is missing. I think it has something to do with the minIndex.

[VernonDozier]

You have too many swaps for a selection sort. You should have at most one swap for every trip through the outer loop, so you should not have a swap inside the INNER loop. The algorithm, from Wikipedia.

1. Find the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

You don't know the answer to step 1 until after the inner loop has completed. Therefore step 2 should not occur until after the the inner loop has completed.

[vmanes]

line 8 should have test index < length-1 As VernonDozier mentioned, the proper version of this has the swap after the inner loop has found the one and only smallest remaining item. Doing the swaps inside the inner loop should still give correct result, but it will make the runtime pretty much equal to that of Bubble sort, if not a bit worse.

What's happening is that you are making an incorrect comparison after the first swap. smallestIndex initially point to the place you want to fill, but you change it to point to where you've found the smallest currently seen value. Your further comparisons are then looking at a spot in the unsorted portion instead of at the known smallest value.

Your code, corrected, should be

for( index = 0; index < length; index++)
	{
		//smallestIndex = index;
		for(minIndex = index + 1; minIndex < length; minIndex++)
		{
			if( list[minIndex].stateCity < list[index].stateCity)
			{
				//smallestIndex = minIndex;
				temp = list[minIndex];
				list [minIndex] = list[index];
				list[index] = temp;
			
			} // end if
		} // end for loop with minIndex
	} // end for loop index

But, it would be better to track the smallestIndex, then use that to swap with index outside the inner loop.

[vincent2085]

1.
for( index = 0; index < length; index++)
2.
{
3.
//smallestIndex = index;
4.
for(minIndex = index + 1; minIndex < length; minIndex++)
5.
{
6.
if( list[minIndex].stateCity < list[index].stateCity)
7.
{
8.
//smallestIndex = minIndex;
9.
temp = list[minIndex];
10.
list [minIndex] = list[index];
11.
list[index] = temp;
12.

13.
} // end if
14.
} // end for loop with minIndex
15.
} // end for loop index

check it out it works