Bubble sort functionality

[kikelinus]

I've been reading some stuff about the bubble sort algorithm, and I have a question. Lets says for example you have 5 elements stored in an array: [7, 3, 8, 9, 4]. If you use the bubble sort algorithm, then it means that you are going to loop a total of 4 times (number of elements - 1): lets call this "loop 1", and inside this loop, there will be another loop ("loop 2"), which is in charge of detecting if the current element in the array is bigger then the one followed by it, and if it is, switch them.

I did the same process that the algorithm does on a piece of paper, and I got to the final solution (all elements sorted) the second time loop 1 was executed. What I mean to say is that all numbers were sorted, before the main loop had finished (before it looped through all 5 elements).

My question is: does the algorithm continue to excecute itself until the whole loop has finished? If so, then is it not wasting time-memory-resources, etc...??

Thanks.

[jim mcnamara]

No. You clear a flag and exit early if the flag is still clear:

  for(i=0;i<total-1; i++){
         flag = 0;
         for (j=0;j<total-1;j++){
               if (array[j]>array[j+]) {
                      swap(array[j],array[j+1]);
                       flag = 1;
               }
         }
          if (flag==0) break;  // exit early  
  }

[kikelinus]

Ohhh....I get it, when it has no more swapping to do, it stops. Thanks

[CornedBee]

but bubble sort is still slow...
Simply the fact that it has two loops - you might consult keda about that, he has a song to sing

[imj75]

If you want an algorithm faster than bubble sort you might do well to look at mergesort using median of three partioning. It is really tight with a Bih-Oh (O)N factor much better than Bubble sort. Other alternatives could be Quicksort, Shellsort and Insertionsort