import Sort from '../Sort';

export default class QuickSort extends Sort {

sort(originalArray) {

// Clone original array to prevent it from modification.

const array = originalArray.slice(0);

// If array has less then or equal to one elements then it is already sorted.

if (array.length <= 1) {

return array;

}

// Init left and right arrays.

const leftArray = [];

const rightArray = [];

// Take the first element of array as a pivot.

const pivotElement = array.shift();

const centerArray = [pivotElement];

// Split all array elements between left, center and right arrays.

while (array.length) {

const currentElement = array.shift();

// Call visiting callback.

this.callbacks.visitingCallback(currentElement);

if (this.comparator.equal(currentElement, pivotElement)) {

centerArray.push(currentElement);

} else if (this.comparator.lessThen(currentElement, pivotElement)) {

leftArray.push(currentElement);

} else {

rightArray.push(currentElement);

}

}

// Sort left and right arrays.

const leftArraySorted = this.sort(leftArray);

const rightArraySorted = this.sort(rightArray);

// Let's now join sorted left array with center array and with sorted right array.

return leftArraySorted.concat(centerArray, rightArraySorted);

}

Quicksort is a divide and conquer algorithm.

Quicksort first divides a large array into two smaller

sub-arrays: the low elements and the high elements.

Quicksort can then recursively sort the sub-arrays

The steps are:

1. Pick an element, called a pivot, from the array.

2. Partitioning: reorder the array so that all elements with

values less than the pivot come before the pivot, while all

elements with values greater than the pivot come after it

(equal values can go either way). After this partitioning,

the pivot is in its final position. This is called the

partition operation.

3. Recursively apply the above steps to the sub-array of

elements with smaller values and separately to the

sub-array of elements with greater values.

Animated visualization of the quicksort algorithm.

The horizontal lines are pivot values.


[Wikipedia](https://en.wikipedia.org/wiki/Quicksort)

import QuickSort from '../QuickSort';

import {

equalArr,

notSortedArr,

reverseArr,

sortedArr,

SortTester,

} from '../../SortTester';

const SORTED_ARRAY_VISITING_COUNT = 190;

const NOT_SORTED_ARRAY_VISITING_COUNT = 62;

const REVERSE_SORTED_ARRAY_VISITING_COUNT = 190;

const EQUAL_ARRAY_VISITING_COUNT = 19;

describe('QuickSort', () => {

it('should sort array', () => {

SortTester.testSort(QuickSort);

});

it('should sort array with custom comparator', () => {

SortTester.testSortWithCustomComparator(QuickSort);

});

it('should do stable sorting', () => {

SortTester.testSortStability(QuickSort);

});

it('should visit EQUAL array element specified number of times', () => {

SortTester.testAlgorithmTimeComplexity(

QuickSort,

equalArr,

EQUAL_ARRAY_VISITING_COUNT,

);

});

it('should visit SORTED array element specified number of times', () => {

SortTester.testAlgorithmTimeComplexity(

QuickSort,

sortedArr,

SORTED_ARRAY_VISITING_COUNT,

);

});

it('should visit NOT SORTED array element specified number of times', () => {

SortTester.testAlgorithmTimeComplexity(

QuickSort,

notSortedArr,

NOT_SORTED_ARRAY_VISITING_COUNT,

);

});

it('should visit REVERSE SORTED array element specified number of times', () => {

SortTester.testAlgorithmTimeComplexity(

QuickSort,

reverseArr,

REVERSE_SORTED_ARRAY_VISITING_COUNT,

);

});