Selection sort doesn't count correctly

[TJW]

I tried to compare the bubble and selection sort, so I set the counters to count the times each sort iterated to find the value. But the results seemed incorrect, especially the selection sort. Do I need to amend the location of the counter or the algorithm is wrong? Thank you!

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int bubbleSort(int [], int); 
int selectionSort(int [], int);
int main()
{
	const int SIZE=20;
	int number=0, array_bubble[SIZE], array_selection[SIZE];
	unsigned seed;
	seed=time(0);
	srand(seed);
	int bubbleCount=0, selectionCount=0;
	cout << "The first array: " << endl;
	for(int x=0; x<SIZE; x++)
	{
		number=rand()%100+1;
		array_bubble[x]=number;
		cout << array_bubble[x]<< " ";
	}
	for(int x=0; x<SIZE; x++)
	{
		array_selection[x]=array_bubble[x];
	}
	cout << endl;
	bubbleCount=bubbleSort(array_bubble, SIZE);//Function call;
	cout << "The number of exchanges made by the bubble sort is: " << bubbleCount << endl <<endl;
	cout << "The second array: " << endl;
	for(int x=0; x<SIZE; x++)
	{
		cout << array_selection[x] << " ";
	}
	cout << endl;
	selectionCount=selectionSort(array_selection, SIZE);//Function call;
	cout << "The number of exchanges made by the selection sort is: " << selectionCount << endl;
	return 0;
}
int bubbleSort(int array[], int size)
{
	int temp, exchangeCount=0;	
	bool madeSwap;
	do
	{
		madeSwap=false;
		for(int count=0; count<(size-1); count++)
		{
			if(array[count]>array[count+1])
			{
				temp=array[count];
				array[count]=array[count+1];
				array[count+1]=temp;
				madeSwap=true;
				exchangeCount++;
			}
		}
	}while(madeSwap);
	return exchangeCount;	
}
int selectionSort(int array[], int size)
{
	int startScan, minIndex, minValue, exchangeCount=0;
	for(startScan=0; startScan<(size-1); startScan++)
	{
		minIndex=startScan;
		minValue=array[startScan];
		for(int index=startScan+1; index<size; index++)
		{
			if(array[index]<minValue)
			{
				minValue=array[index];
				minIndex=index;
				exchangeCount++;
			}
		}
		array[minIndex]=array[startScan];
		array[startScan]=minValue;
	}
	return exchangeCount;
}

[jonnin]

selection sort is a little smarter than bubble. it will do less work.
check to see if it is sorted after selection sort (so you know it does not have a bug). If it is sorted, its probably telling you the right answer.

comparisons have a price too. counting those can also be enlightening.

[Duthomhas]

Both his sorts are correct; he is complaining because the number of exchanges reported by the selection sort don’t meet his expectations.

You put the exchangeCount++ in with the “found a smaller value” part. There is no exchange happening there. Move it down a couple of lines. :O)

[TJW]

Thank you, Duthomhas!
I amended it, but the number is still not correct. It always prints the number as (the size of the array - 1). ex. if the size of the array is 20, it prints 19. But I traced different tests manually, the selection sort's exchange times should have been less, not just the size-1.
The amended codes:
int selectionSort(int array[], int size)
{
int startScan, minIndex, minValue, exchangeCount=0;
for(startScan=0; startScan<(size-1); startScan++)
{
minIndex=startScan;
minValue=array[startScan];
for(int index=startScan+1; index<size; index++)
{
if(array[index]<minValue)
{
minValue=array[index];
minIndex=index;
}
}
array[minIndex]=array[startScan];
array[startScan]=minValue;
exchangeCount++;
}
return exchangeCount;
}

[Duthomhas]

No, the swap on 77..78 is unconditional. You should have SIZE-1 swaps.

[TJW]

I see. So I had to make it conditional to count the correct swaps.
Here's what I did to make it conditional: (from 61)
int selectionSort(int array[], int size)
{
int startScan, minIndex, minValue, exchangeCount=0;
bool madeSwap=false;
for(startScan=0; startScan<(size-1); startScan++)
{
if(madeSwap)
{
exchangeCount++;
}
minIndex=startScan;
minValue=array[startScan];
for(int index=startScan+1; index<size; index++)
{
if(array[index]<minValue)
{
minValue=array[index];
minIndex=index;
madeSwap=true;
}
}
array[minIndex]=array[startScan];
array[startScan]=minValue;
}
return exchangeCount;
}

[JLBorges]

#include <iostream>

// return the position of the smallest item at or after start_pos
int pos_smallest_item( const int array[], int size, int start_pos )
{
    int pos_smallest = start_pos ;
    for( int i = start_pos+1 ; i < size ; ++i )
        if( array[i] < array[pos_smallest] ) pos_smallest = i ;
    return pos_smallest ;
}

void swap( int array[], int i, int j ) // swap array[i] and array[j]
{
    const int temp = array[i] ;
    array[i] = array[j] ;
    array[j] = temp ;
}

int selection_sort( int array[], int size ) // return number of swaps
{
    int num_swaps = 0 ;

    for( int i = 0 ; i < size-1 ; ++i )
    {
        const int pos_smallest = pos_smallest_item( array, size, i ) ;

        if( array[pos_smallest] != array[i] ) // swap only if required
        {
            swap( array, i, pos_smallest ) ;
            ++num_swaps ;
        }
    }

    return num_swaps ;
}

int main()
{
    int arr[] { 12, 12, 12, 18, 18, 14, 14, 12, 14, 14, 12, 18, 17, 15, 12, 18 } ;
    const int array_size = sizeof(arr)/sizeof( arr[0] ) ;

    const int nswaps = selection_sort( arr, array_size ) ;

    for( int v : arr ) std::cout << v << ' ' ;
    std::cout << "\n#items: " << array_size << "  #swaps: " << nswaps << '\n' ; ;
}

http://coliru.stacked-crooked.com/a/bb2346118e69d8ba