Сортировка – это фундаментальная операция в информатике, которая предполагает расположение элементов в определенном порядке. Dart, популярный язык программирования, предоставляет несколько алгоритмов сортировки для эффективной организации данных. В этой статье блога мы рассмотрим различные методы сортировки в Dart, в том числе знаменитую пузырьковую сортировку, а также другие часто используемые алгоритмы, такие как сортировка выбором, сортировка вставками, сортировка слиянием, быстрая сортировка и пирамидальная сортировка.

1. Пузырьковая сортировка.
   Пузырьковая сортировка – это простой алгоритм сортировки на основе сравнения. Он неоднократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Этот процесс повторяется до тех пор, пока не будет отсортирован весь список.

void bubbleSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

1. Сортировка выбором:
   Сортировка выбором делит входной список на две части: отсортированную часть слева и неотсортированную часть справа. Он неоднократно выбирает самый маленький элемент из неотсортированной части и заменяет его самым левым несортированным элементом.

void selectionSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }
}

1. Сортировка вставками.
   Сортировка вставками создает окончательный отсортированный массив по одному элементу за раз. Он берет один элемент из входных данных и вставляет его в правильную позицию в уже отсортированной части массива.

void insertionSort(List<int> arr) {
  int n = arr.length;
  for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

1. Сортировка слиянием.
   Сортировка слиянием – это алгоритм «разделяй и властвуй», который делит входной список на более мелкие подсписки, рекурсивно сортирует их, а затем объединяет отсортированные подсписки для создания окончательного отсортированного списка.

void mergeSort(List<int> arr) {
  if (arr.length <= 1) {
    return;
  }
  int mid = arr.length ~/ 2;
  List<int> left = arr.sublist(0, mid);
  List<int> right = arr.sublist(mid);
  mergeSort(left);
  mergeSort(right);
  merge(arr, left, right);
}
void merge(List<int> arr, List<int> left, List<int> right) {
  int i = 0, j = 0, k = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
    }
  }
  while (i < left.length) {
    arr[k++] = left[i++];
  }
  while (j < right.length) {
    arr[k++] = right[j++];
  }
}

1. Быстрая сортировка.
   Быстрая сортировка – это еще один алгоритм “разделяй и властвуй”, который выбирает опорный элемент, разбивает массив вокруг опорного элемента и рекурсивно сортирует подмассивы.

void quickSort(List<int> arr, int low, int high) {
  if (low < high) {
    int pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
}
int partition(List<int> arr, int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  for (int j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  int temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;
  return i + 1;
}

1. Кучная сортировка.
   Кучная сортировка использует свойства двоичной кучи для сортировки элементов. Сначала он создает максимальную кучу из входного массива, а затем повторно извлекает максимальный элемент из кучи, в результате чего получается отсортированный массив.

void heapSort(List<int> arr) {
  int n = arr.length;
  for (int i = n ~/ 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  for (int i = n - 1; i >= 0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}
void heapify(List<int> arr, int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest != i) {
    int temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;
    heapify(arr, n, largest);
  }
}

В этой статье блога мы рассмотрели несколько алгоритмов сортировки, реализованных в Dart. Мы рассмотрели пузырьковую сортировку, сортировку выбором, сортировку вставками, сортировку слиянием, быструю сортировку и пирамидальную сортировку. Каждый алгоритм имеет свои сильные и слабые стороны, и выбор того, какой из них использовать, зависит от конкретных требований и ограничений решаемой задачи. Понимая эти методы сортировки, вы сможете применить наиболее подходящий алгоритм для эффективной сортировки данных в ваших программах Dart.