CODEWITHSUNDEEP
c++
Craig
Craig

Reputation: 183

Selection Sort Comparisons

I have to keep track of all comparisons in this selection sort, but when I do only 1 is returned for the value out of a list of 1000. I am not sure I implemented it correctly but I am sure I placed the comparison count correctly/. Typically a selection sort has a fixed amount of key comparisons but our instructor has forbidden the use of formulas to track them. I am curious why this output keeps returning:

comp = 1
swap = 1 

template <class elemType>
void selectionSort(elemType list[], int length)
{
    int loc, minIndex;
    int first; 
    int last, second;
    int swaps =0;
    int comp = 0;

    minIndex = first;
    for (loc = 0; loc < length; loc++)
    {
        comp+=1; 

        for(loc = first +1; loc<=last; loc++)
        {
            comp+=1;
            if(list[loc]<list[minIndex])
                minIndex=loc;
            comp+=1;
        }
        elemType temp;
        temp= list[first];
        list[first]= list[second];
        list[second] = temp;


        swaps+=1;
    }

    //  comp = (length *(length-1)/2);

    cout<<"swaps= "<<swaps<<endl;
    cout<<"comps= "<<comp<< endl;
}

Any thoughts are appreciated

Upvotes: 0

Views: 691

Answers (1)

Yogendra Singh
Yogendra Singh

Reputation: 34367

I guess your sorting itself is not working. You need to properly initialize last, first and second variables (specially the last) and then move(increment) them.

Since your last variable is defaulted with 0, its not performing the iterations because of loc<=last condition in the second for loop as you have desired. I think you need to initialize it as :

 last = length-1;

There is one more issue: In both the loops, you are using the same index variable i.e. loc. I think you need to use two different variables.

for (loc = 0; loc < length; loc++)
{
  comp+=1; 
   for(loc = first +1; loc<=last; loc++)
   {

Once you fix the logic so that it performs the full sorting, you will get the right count.

Upvotes: 1

Related Questions