Efficient Sorting Algorithms in Dart: Comparing Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort

Sorting algorithms are fundamental tools in computer science, allowing us to arrange elements in a specific order efficiently. In this article, we'll explore five different sorting algorithms implemented in Dart: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort.

1. Bubble Sort: A Simple Comparison-Based Algorithm
2. Selection Sort: Building the Sorted Portion Gradually
3. Insertion Sort: Building the Final Sorted List One Element at a Time
4. Merge Sort: Divide and Conquer
5. Quick Sort: Another Divide and Conquer Approach

1. Bubble Sort: A Simple Comparison-Based Algorithm

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted. Despite its simplicity, Bubble Sort has a worst-case time complexity of O(n^2), making it inefficient for larger datasets.

void main() {
  final arr = [9, 3, 4, 10, 5, 8, 11, 45];
   print("Before Sorting => $arr");
   bubbleSort(arr);
   print("After Sorting => $arr");
   print(sorted);
  }
  
  void bubbleSort<E extends Comparable<dynamic>>(List<E> list) {
    for (int end = list.length - 1; end > 0; end--) {
      bool isswaped = false; 
      for (int current = 0; current < end; current++) {
        if (list[current].compareTo(list[current + 1]) > 0) {
          list.swap(current, current + 1);
          isswaped = true;
        }
      }
      if (!isswaped) return;
    }
  }        

2. Selection Sort: Building the Sorted Portion Gradually

Selection Sort is another straightforward algorithm that repeatedly selects the minimum element from the unsorted part of the list and places it at the beginning. It gradually builds the sorted portion of the list. Like Bubble Sort, Selection Sort also has a worst-case time complexity of O(n^2).

void selectionSort<E extends Comparable<dynamic>>(List<E> list) {
  for (int start = 0; start < list.length - 1; start++) {
    int lowest = start;
    for (int next = start + 1; next < list.length; next++) {
      if (list[next].compareTo(list[lowest]) < 0) {
        lowest = next;
      }
    }
    if (lowest != start) {
      list.swap(lowest, start);
    }
  }
}        

3. Insertion Sort: Building the Final Sorted List One Element at a Time

Insertion Sort constructs the final sorted list by taking each element and inserting it into the correct position in the already sorted part of the list. It performs well for small datasets and partially sorted lists, but it also has a worst-case time complexity of O(n^2).

void insertionSort<E extends Comparable<dynamic>>(List<E> list) {
  for (int current = 1; current < list.length; current++) {
    for (int shifting = current; shifting > 0; shifting--) {
      if (list[current].compareTo(list[shifting - 1]) < 0) {
        list.swap(current, shifting - 1);
      } else {
        break;
      }
    }
  }
}         

4. Merge Sort: Divide and Conquer

Merge Sort is a more efficient algorithm based on the divide-and-conquer approach. It divides the list into halves, sorts them separately, and then merges the sorted halves to obtain the final sorted list. Merge Sort has a time complexity of O(n log n), making it more suitable for larger datasets.

List<E> _merge<E extends Comparable<dynamic>>(List<E> listA, List<E> listB) {
  int indexA = 0;
  int indexB = 0;
  final result = <E>[];
  while (indexA < listA.length && indexB < listB.length) {
    final valueA = listA[indexA];
    final valueB = listB[indexB];
    if (valueA.compareTo(valueB) < 0) {
      result.add(valueA);
      indexA++;
    } else if (valueA.compareTo(valueB) > 0) {
      result.add(valueB);
      indexB++;
    } else {
      result.add(valueA);
      result.add(valueB);
      indexA++;
      indexB++;
    }
  }
  if (indexA < listA.length) {
    result.addAll(listA.getRange(indexA, listA.length));
  }
  if (indexB < listB.length) {
    result.addAll(listB.getRange(indexB, listB.length));
  }
  return result;
}

List<E> mergeSort<E extends Comparable<dynamic>>(List<E> list) {
  if (list.length < 2) return list;
  int mid = list.length ~/ 2;
  final left = mergeSort(list.sublist(0, mid));
  final right = mergeSort(list.sublist(mid));
  return _merge(left, right);
}        

5. Quick Sort: Another Divide and Conquer Approach

Quick Sort selects a pivot element and partitions the list into two sub-lists around the pivot. The two sub-lists are then recursively sorted. On average, Quick Sort has a time complexity of O(n log n), making it efficient for most cases. However, it can degrade to O(n^2) in the worst-case scenario.

List<E> quickSort<E extends Comparable<dynamic>>(List<E> list) {
  if (list.length < 2) return list;
  final pivot = list[0];
  final lessThanPivotList = list.where((val) => val.compareTo(pivot) < 0);
  final equlaToPivotList = list.where((val) => val.compareTo(pivot) == 0);
  final greaterThanPivotList = list.where((val) => val.compareTo(pivot) > 0);
  return [
    ...quickSort(lessThanPivotList.toList()),
    ...equlaToPivotList.toList(),
    ...quickSort(greaterThanPivotList.toList()),
  ];
}         

When choosing a sorting algorithm, it's essential to consider the size of the dataset and the specific characteristics of the data. For smaller datasets or cases where data is mostly pre-sorted, simple algorithms like Bubble Sort and Selection Sort may be sufficient. However, for larger datasets, Merge Sort and Quick Sort provide better performance.

In conclusion, sorting algorithms are crucial tools for developers when dealing with large amounts of data. Understanding the strengths and weaknesses of different algorithms allows developers to make informed choices and optimize the performance of their applications. Dart's flexibility enables the implementation and experimentation with these sorting algorithms, providing a deeper understanding of algorithmic concepts and their real-world applications.

Thank You for reading this article.