0

The pset 3 short on bubble sorting mentions that we should:

1) set a swap counter to a non-zero value.

2) Define the loop

3) In each loop iteration reset the counter to 0 and increase the swap counter if a swap of two array elements occurs.

4) after the loop if the swap counter is 0, terminate the sort

I understand the reason for this which is to stop the recursive bubble sort early if the data is sorted rather than running through up to n^2 loops.

However in my code I declare my swap counter and define it to be 0 rather than a non-zero value and it still seems to work. I don't find I need a non-negative value:

void sort(int array[], int size)
{
if (size <= 1)
    return;

int swapCounter = 0;    
for(int j = 0; j < size - 1; j++)
{

    if (array[j] > array[j + 1])
    {
        int swap = array[j + 1];
        array[j + 1] = array[j];
        array[j] = swap;
        swapCounter++;
    }
}

if (swapCounter > 0)
    sort(array, size - 1);
}

Is there something I am missing?

Do I need to set swapCounter to a non-zero integer before I define my for loop?

Or is this only neccessary when using do...while loops?

1

In the pseudo-code mentioned in the short swapcounter is used as a sentinel to detect whether swapping of two elements of the array has taken place in the current passing of the array. If the swapcounter is zero at the end of a particular iteration over the array elements this means that the array is already sorted.

Your implementation works in a similar way. You are checking if the swapcounter > 0 and then recursively calling the sort function with updated parameters, whereas the pseudo-code is taking swapcounter != 0 as a condition to continue the sorting process.

Since there is no way that the swapcounter could ever become negative so both the conditions ultimately lead to the same result. It has nothing to do with the usage of do..while loop.

6
  • Thanks, that does clarify the picture somewhat. However I'm still not clear why they even needed to define the swapcounter as a non-zero character before the loop. Since its value only gets checked once the loop has iterated. So why not miss out that declaration and the part where you need to set it to 0 as the first step in the for loop. Instead why not just declare it as 0 as the first step of the for loop?
    – Souper
    Feb 4 '17 at 19:44
  • Firstly if you declare the swapcounter inside the for loop and set it to zero you would not be able to use it outside the scope of the for loop i.e. in the if condition you have after your loop.
    – N. Tiwari
    Feb 4 '17 at 19:53
  • Also, setting it to -1 and then setting it 0 at the start of every iteration over the array ensures that the value of swapcounter is always zero if there is no swap taking place and non zero otherwise. However, as i have mentioned in the answer what you have implemented is not much different as your sentinel is doing exactly what it is supposed to i.e. indicate when there are no swaps even after iterating over the whole array.
    – N. Tiwari
    Feb 4 '17 at 19:58
  • Great, thanks again. I'm a little annoyed I didn't workout that the scope of swapcounter would be limited if declared in the for loop, and thank you for pointing that out. However I'm sorry for labouring the point but I don't understand why they say in the video that initial declaration of swapcounter HAS to be a non-zero value. Seeing as though value is not checked until the loop is finished wouldn't declaring it as 0 before the loop and then not having to reset it be just as valid? If any swaps have occurred the swapcounter != 0 condition will still be run
    – Souper
    Feb 4 '17 at 20:11
  • Yes, it would definitely be just as valid. The algorithm in the video uses the condition swapcounter != 0 in the loop and not swapcounter > 0 , this is the only reason for that extra step.
    – N. Tiwari
    Feb 4 '17 at 20:21

You must log in to answer this question.

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