0

My first question on this board and I really need some help in order to figure out what could be wrong with my code. I decided to go with a a selection sort but as soon as I run ./generate 2 2 in order to check if it works i get this unsorted list.

38906
31103

I implemented the code as follows:

for (int i = 0; i < n; i++)
{
    int min = i;

    for (int j = i+1; j < n; j++)
    {
       if (values[min]>values[j])
       {
            min = j;
             int temp = values[min];
             values [min] = values [i];
             values [i] = temp;
       }

    }

}


return ;

It would be great if somebody could point me in the right direction. Am I actually checking my code in the right way. I couldn't figure out how to use gdb for debugging since there is no ruining file just the helpers.c.

Thank you in advance!

1

The pseudocode for selection sort is as follows

for int i = 0 to i < n - 1, increment i by 1
{
    declare an int named min and set it to i

    for int j = i + 1 to j < n, increment j by 1
    {
        if values[min] > values[j]
        {
            set min to j
        }
    }

    swap values[i] and values[min]
}

You did most of it correctly though! However, you shouldn't be swapping the two values every time values[min] > values[j] because that would mess things up. Consider the following example

array: 5, 4, 3, 2, 1
pick the 5
walkthrough the list {4, 3, 2, 1} and pick the least element (i.e., 1)
swap it with the 5
array: 1, 4, 3, 2, 5
...

This way, you guarantee that after the first iteration of the outer loop, the least element in the array will be positioned at index 0.

What you're doing is something like

array: 5, 4, 3, 2, 1
set i to 0
set min to i
set j to 1
walkthrough the list {4, 3, 2, 1}
if values[min] > values[j]
{
    set min to j
    swap them
}

array: 4, 5, 3, 2, 1
i is still 0
min = 1
j is now 2
if (values[min] > values[j])
{
    set min to j
    swap them
}

array: 4, 3, 5, 2, 1
...

array: 4, 3, 2, 1, 5
then i = 1

and you'll never get back to values[0] (which is 4) again even though it's not in it's correct position yet.

| improve this answer | |
  • Thank Kareem that is a good point. But what so ever even when changing this part and adding the swap in the first for() loop it is still not swapping my array. I'm starting to thing that I can't test it with the ./generate. How are you checking that this part of the code is working? – user1681 Jul 4 '14 at 19:25
  • @user1681 I use gdb to debug my programs. You can either use it or update your question with your new code to let us help you identify the bug! – Kareem Jul 4 '14 at 20:12
  • And again thank you!! One more thing... It worked all the time but in order to see the sorting you should add pintf after the swap block in order to see the sorted array. ./generate is not swapping the list. ./find is displaying the final sorted array. – user1681 Jul 4 '14 at 20:14
  • @user1681 generate only generates a number of random values specified by the command-line argument passed to it. find, on the other hand, is the one that has the sort() function. When you pipe the output of generate as the input to find, the random values generated by generate are stored in an array declared in find. This array, by its turn, is passed to sort() to get it sorted. You then may print it out to see the final result! – Kareem Jul 4 '14 at 20:26

You must log in to answer this question.

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