optimized bubbleSort in dart

Question

so i have a task that made me do a bubblesort and I did this :

    bubbleSort(List<int> list) {
  for (int i = 0; i < list.length; i++) {
    for (int j = 0; j < list.length - 1; j++) {
      if (list[j] > list[j + 1]) {
        int num = list[j];
        list[j] = list[j + 1];
        list[j + 1] = num;
      }
    }
  }
  print(list);
}

void main() {
  List<int> list = [2, 5, 3, 15, 20, 5, 2, 7, 9];
  bubbleSort(list);
}

and now it want me to make an optimized bubbleSort how is that in Dart ?

What do you mean by "optimize"? If you change, well, almost anything, it's no longer bubblesort. (Which is a good thing, because bubblesort isn't *great*.) — lrn, Oct 09 '22 at 17:04
Maybe his professor means "compile it with -O2 on the command line" :) — Randal Schwartz, Oct 09 '22 at 18:25

Spektre · Accepted Answer · 2022-10-10T07:02:34.907

1

If by optimized you mean it stops on ordered array than:

bubbleSort(List<int> list) { int i,j,e;
  for (e=1,i=0; (i < list.length)&&(e); i++) {
    for (e=0,j=0; j < list.length - 1; j++) {
      if (list[j] > list[j + 1]) { e=1;
        int num = list[j];
        list[j] = list[j + 1];
        list[j + 1] = num;
      }
    }
  }
  print(list);
}

void main() {
  List<int> list = [2, 5, 3, 15, 20, 5, 2, 7, 9];
  bubbleSort(list);
}

I simply added e which is set on any swap which means once you iterate inner loop without swap the sorting stops..

This is still O(n^2) however much much faster on semi sorted data (in same direction)...

Another option to optimize this is to detect how much the array is sorted and if in asc or desc order. Once reverse order (in respect to used sort) is detected reverse the array before using bubble...

for the detection you can do something like this:

for (e=0,i=1;i<list.length;i++) 
 if (list[i]>list[i-1]) e++; 
  else e--;

now the more positive e is the more asc sorted the array is and the more negative the more desc sorted the array is...

so you can add for example (for asc sorting):

if (e<-list.length/4) // for asc sorting
//if (e>+list.length/4) // for desc sorting
 for (i=0,j=list.length-1;i<j;i++,j--) 
    {
    int num = list[i];
    list[i] = list[j];
    list[j] = num;
    }

and only now use bubble ...

edited Oct 10 '22 at 07:02

answered Oct 10 '22 at 06:37

Spektre

49,595
11
110
380

IMO, the variable `e` should be declared inside the main loop. – Oct 10 '22 at 06:49
@YvesDaoust I do not code in dart so I was afraid of some kind of syntax error ... feel free to repair – Spektre Oct 10 '22 at 06:50
To the OP: in the worst case, this version (first in the post) is slower because it is doing an extra test. – Oct 10 '22 at 06:51
But you know how to declare inside a block... In any case, the initialization e=1 seems superfluous. – Oct 10 '22 at 06:52
@YvesDaoust My experience is that the first version is on average much faster can even beat quick sort on small arrays ... its slower only on almost sorted array in reverse direction which is dealt with the reversal. The extra if is not inside inner loop so its not a big deal as there is brunch already anyway. Yes you right the `e=1` init is just to feel safer and to avoid compiler warning... – Spektre Oct 10 '22 at 06:53
however the quick sort wins with increasing `n` pretty quickly for example see [time comparison for `n=1024` data size](https://stackoverflow.com/a/36932606/2521214) – Spektre Oct 10 '22 at 06:59
I don't deny that. But in the worst case, this variant is *always* slower than that of the OP. You have a similar phenomenon with binary search with a test for early termination in case the key is found: if the key is not there, this variant is slower. – Oct 10 '22 at 07:58

optimized bubbleSort in dart

1 Answers1