optimization of this algorithm?

[newer69]

void teest(int *prm1, int prm2)
{
  int m, n, tmp, flg;
  for(m=prm2-1; m>0; --m)
  {
    flg = 0;
    n=0;

    while(n<m)
    {
      if ( prm1[n] > prm1[n+1])
      {
        tmp = prm1[n];
        prm1[n] = prm1[n+1];
        prm1[n+1]= tmp;
        flg=1;
      }
      ++n;
    }

    if (!flg)
      break;
  }
}

as you can see there is already the optimization of the flag ..
Do you think that there is sth else that could make that algorithm (Bubble sort) better and faster? is there another better optimization?

thanks again :)

[Ivan Sidarau]

do you really need bubble sort?

[newer69]

I think so, because i was asked if there is a optimization of this algorithm so I dont think I can say this algorithm is about sorting and I can give the best algorithm of sorting as a optimization of this algorithm.. right?

[viliml]

maybe this, but im not sure if it's realy optimization, but it makes it a lot clearer:

void teest(int *prm1, int prm2)
{
  int m, n, flg=1;
  for(m=prm2-1; m>0 && flg; --m)
  {
    flg = 0;
    for (n=0; n<m; ++n)
    {
      if ( prm1[n] > prm1[n+1])
      {
        swap (prm1[n], prm1[n+1]);
        flg=1;
      }
    }
  }
}

[newer69]

this one is a lot clearer but it's not a optimization because you didnt actually change something :)

[rapidcoder]

The best optimisation of bubble sort is not using bubble sort.

[newer69]

hahaha yeah! that's right but do you think I can give it as an answer? :p

[viliml]

I found this by googleing:

One can still improve the above optimization a little bit. Let a[k] and a[k+1] be the last two numbers swapped in the i-th pass. Then surely the numbers a[k+1] to a[n] are already in their final positions. In the next pass we only need to consider the numbers a[1] to a[k], i.e., loop from 1 to k-1. The above optimization only lets us ignore the last number of each pass; this optimization can ignore potentially many numbers in each pass.

I tried to do somethig like that but I can't get it to work. You try it!
I laso found this:

A further improvement can be doing successive passes in opposite directions. This ensures that if one small number is at the end or one large number is at the beginning it reaches its final position in one pass.

, so try to implement that too!

[newer69]

actually the first one is already included in the algorithm by the first "for" where you can see that the m is continually reduced so we dont consider the last number of the array because as you said it's in its final position (it's the bigger number that's why it is located at the end of the array) ...
but I can add the case with the directions... if it goes right AND LEFT at the same pass then i think i will have optimization..

thank you very much

[viliml]

here, I even done the algorithm, in comparison to many other, "less optimized" versions, and here's the code:

void bubblesort5(int* a, int n)
{
     int bound = n-2;
     for (int i=1; i<=n; i++)
     {
         int newbound = 0;
         for (int j=i-1; j<bound; j++)
         {
             if (a[j] > a[j + 1])
             {
                swap( a[j], a[j + 1] );
                newbound = j - 1;
                }
             }
         bound = newbound;
         newbound = 0;
         for (int j=bound+3; j>=i; j--)
         {
             if (a[j-1] > a[j])
             {
                swap( a[j], a[j-1] );
                if (!newbound) newbound = j - 1;
                }
             }
         bound = newbound;
         }
     }

That's the most optimized it can get!
But, sort() it stimm hundreds of times faster(literarly!)!
I tried the worst-case scenario(reverse) for 50000 items, and the biult-in sort() was 10 000 (yup, ten thousand!) times faster!!!

[viliml]

and, by the way, the first optimisation IS NOT included by your first for! that just excludes the last item, but this excludes the whole last swap, wich could be before the last item! It would be like this:

void bubblesort4(int* prm1, int prm2)
{
    int bound = prm2-2;
    for (int m=1; m<=prm2; m++)
    {
        int newbound = 0;
        for (int n=0; n<=bound; n++)
        {
            if (prm1[n] > prm1[n + 1])
            {
               swap( prm1[n], prm1[n + 1] );
               newbound = n - 1;
               }
            }
        bound = newbound;
        }
    }

see the difference?