0

I am trying to implement an insertion sort algorithm for pset3, but I believe the problem lies in how I swap the values at the end of the code.

Any clues on how to fix this?

void sort(int values[], int n)
{
    // TODO: implement an O(n^2) sorting algorithm
    for (int i = 1; i < (n - 1); i++)
    {
        int min = i;
        for (int j = i + 1; j < n ; j++)    
        {
            if (values [j] < values [min])
            {
                min = j;
            }
            if (min != i)
            {
                int swap = values [j];
                values [j] =  values [min];
                values [min] = swap;
            }
        }
    }
    //printing for testing purposes
    for (int k = 0; k < 10; k++) {
    printf("%i \n", values[k]);
    }


    return;
}
1

The above code is partially correct. Although the logic seems to be appropriate, it is not efficient. All you have to do is set the value of i as minimum every time you enter the 'i' loop, and then start with j loop starting with j=i+1 till the end. Every time you find an element smaller than the element at index 'min', update the 'min' variable to an index j, i.e, min=j. This means the index of the minimum element so far is j,which is held in min variable. For the swapping process, all you need to do is swap the elements at index 'i' and index 'min' once (just after the j loop and inside the i loop). This will help in improving the efficiency of the code. Hope this helps. :)

The modified code will look similar to this:

void sort(int values[], int n)
{
  for (int i = 0; i < (n - 1); i++)
  {
    int min = i;
    for (int j = i + 1; j < n ; j++)    
    {
        if (values [j] < values [min])
            min = j;
    }

     //swap min and i elements 
            int swap = values [i];
            values [i] =  values [min];
            values [min] = swap;
}

//printing for testing purposes
for (int k = 0; k < n; k++) {
printf("%i \n", values[k]);
}

return;
}
0

The swap mechanism is correct, but all it is doing is swapping the minimum value with itself. It sets min=j and then swaps values[min] with values[j].

The logic of the sort is flawed. As it is, if you were to swap values[min] with values[i], it would work, but efficiency would be impacted. Given the way it is encoded, it will perform the swap every time it finds a value less than values[i]. The worst case would be if the list were already in a descending sort. (You can work it out on paper, or just add a counter to see how many times it performs a swap.) This happens because the swap code is inside the inner for loop.

If, however, the code were to go all the way through the inner loop to identify the smallest element, and only do one swap following the inner loop, but inside the outer loop, then efficiency is substantially improved.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .