Дан массив целых чисел. Отсортируйте массив методом быстрой сортировки.

Пример:

Input: array = [1,2,12,2,34,45,65,76,78,98,89]
Output: [1,2,2,12,34,45,65,76,78,89,98]

БЫСТРАЯ СОРТИРОВКА

Анализ сложности:

  • Временная сложность:

Лучшая временная сложность — O(logN)

Худшая временная сложность — O(n²)

  • Пространственная сложность: O(1).
    Дополнительное пространство не требуется, поэтому объемная сложность постоянна.

РЕШЕНИЕ :

function partition(arr, startIndex, endIndex) {
  const pivotVal = arr[endIndex]; 
  // the pivot element
  let index = startIndex;
  // begin iterate and swap
  for (let i = index; i < endIndex; i++) {
    if (arr[i] < pivotVal) {
      [arr[i], arr[index]] = [arr[index], arr[i]];
      index += 1;
    }
  }

  // move `pivotVal` to the middle index and return middle index
  [arr[index], arr[endIndex]] = [arr[endIndex], arr[index]];
  return index;
}

function quickSort(arr, startIndex, endIndex) {
  // Base case or terminating case
  if (startIndex >= endIndex) {
    return;
  }

  // Returns midIndex / pivot index
  let midIndex = partition(arr, startIndex, endIndex);

  // Recursively apply the same logic to the left and right subarrays
  quickSort(arr, startIndex, midIndex - 1);
  quickSort(arr, midIndex + 1, endIndex);
}

let arr = [-2, 4, 6, 3, 7, 2];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-2, 2, 3, 4, 6, 7]

Алгоритм:

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

  1. Массив делится на подмассивы путем выбора основного элемента (элемента, выбранного из массива).
  2. При делении массива опорный элемент должен располагаться таким образом, чтобы элементы, меньшие опорной точки, оставались с левой стороны, а элементы, превышающие опорную, находились справа от опорной точки.
  3. Левый и правый подмассивы также разделяются с использованием того же подхода. Этот процесс продолжается до тех пор, пока каждый подмассив не будет содержать один элемент.
  4. На данный момент элементы уже отсортированы. Наконец, элементы объединяются в отсортированный массив.

Сложность быстрой сортировки

1. Сложности со временем

  • Сложность в наихудшем случае [Big-O]: O(n2)
    Это происходит, когда выбранный опорный элемент является либо самым большим, либо самым маленьким элементом.
  • Это условие приводит к тому, что опорный элемент находится в крайнем конце отсортированного массива. Один подмассив всегда пуст, а другой подмассив содержит n - 1 элементов. Таким образом, быстрая сортировка вызывается только для этого подмассива.
  • Однако алгоритм быстрой сортировки имеет лучшую производительность для разбросанных опорных точек.
  • Сложность в лучшем случае [Big-omega]: O(n*log n)
    Это происходит, когда опорный элемент всегда является средним элементом или рядом со средним элементом.
  • Средняя сложность дела [Big-theta]: O(n*log n)
    Это происходит, когда вышеуказанные условия не выполняются.

2. космическая сложность

Сложность пространства для быстрой сортировки составляет O(log n).

Быстрая сортировка приложений

Алгоритм быстрой сортировки используется, когда

  • язык программирования хорош для рекурсии
  • сложность времени имеет значение
  • сложность пространства имеет значение