Быстрая сортировка — это алгоритм сортировки для сортировки списка несортированных элементов в массиве, это алгоритмы разделяй и властвуй (в основном разделяя проблему на подзадачи, пока она не станет легко решить), который работает путем выбора опорного элемента из массива и разделения элементов на два подмассива, один с элементами, которые меньше, чем опорный, а другой с элементами, которые больше опорной точки.

Вы можете выбрать основу:

  • Начальный элемент массива
  • Последний элемент массива
  • Средний элемент массива
  • Медиана массива

Для этого блога мы будем использовать подход последнего элемента.

ВРЕМЕННАЯ СЛОЖНОСТЬ:быстрая сортировка имеет временную сложность O(n*n),со средней сложностью O(nlog(n)).

Код Sudo:

/**
* Checking if the array is empty or not, if it is empty then return
* Selecting a pivot element, in our case it is the last element in the array
* Initialise an empty left array variable(to store less values) and right array variable(to store greater values).
* Initializing a loop to the length-1 of the array, so that we can compare element if they are less than or greater than the pivot
* Inside the loop, check if current value is less or greater than pivot, if less than put in left array else in right array.
* So now, we have left array(that has less values), we have pivot that is the middle (as it is greater than less values and less than greater values) and a right array(that has greater values).
* We need to use the recursion to call the function , until we reach empty array and return the output
*/

Перейдем к коду:

const quickSort = (unSortedArray) => {
// checking if array is not empty
if (!unSortedArray.length) return [];
// selecting the pivit from the array
let pivotElement = unSortedArray[unSortedArray.length - 1];
// array to store lesser values
let leftArray = [];
// array to store greater values
let rightArray = [];
//iterating through length-2 elements
for (let i = 0; i < unSortedArray.length - 1; i++) {
if (unSortedArray[i] < pivotElement) {
leftArray.push(unSortedArray[i]);
} else {
rightArray.push(unSortedArray[i]);
}
}
return [...quickSort(leftArray), pivotElement, ...quickSort(rightArray)];
};
console.log(quickSort([-6, 20, 8, 4, -2]));

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

Следите за новостями. Если вы впервые здесь, загляните в наш блог Алгоритмы с Javascript, мы расскажем о нескольких наиболее часто используемых алгоритмах.

В следующем блоге мы рассмотрим Сортировку слиянием.