Быстрая сортировка — это алгоритм сортировки для сортировки списка несортированных элементов в массиве, это алгоритмы разделяй и властвуй (в основном разделяя проблему на подзадачи, пока она не станет легко решить), который работает путем выбора опорного элемента из массива и разделения элементов на два подмассива, один с элементами, которые меньше, чем опорный, а другой с элементами, которые больше опорной точки.
Вы можете выбрать основу:
- Начальный элемент массива
- Последний элемент массива
- Средний элемент массива
- Медиана массива
Для этого блога мы будем использовать подход последнего элемента.
ВРЕМЕННАЯ СЛОЖНОСТЬ:быстрая сортировка имеет временную сложность 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, мы расскажем о нескольких наиболее часто используемых алгоритмах.
В следующем блоге мы рассмотрим Сортировку слиянием.