optimized bubbleSort in dart-CodePudding

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 ?

CodePudding user response：

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 ...