How to extract items from nested lists in a dart-CodePudding

I was trying to write a recursive quicksort algorithm. The problem is that it returns elements in a set of nested arrays

void main(List<String> arguments) {
  List myList = [2, 4, 9, 7, 1, 12];
  print(quickSort(myList));
}

List quickSort(var arr){
  if (arr.length < 2){
    return arr;
  } else {
    int pivot = arr[0];
    List less = [];
    List greater = [];
    arr.removeAt(0);
    arr.forEach((element) {
      if (element > pivot){
        greater.add(element);
      } else {
        less.add(element);
      }
    });
    return [quickSort(less), pivot, quickSort(greater)];
  }
}

Here is the result of the algorithm [[1], 2, [[], 4, [[7], 9, [12]]]]

I want to get the data in this format: [1, 2, 4, 7, 9, 12]

CodePudding user response：

There are one problem which are the main reason for your problems. But there are also multiple related problems when is the reason why you did not discover the main problem.

The main problem is that you are inserting lists instead of the content of the returned lists in:

return [quickSort(less), pivot, quickSort(greater)];

What you want here is to insert all elements from the returned list from of e.g. quickSort(less). Instead, you are inserting it as a List itself which makes your import like you are seeing it.

To fix this, you should use ... to tell Dart that it should iterate over the list and insert all the elements. So something like this:

return [...quickSort(less), pivot, ...quickSort(greater)];

The reason why you got this problem is because of missing types in general in your code. You should, in general, never just write List since that means List<dynamic> in Dart. dynamic means whatever type so the List are allowed to contain a mix of types. This is bad since that also means extracting data from these List are also going to be dynamic and Dart can therefore not help us preventing type issues.

I have rewritten your code to make it more type safe here:

void main(List<String> arguments) {
  List<int> myList = [2, 4, 9, 7, 1, 12];
  print(quickSort(myList));
}

List<int> quickSort(List<int> arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    int pivot = arr[0];
    List<int> less = [];
    List<int> greater = [];
    arr.removeAt(0);

    for (final element in arr) {
      if (element > pivot) {
        greater.add(element);
      } else {
        less.add(element);
      }
    }

    return [...quickSort(less), pivot, ...quickSort(greater)];
  }
}

Also, I would suggest not using .forEach() but instead use normal for-each loops as I have done.

And at last, this would also be as type safe since we are allowed to use var/final to tell Dart that it should automatically figure out the correct type based on context. You should still, however, specify types when it comes to method signatures:

void main(List<String> arguments) {
  final myList = [2, 4, 9, 7, 1, 12];
  print(quickSort(myList));
}

List<int> quickSort(List<int> arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    final pivot = arr[0];
    final less = <int>[];
    final greater = <int>[];
    arr.removeAt(0);

    for (final element in arr) {
      if (element > pivot) {
        greater.add(element);
      } else {
        less.add(element);
      }
    }

    return [...quickSort(less), pivot, ...quickSort(greater)];
  }
}

So the point is really that if you are ever going to specify types in Dart, then please write the full type since just List is much worse than final/var in most situations. :)