CODEWITHSUNDEEP
c++functionbubble-sort
soniccool
soniccool

Reputation: 6058

Curious on bubblesort method

I created a simple bubblesorting script here that takes in arrays and sorts them, This is only a snippet of the code. But its the code that sorts it. I want to make it so Instead of making nine or so comparisons for example on every pass, to modify the bubble sort to make eight or one less comparisons on the second pass, seven on the third pass, and so on. I am totally lost how to implement that. What would be the best idea for that?

        int bubbleSortArray(int array[])
        {
            for(int i=0;i<10;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(array[i]>array[j])
                    {
                        swap(array[i], array[j]);
                        amountOfSwaps += 1;
                    }
                }
            }

        printArray(array);
        return amountOfSwaps;

        }


       void swap(int & value1, int & value2)
       {
              int temp=value1; 
              value1=value2;
              value2=temp;
       }

Upvotes: 2

Views: 333

Answers (3)

greatwolf
greatwolf

Reputation: 20858

Note that a distinquishing property of a bubblesort is that it checks whether a swap was performed at all for each pass. If it didn't swap then everything is in order and you can break early. Something like this:

int bubbleSort(int *arry, size_t size)
{
  bool swapped;
  size_t upper_bound = size;
  int amountOfSwaps = 0;

  do
  {
    swapped = false;
    for(int i = 1; i < upper_bound; ++i)
    {
      if(arry[i] < arry[i - 1])
      {
        swap(arry[i], arry[i - 1]);
        swapped = true;
        ++amountOfSwaps;
      }
    }
    --upper_bound;
  }while(swapped);

  return amountOfSwaps;
}

Upvotes: 0

Andrew Dunaway
Andrew Dunaway

Reputation: 1226

Your code is already doing what you are looking for. Since j iterates to the length i, it grows by one larger each time. I think you are being confused because your code is actually implementing it backwards from your English in the question ;)

Here is a sample array, and the modifications that would be made at each iteration. The parenthesis denote what part of the array is being checked in each iteration:

(7)5 3 8 6 9 4 2 0 1
(7 5)3 8 6 9 4 2 0 1
(7 5 3)8 6 9 4 2 0 1
(8 7 5 3)6 9 4 2 0 1
(8 7 6 5 3)9 4 2 0 1
(9 8 7 6 5 3)4 2 0 1
(9 8 7 6 5 4 3)2 0 1
(9 8 7 6 5 4 3 2)0 1
(9 8 7 6 5 4 3 2 0)1
(9 8 7 6 5 4 3 2 1 0)

As you can see the first time through nothing is actually done, nor ever will be because you are comparing one element against itself. The second time through you are now comparing two elements, then three, then so on.

To make your code start with comparing them all, and then doing one less each time (as your question states) you would modify you loop to the following (note j<10-i):

    for(int i=0;i<10;i++)
    {
        for(int j=0;j<10-i;j++)
        {

Either way it amounts to the same thing and will work in the end. You could further skip the first comparison against itself by setting i = 1:

for(int i=1;i<10;i++)
    {
        for(int j=0;j<10-i;j++)
        {

This will leave off the first comparison above, which is the other optimization you were looking for.

Upvotes: 1

mergeconflict
mergeconflict

Reputation: 8276

I think you've got your loop on j a bit backwards. I think you need something like:

for (int i = 0; i < 10; i++) {
    for (int j = 1; j < 10 - i; j++) {
        // ...
    }
}

Upvotes: 1

Related Questions